Learning VPP: Inside bihash, the Lock-Free Hash Table

TL;DR — everything that matters, in one paragraph. bihash (the bounded-index extensible hash, clib_bihash in VPP) is the hash table behind almost every VPP table — FIB, L2, NAT sessions, ACL flow caches. Its defining property is lock-free lookups: a reader never takes a lock, so millions of packets per second can probe it concurrently with no contention. The layout is a fixed bucket array (2^log2 buckets); each bucket points to a page of a few key-value pairs (KVPs) that a lookup scans linearly. Collisions are handled by growing the page (4 → 8 → 16 KVPs) — that’s the “extensible” part. Writers take a per-bucket spinlock, build the new page, and atomically swap the bucket pointer; readers detect an in-flight change via a generation counter and simply retry. The name encodes the sizes: bihash_48_8 is a 48-byte key and an 8-byte value. Size it with one number — log2 of the bucket count — and pre-allocate the memory pool up front.

At line rate you can’t afford a mutex on a lookup. A hash table that 140 million packets a second hammer concurrently needs reads that never block and never bounce a cache line between cores. That’s what bihash is for.

The Structure: Buckets, Pages, KVPs

A bihash is three layers (Figure 1):

1. Bucket array — a flat array of 2^log2_nbuckets buckets, fixed at init. Hashing the key picks one bucket.
2. Bucket — a single machine word holding the offset to a page plus log2_pages (how big that page is). Empty buckets are zero.
3. Page of KVPs — an array of BIHASH_KVP_PER_PAGE key-value pairs. A lookup reads the bucket, finds its page, and linearly scans the KVPs comparing keys. With a few entries per page, that scan is effectively O(1) and stays in one or two cache lines.

The KVP sizes are baked into the type name: bihash_48_8 stores a 48-byte key and an 8-byte value (so a packet’s full tuple as the key, a result/index as the value). VPP ships bihash_8_8, _16_8, _24_8, _48_8, and more — you pick the smallest key that holds your data.

Lock-Free Lookups — the Key Trick

This is the part worth understanding. A lookup does no locking at all:

The bucket is a single word, read atomically. A writer never mutates a live page in place — it builds a fresh page, then atomically overwrites the bucket word to point at it. So a reader either sees the old bucket (and the old, still-valid page) or the new one — never a torn state. To catch the rare case where the bucket changes during a scan, each bucket carries a small generation/change counter; if it moved, the reader re-reads the bucket and scans again. Writers serialize on a per-bucket spinlock, so two inserts to the same bucket don’t race — but they never block readers.

The payoff: lookups scale linearly with cores. No shared lock, no cache-line ping-pong on a mutex, no reader ever parked behind a writer.

Extensible: Collisions Grow the Bucket

When two keys hash to the same bucket and its page is full, bihash doesn’t chain or probe elsewhere — it doubles the page. A 4-KVP page becomes an 8-KVP page (a bigger log2_pages), the entries are copied in, and the bucket is swapped to the new page. Lookups still scan one contiguous page; they’re just slightly longer. This keeps the common case (a near-empty bucket) at a single short scan while gracefully absorbing hot buckets — hence extensible.

If a bucket would grow past the configured maximum, the insert fails rather than degrading unboundedly — a signal that the table is undersized for the working set.

Sizing It

A bihash is configured with essentially one knob: log2 of the bucket count (plus a memory budget for the pages). More buckets means fewer collisions and shorter scans, at the cost of memory you allocate up front from a dedicated heap — bihash never calls malloc on the data path.

A practical rule: size the bucket count so the expected entries land roughly one per bucket. For a flow cache holding a worker’s working set of, say, 512 K flows, log2 = 19 (≈ 512 K buckets) keeps almost every lookup a single-entry scan. Oversizing wastes memory; undersizing turns lookups into longer page scans and risks insert failures on hot buckets.

Using bihash: API Notes

A few practical rules from the VPP documentation for when you actually wire one up:

• Pick a template by key/value size. Include e.g. vppinfra/bihash_8_8.h (VPP ships 8/16/20/24/40/48-byte keys, u8 * vector keys, and 8-byte values) and declare the table with BVT(clib_bihash) or the explicit clib_bihash_8_8_t. A standalone app also includes bihash_template.c.
• Init and size it. clib_bihash_init_8_8(h, "name", nbuckets, memory_size). Choose nbuckets ≈ expected_records / BIHASH_KVP_PER_PAGE; the table owns a separate arena, so it’s fine to be generous to absorb collisions.
• Add / update / delete. Set kv.key and kv.value, then clib_bihash_add_del_8_8(h, &kv, is_add) (1 = add, 0 = delete). To update a value, just re-add the pair.
• Lookups take no lock. clib_bihash_search_8_8(h, &search_kv, &return_kv) returns < 0 on a miss. On the packet hot path use clib_bihash_search_inline_with_hash and prefetch ahead: compute the hash early, then call clib_bihash_prefetch_bucket and clib_bihash_prefetch_data a few packets in advance to hide memory latency.
• Iterate with clib_bihash_foreach_key_value_pair. It is OK to delete entries during a walk, but not OK to add — an insert can rehash the current bucket, so entries get skipped or revisited. The iterator does not take the writer lock; take it yourself if your use case needs one.
• The hash function matters. A slow or poorly-distributed hash costs both throughput and space efficiency; a CPU CRC32 intrinsic is a good default.

Summary

1. bihash is VPP’s lock-free hash — the backbone of FIB, L2, NAT, and flow caches.
2. Layout: bucket array → page → linear scan of a few KVPs (≈ O(1)).
3. Reads take no lock; writers build a new page and atomically swap the bucket, readers retry on a generation change.
4. Collisions grow the page (extensible), not a probe chain.
5. The name = sizes (bihash_48_8 = 48 B key, 8 B value); size with log2 buckets, pre-allocated.

References

• VPP bihash — bounded-index extensible hash — the authoritative description and API.
• FD.io VPP source — vppinfra/bihash_template.h — the templated implementation.
• FD.io VPP documentation — the Vector Packet Processor and its data structures.
• The Linux kernel’s rhashtable is the same idea in another codebase — a resizable, RCU-protected hash table with lock-free reads and per-bucket locks for writers. See LWN’s “Relativistic hash tables, part 1: Algorithms” and the practical “The rhashtable documentation I wanted to read”; source in lib/rhashtable.c.
• “Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming” (Triplett, McKenney & Walpole, USENIX ATC 2011) — the paper behind RCU/relativistic hash tables and lock-free resizing.
• Bucket hashing with separate chaining is a textbook algorithm — see Sedgewick & Wayne, Algorithms §3.4 “Hash Tables”, CLRS Introduction to Algorithms ch. 11, and the Wikipedia “Hash table” article (the bucket-array-plus-chains figure this post’s Figure 1 follows).
• Video: MIT 6.006 — “Hashing with Chaining” (Erik Demaine), a clear lecture on the bucket-array-plus-chains model.