vault

Hash and Array Maps

17 min read

Hash and Array Maps

BPF_MAP_TYPE_HASH and BPF_MAP_TYPE_ARRAY are the two foundational BPF map types — the default tools a Berkeley Packet Filter (BPF) program reaches for when it needs keyed storage or indexed storage. A hash map is a general-purpose hash table: arbitrary-byte keys and values (both may be structs), entries created and freed dynamically up to a max_entries ceiling, protected by per-bucket spinlocks for concurrent access. An array map is a fixed-size array: the key is always a 4-byte u32 index, every slot is pre-allocated and zero-initialized at creation, and there is no deletion because the size never changes. The two embody opposite trade-offs — the hash is flexible but pays for dynamic allocation and hashing; the array is rigid but is the fastest possible lookup (a bounds check and an index). One detail makes the array quietly central to all of eBPF: a single-entry array map, made memory-mappable, is how BPF global variables (.data, .bss, .rodata) are implemented. This note covers both types’ internals as they stand in Linux 6.12 LTS (verified unchanged in 6.18 LTS), from the kernel sources kernel/bpf/hashtab.c and kernel/bpf/arraymap.c.

Mental Model: Dynamic-and-Keyed vs Fixed-and-Indexed

Think of the hash map as a HashMap<K, V> and the array as a Vec<V> of fixed length. The hash lets you key by anything — a 5-tuple, a PID, a string — and grows entries as you insert them; the array forces a dense integer index 0..max_entries and exists in full from the moment it is created. That single structural difference cascades into every other property:

flowchart TB
  subgraph HASH["BPF_MAP_TYPE_HASH"]
    HK["key: any bytes<br/>(struct OK)"] --> HF["hash(key) &amp; (n_buckets-1)"]
    HF --> HB["bucket (hlist + raw_spinlock)"]
    HB --> HE["htab_elem: key + value<br/>(allocated on insert)"]
  end
  subgraph ARR["BPF_MAP_TYPE_ARRAY"]
    AK["key: u32 index"] --> AC["index &gt;= max_entries? -&gt; NULL"]
    AC --> AS["value at base + index*elem_size<br/>(pre-allocated, zeroed)"]
  end

The two foundational map types side by side. What it shows: the hash path runs key bytes through a hash, masks into one of n_buckets buckets, takes that bucket’s spinlock, and walks a short collision list of dynamically allocated htab_elems; the array path bounds-checks a u32 index and returns a pointer to a pre-allocated, zero-initialized slot with no lock at all. The insight to take: the hash trades speed and predictability for flexibility (any key, dynamic membership); the array trades flexibility for the fastest, most predictable, lock-free access — which is exactly why globals and per-CPU hot paths are built on arrays, not hashes.

BPF_MAP_TYPE_ARRAY — Fixed, Pre-allocated, Index-keyed

The shape and its constraints

An array map is, per Documentation/bpf/map_array.rst, “generic array storage. The key type is an unsigned 32-bit integer (4 bytes) and the map is of constant size.” It was introduced in kernel 3.19. The validation in array_map_alloc_check() (kernel/bpf/arraymap.c, v6.12) enforces the rules:

/* kernel/bpf/arraymap.c (v6.12), abridged */
if (attr->max_entries == 0 || attr->key_size != 4 ||
    attr->value_size == 0 ||
    attr->map_flags & ~ARRAY_CREATE_FLAG_MASK ||
    ...)
        return -EINVAL;

Walking this: max_entries must be non-zero; key_size must be exactly 4 (the u32 index is non-negotiable — try to create an array with any other key size and you get -EINVAL); value_size must be non-zero. The value may be any size, but the kernel rounds each element up to an 8-byte boundary (elem_size = round_up(attr->value_size, 8)), so a 4-byte value still consumes 8 bytes per slot.

Pre-allocation and zero-initialization

The defining property is in array_map_alloc(): all elements are allocated and zero-initialized at creation time. There is no per-insert allocation ever; the entire max_entries * elem_size block is reserved up front. This is why an array lookup is just arithmetic:

/* kernel/bpf/arraymap.c (v6.12) */
static void *array_map_lookup_elem(struct bpf_map *map, void *key)
{
        struct bpf_array *array = container_of(map, struct bpf_array, map);
        u32 index = *(u32 *)key;
 
        if (unlikely(index >= array->map.max_entries))
                return NULL;
        return array->value + (u64)array->elem_size * (index & array->index_mask);
}

The lookup reads the u32 index, bounds-checks it against max_entries (returning NULL if out of range), and returns a pointer at base + index * elem_size. There is no lock, no hash, no allocation — a bounds check and a multiply-add. The & array->index_mask is a Spectre-v1 hardening: the array is internally rounded up to a power of two and the index is masked so that even a speculative out-of-bounds index cannot read past the allocation (the masking is skipped only when bpf_bypass_spec_v1() says the platform doesn’t need it). Because the slot always exists and is never freed, bpf_map_delete_elem is not supported on arrays — to “clear” a slot you update_elem it to a zero value, as the documentation spells out.

lookup-returns-pointer and the data-race trap

As with all maps reached from a BPF program, bpf_map_lookup_elem on an array returns a direct pointer into the live slot — no copy. The documentation is explicit that the user “must use primitives like __sync_fetch_and_add() when updating the value in-place” to avoid racing with a userspace reader. A counter incremented as *value += 1 from two CPUs will lose updates; __sync_fetch_and_add(value, 1) will not. (The contention-free alternative — a per-CPU array, where each core has its own copy — is covered in Per-CPU Maps; this note stays on the plain shared array.)

BPF_F_MMAPABLE and memory mapping

Since kernel 5.5, an array map (and only an array map — the array_map_alloc_check rejects BPF_F_MMAPABLE on any other type) can be created with the BPF_F_MMAPABLE flag, which lets userspace mmap() the map’s value memory directly. The kernel allocates the storage page-aligned with vmalloc so it can be mapped:

/* kernel/bpf/arraymap.c (v6.12), abridged */
if (attr->map_flags & BPF_F_MMAPABLE) {
        array_size = PAGE_ALIGN(array_size);
        array_size += PAGE_ALIGN((u64) max_entries * elem_size);
}
...
data = bpf_map_area_mmapable_alloc(array_size, numa_node);

The map definition starts on the first page and the values on the second, “which in some cases will result in over-allocation of memory” (the documentation’s words — small maps waste up to a page). The payoff: userspace reads and writes the map’s contents as plain memory, with no bpf() syscall per access. This is a real performance win for tight userspace↔BPF data sharing, and it is the mechanism on which global variables are built.

Global Variables Are Single-Entry Array Maps

A BPF C program can declare what look like ordinary global variables:

const volatile int target_pid = 0;   /* .rodata — a tunable constant */
int dropped_packets = 0;              /* .bss / .data — mutable state */

A BPF program has no address space of its own that survives between invocations (see BPF Maps on why programs are stateless), so these cannot be globals in the ordinary sense. Instead, the loader (libbpf) turns each ELF data section — .data, .bss, .rodata, and the .kconfig pseudo-section — into a single-entry BPF_MAP_TYPE_ARRAY, where the one value (at index 0) is the entire section laid out as a struct. This is visible directly in libbpf’s bpf_object__init_internal_map() (tools/lib/bpf/libbpf.c, v6.12):

/* tools/lib/bpf/libbpf.c (v6.12), abridged */
def->type = BPF_MAP_TYPE_ARRAY;
def->key_size = sizeof(int);
def->value_size = data_sz;                       /* the whole section */
def->max_entries = 1;                            /* single entry */
def->map_flags = type == LIBBPF_MAP_RODATA || type == LIBBPF_MAP_KCONFIG
                 ? BPF_F_RDONLY_PROG : 0;        /* read-only constants */
...
if (map_is_mmapable(obj, map))
        def->map_flags |= BPF_F_MMAPABLE;        /* so userspace can poke it */

Walking this: value_size is the size of the entire data section (all your globals packed into one struct); max_entries is 1; for .rodata and .kconfig the map gets BPF_F_RDONLY_PROG, which makes it read-only from the BPF program’s side (the verifier forbids writes) while still being writable by the loader before the program runs; and the map is made BPF_F_MMAPABLE so the loader and the userspace skeleton can read and write the globals as plain memory. When the compiler emits a reference to target_pid, it becomes a load from “this internal array map, offset of target_pid within the section.”

This design is what makes two powerful patterns work. First, read-only globals as constants the verifier can propagate: because .rodata is frozen (the loader calls BPF_MAP_FREEZE on it before load — libbpf “freeze[s] .rodata and .kconfig map as read-only from syscall side”), the verifier treats const volatile globals as known constants and can dead-code-eliminate branches on them. This is how libbpf does “compile once, configure at load time”: you set target_pid from userspace before loading, and the verifier sees a constant. Second, mutable globals as shared state: a .bss/.data global is just an mmap’d array slot, so userspace reads skel->bss->dropped_packets as a struct field with zero syscalls. The BPF skeleton generated by bpftool gen skeleton (see BPF Skeletons and bpftool) exposes these sections as typed C structs precisely because they are mmap’d array maps.

Uncertain

Verify: that the verifier’s constant-propagation / dead-code-elimination of const volatile .rodata globals depends specifically on the BPF_MAP_FREEZE step (and not merely on the BPF_F_RDONLY_PROG flag). Reason: I confirmed from libbpf source that .rodata is created with BPF_F_RDONLY_PROG and frozen, and that this is how load-time-constant tuning works, but I did not read the verifier code that performs the constant folding to confirm the exact precondition. To resolve: read mark_map_contents_read_only / the direct-value-read path in kernel/bpf/verifier.c for 6.12. #uncertain

BPF_MAP_TYPE_HASH — Dynamic, Hashed, Bucket-locked

The shape

A hash map provides “general purpose hash map storage. Both the key and the value can be structs, allowing for composite keys and values” (per map_hash.rst; introduced in kernel 3.19). Unlike the array, there is no constraint that the key be 4 bytes — it can be any size, and a struct key (say, a packet 5-tuple) is the common case. The kernel allocates and frees key/value pairs dynamically, up to max_entries.

Internally (kernel/bpf/hashtab.c, v6.12), the table is an array of buckets, each a struct bucket:

/* kernel/bpf/hashtab.c (v6.12) */
struct bucket {
        struct hlist_nulls_head head;   /* collision chain */
        raw_spinlock_t raw_lock;        /* per-bucket lock */
};

The number of buckets is roundup_pow_of_two(max_entries), so the bucket index is computed by hashing the key and masking with n_buckets - 1. Each bucket is a hlist_nulls — a singly-linked list with a special “nulls” terminator that encodes the bucket index, used to detect a race where a lookup follows a chain that gets moved to a different bucket under RCU. Each map element is a struct htab_elem carrying its hash, its key, and its value inline (key[] is a flexible array; the value follows after the 8-byte-rounded key).

Concurrency: per-bucket lock plus a reentrancy guard

A hash map can be accessed concurrently from programs on different CPUs, so it needs locking. The mechanism is finer-grained than one big lock and subtler than just “a lock per bucket.” htab_lock_bucket() does two things:

/* kernel/bpf/hashtab.c (v6.12), abridged */
static inline int htab_lock_bucket(const struct bpf_htab *htab,
                                   struct bucket *b, u32 hash, unsigned long *pflags)
{
        hash = hash & min_t(u32, HASHTAB_MAP_LOCK_MASK, htab->n_buckets - 1);
        preempt_disable();
        local_irq_save(flags);
        if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
                __this_cpu_dec(*(htab->map_locked[hash]));
                local_irq_restore(flags);
                preempt_enable();
                return -EBUSY;          /* re-entrant access on this CPU */
        }
        raw_spin_lock(&b->raw_lock);    /* the actual per-bucket lock */
        *pflags = flags;
        return 0;
}

The raw_spin_lock(&b->raw_lock) is the per-bucket spinlock — different buckets can be modified concurrently with no contention, which is the whole point of hashing into many buckets. But there is a second layer: an 8-way per-CPU counter array (map_locked[HASHTAB_MAP_LOCK_COUNT], HASHTAB_MAP_LOCK_COUNT == 8) that detects reentrancy on the same CPU. Because a BPF program might fire inside a context where it has already taken a bucket lock — for example, a kprobe attached to a function that the hash-map update path itself calls, or an NMI interrupting an update — a naive raw_spin_lock would deadlock. The per-CPU counter catches this: if the same CPU tries to lock a bucket (modulo 8) it already holds, the increment returns ≠ 1, and the call bails out with -EBUSY instead of deadlocking. The BPF program sees the update simply fail, which is the safe outcome. This is a concrete example of how BPF data structures must be hardened against running in arbitrary, possibly nested, kernel contexts.

Pre-allocation by default; BPF_F_NO_PREALLOC and the allocator trade-off

The most important operational property of the hash map: it pre-allocates all its elements by default. The documentation states it plainly — “Hash maps use pre-allocation of hash table elements by default. The BPF_F_NO_PREALLOC flag can be used to disable pre-allocation when it is too memory expensive.” At creation, prealloc_init() allocates max_entries (plus a few extra per-CPU spares) htab_elems up front and threads them onto a per-CPU free-list. An insert then just pops a pre-allocated element off the free-list; a delete pushes it back. No memory allocation happens on the update path at all.

Why is pre-allocation the default, given it costs max_entries × elem_size of memory whether or not the map fills up? Because of where BPF programs run. A hash map update can be triggered from contexts where calling the kernel’s general memory allocator is forbidden — inside a non-maskable interrupt (NMI), or from a kprobe attached deep in the allocator itself, where re-entering the allocator would deadlock or corrupt state. Pre-allocating sidesteps the problem entirely: the memory already exists, so the update path never calls into the page allocator. The source comment in hashtab.c records exactly this history — before a dedicated BPF allocator existed, dynamic allocation in these contexts was unsafe, so prealloc was mandatory for them.

With BPF_F_NO_PREALLOC, elements are instead allocated on demand on each insert — but, as of 6.12, not via plain kmalloc. The non-prealloc path uses bpf_mem_alloc, a purpose-built BPF allocator (bpf_mem_cache_alloc(&htab->ma)), which maintains its own per-CPU caches of free objects so that allocation is safe even from NMI and other restricted contexts. The alloc_htab_elem() function shows the fork directly:

/* kernel/bpf/hashtab.c (v6.12), abridged */
if (prealloc) {
        l = __pcpu_freelist_pop(&htab->freelist);   /* pop a pre-allocated elem */
        if (!l)
                return ERR_PTR(-E2BIG);
        l_new = container_of(l, struct htab_elem, fnode);
} else {
        if (is_map_full(htab) && !old_elem)
                return ERR_PTR(-E2BIG);
        l_new = bpf_mem_cache_alloc(&htab->ma);      /* allocate on demand */
        if (!l_new)
                return ERR_PTR(-ENOMEM);
}

So the trade-off is: prealloc uses more memory (the full max_entries is reserved immediately) but gives constant-time, allocation-free, deadlock-proof updates; no-prealloc uses memory proportional to actual occupancy (good when a map is rarely full or max_entries is huge), at the cost of an allocation per insert — still safe, thanks to bpf_mem_alloc, but with the latency and failure mode (-ENOMEM) of a real allocation. The historical reason prealloc was the default — allocation being unsafe in BPF contexts — has been substantially addressed by bpf_mem_alloc, but prealloc remains the default for predictability.

Operations and iteration

bpf_map_update_elem(map, key, value, flags) inserts or replaces atomically; BPF_ANY insert-or-update, BPF_NOEXIST insert-only, BPF_EXIST update-only. bpf_map_lookup_elem returns a pointer to the value (or NULL). bpf_map_delete_elem removes by key. From userspace, iteration uses BPF_MAP_GET_NEXT_KEY: pass NULL to get the first key, then each key to get the next, until -ENOENT. A caveat the documentation flags: if the current key is deleted between calls, get_next_key restarts at the first key, so when iteration and deletion are interleaved you should use the batched lookup operations instead.

Comparison: When to Choose Which

Choose an array when the key space is a small dense integer range (a CPU index, a small enum, a fixed table of constants), when you need the fastest and most predictable lookup (no hashing, no locking, no allocation), or when you need to mmap the data into userspace (only arrays can). Global variables, lookup tables indexed by syscall number or protocol, and per-CPU scratch buffers are all array territory.

Choose a hash when the key is arbitrary or large (a 5-tuple, a PID, a string), when membership is dynamic (you don’t know which keys will appear), or when occupancy is sparse relative to the key space. Connection-tracking tables, per-PID statistics, and blocklists keyed by IP are hash territory. If the hash will fill and you want eviction rather than insert failures, reach for an LRU hash; if it is a hot counter and you want to eliminate cross-CPU contention, reach for a per-CPU hash or array.

A subtle middle case: a small bounded set of counters keyed by a value you control (e.g. an error-code enum) is better as an array indexed by the code than as a hash keyed by it — same semantics, but lock-free and allocation-free.

Failure Modes and Common Misunderstandings

  • “bpf_map_delete_elem returns -EINVAL on my array.” Arrays don’t support deletion; the size is fixed. Write a zero value to the slot instead.
  • Array creation fails with -EINVAL and you used a non-u32 key. Array keys must be exactly 4 bytes. Use a hash if you need a wider or struct key.
  • BPF_F_MMAPABLE rejected. Only BPF_MAP_TYPE_ARRAY accepts it; the array_map_alloc_check returns -EINVAL for any other type, including per-CPU array.
  • Hash insert returns -E2BIG. The map is full (max_entries reached) and you’re inserting a new key. A plain hash does not evict — use an LRU hash if you want eviction, or size max_entries larger.
  • Hash update fails intermittently with -EBUSY. The per-CPU reentrancy guard fired — the same CPU tried to update a bucket it already held (nested BPF execution, e.g. a kprobe on a function in the update path). This is the deadlock-avoidance mechanism working as intended; the fix is to avoid attaching to functions on the map’s own update path.
  • A const volatile global isn’t being treated as a constant by the verifier. It must live in .rodata (declared const) and the loader must freeze the map before load; a plain mutable global in .bss/.data is not constant-folded.
  • Userspace writes to .rodata after load are silently ineffective or rejected. Once frozen (BPF_MAP_FREEZE), .rodata is read-only from the syscall side; set tunables before loading the program.
  • Lost counter updates on a shared hash/array value. Read-modify-write race across CPUs; use __sync_fetch_and_add or a per-CPU map.

Production Notes

The hash map is the workhorse of BPF observability: a bpftrace one-liner that aggregates by a key is creating a hash map, and the prealloc-by-default behavior means a hash sized max_entries = 1_000_000 reserves that memory immediately — a frequent surprise when a tool’s RSS jumps at startup. Setting BPF_F_NO_PREALLOC is the standard fix when the key space is huge but sparsely populated, now that bpf_mem_alloc makes on-demand allocation safe. The array map’s mmap path is the foundation of every modern libbpf tool’s configuration story: tools set const volatile tunables and read .bss counters through the skeleton’s typed structs without a single per-access syscall. When sizing a hash-based connection tracker, the lesson learned repeatedly in production is that a plain hash fails closed when full (drops new flows) while an LRU fails open (evicts old flows) — picking the wrong one turns a capacity problem into either dropped connections or forgotten state, and the symptom is far removed from the undersized max_entries.

See Also

Graph View

Backlinks