THEORY OF OPERATION(9)

🌸 THEORY OF OPERATION(9) 🌸

okay bestie, so this is Theory of Operation(9) from the Kernel API Manual — it's the whole brain-dump on how this packet-matching thing actually works, and honestly? it ate. let's get into it 💅

---

💖 PROBLEM 💖

so the whole ~vibe~ here is: match packet bytes against entries that are made out of ranged or non-ranged packet field specifiers, and then map those matches to arbitrary references. it's giving matchmaking but for packets ✨ like:

                     --- fields --->
            |    [net],[port],[net]... => [reference]
         entries [net],[port],[net]... => [reference]
            |    [net],[port],[net]... => [reference]
            V    ...

where [net] fields can be IP ranges or netmasks, and [port] fields are port ranges. and like — arbitrary packet fields can be matched. anything. iconic behavior fr fr 👑

---

🦋 ALGORITHM OVERVIEW 🦋

this algorithm is loosely inspired by [Ligatti 2010], and lowkey it fundamentally relies on the whole idea that every contiguous range in a space of b bits can be converted into b * 2 netmasks — that's from Theorem 3 in [Rottenstreich 2010], and it's also illustrated in Section 9 of [Kogan 2014]. so like, citations but make it slay 💅

so classification against a bunch of entries — the ones that require matching given bits of a packet field — is performed by grouping those bits in sets of arbitrary size, and then classifying packet bits one group at a time.

Example: to match the source port (16 bits) of a packet, we can divide those 16 bits in 4 groups of 4 bits each. Given the entry: 0000 0001 0101 1001 and a packet with source port: 0000 0001 1010 1001 — first and second groups match, but the third doesn't. We conclude that the packet doesn't match the given entry.

then you translate the set to a sequence of lookup tables, one per field. each table has two dimensions, bestie: the bit groups to be matched for a single packet field, and all the possible values of said groups (those are the buckets 🪣).

input entries are represented as one or more rules, depending on the number of composing netmasks for the given field specifier, and a group match is indicated as a set bit, with the number corresponding to the rule index, in all the buckets whose value matches the entry for a given group.

rules are mapped between fields through an array of x, n pairs, with each item mapping a matched rule to one or more rules. the position of the pair in the array indicates the matched rule to be mapped to the next field, x indicates the first rule index in the next field, and n the amount of next-field rules the current rule maps to.

and the mapping array for the last field maps to the desired references. 🎯

to match, we perform table lookups using the values of grouped packet bits, and use a sequence of bitwise operations to progressively evaluate rule matching. it's giving math girlie supremacy ngl

a stand-alone, reference implementation — which also includes notes about possible future optimisations — is available at: https://pipapo.lameexcu.se/

(go visit her, she's iconic 🌈)

---

🎀 INSERTION 🎀

here's the whole inserting-something-into-the-thing pipeline, step by step:

• for each packet field:
  • divide the b packet bits we want to classify into groups of size t, obtaining ceil(b / t) groups

Example: match on destination IP address, with t = 4: 32 bits, 8 groups of 4 bits each

• allocate a lookup table with one column ("bucket") for each possible value of a group, and with one row for each group

Example: 8 groups, 2^4 buckets:

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0
              1
              2
              3
              4
              5
              6
              7

• map the bits we want to classify for the current field, for a given entry, to a single rule for non-ranged and netmask set items, and to one or multiple rules for ranges. ranges are expanded to composing netmasks by pipapo_expand.

Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048 - rule #0: 10.0.0.5 - rule #1: 192.168.1.0/24 - rule #2: 192.168.2.0/31

• insert references to the rules in the lookup table, selecting buckets according to bit values of a rule in the given group. this is done by pipapo_insert.

Example: given: - rule #0: 10.0.0.5 mapping to buckets < 0 10 0 0 0 0 0 5 > - rule #1: 192.168.1.0/24 mapping to buckets < 12 0 10 8 0 1 < 0..15 > < 0..15 > > - rule #2: 192.168.2.0/31 mapping to buckets < 12 0 10 8 0 2 0 < 0..1 > > these bits are set in the lookup table:

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0    0                                              1,2
              1   1,2                                      0
              2    0                                      1,2
              3    0                              1,2
              4  0,1,2
              5    0   1   2
              6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
              7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1

• if this is not the last field in the set, fill a mapping array that maps rules from the lookup table to rules belonging to the same entry in the next lookup table, done by pipapo_map.

Note that as rules map to contiguous ranges of rules, given how netmask expansion and insertion is performed, union nft_pipapo_map_bucket stores this information as pairs of first rule index, rule count.

Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048, given lookup table #0 for field 0 (see example above):

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0    0                                              1,2
              1   1,2                                      0
              2    0                                      1,2
              3    0                              1,2
              4  0,1,2
              5    0   1   2
              6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
              7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1

and lookup table #1 for field 1 with: - rule #0: 1024 mapping to buckets < 0 0 4 0 > - rule #1: 2048 mapping to buckets < 0 0 5 0 >

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0   0,1
              1   0,1
              2                    0   1
              3   0,1

we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024 in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1 (rules #1, #2) to 2048 in lookup table #2 (rule #1):

             rule indices in current field: 0    1    2
             map to rules in next field:    0    1    1

• if this is the last field in the set, fill a mapping array that maps rules from the last lookup table to element pointers, also done by pipapo_map.

Note that, in this implementation, we have two elements (start, end) for each entry. The pointer to the end element is stored in this array, and the pointer to the start element is linked from it.

Example: entry 10.0.0.5:1024 has a corresponding struct nft_pipapo_elem pointer, 0x66, and element for 192.168.1.0-192.168.2.1:2048 is at 0x42. From the rules of lookup table #1 as mapped above:

             rule indices in last field:    0    1
             map to elements:             0x66  0x42

---

⭐ MATCHING ⭐

okay so for matching we use a result bitmap, with the size of a single lookup table bucket, to represent the matching state that applies at every algorithm step. this is done by pipapo_lookup. she's the main character here, no cap 👑

• for each packet field:
  • start with an all-ones result bitmap (res_map in pipapo_lookup)
  • perform a lookup into the table corresponding to the current field, for each group, and at every group, AND the current result bitmap with the value from the lookup table bucket

            Example: 192.168.1.5 < 12 0  10 8  0 1  0 5 >, with lookup table from
            insertion examples.
            Lookup table buckets are at least 3 bits wide, we'll assume 8 bits for
            convenience in this example. Initial result bitmap is 0xff, the steps
            below show the value of the result bitmap after each group is processed:

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0    0                                              1,2
              result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6

              1   1,2                                      0
              result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6

              2    0                                      1,2
              result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6

              3    0                              1,2
              result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6

              4  0,1,2
              result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6

              5    0   1   2
              result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2

              6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
              result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2

              7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
              final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2

• at the next field, start with a new, all-zeroes result bitmap. for each bit set in the previous result bitmap, fill the new result bitmap (fill_map in pipapo_lookup) with the rule indices from the corresponding buckets of the mapping field for this field, done by pipapo_refill

Example: with mapping table from insertion examples, with the current result bitmap from the previous example, 0x02:

             rule indices in current field: 0    1    2
             map to rules in next field:    0    1    1

the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be set.

We can now extend this example to cover the second iteration of the step above (lookup and AND bitmap): assuming the port field is 2048 < 0 0 5 0 >, with starting result bitmap 0x2, and lookup table for "port" field from pre-computation example:

                           bucket
            group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
              0   0,1
              1   0,1
              2                    0   1
              3   0,1

operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5] & 0x3 [bucket 0], resulting bitmap is 0x2.

• if this is the last field in the set, look up the value from the mapping array corresponding to the final result bitmap

Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for last field from insertion example:

             rule indices in last field:    0    1
             map to elements:             0x66  0x42

the matching element is at 0x42. ✨ found her ✨

---

📚 REFERENCES 📚

---

…and that's where part 2 picks it up bestie, don't go anywhere 💖

…and the reference list wraps up with these three certified bangers, bestie:

• [Ligatti 2010] — A Packet-classification Algorithm for Arbitrary Bitmask Rules, with Automatic Time-space Tradeoffs by Jay Ligatti, Josh Kuhn, and Chris Gage. Proceedings of the IEEE International Conference on Computer Communication Networks (ICCCN), August 2010. https://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf
• [Rottenstreich 2010] — Worst-Case TCAM Rule Expansion by Ori Rottenstreich and Isaac Keslassy. 2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592rep=rep1type=pdf
• [Kogan 2014] — SAX-PAC (Scalable And eXpressive PAcket Classification) by Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane, and Patrick Eugster. Proceedings of the 2014 ACM conference on SIGCOMM, August 2014. https://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf

---

👀 SEE ALSO 👀

okay so the see-also section is literally a whole friend group of pipapo functions, no cap. first up, the kernel file itself:

Kernel file ./net/netfilter/nft_set_pipapo.c

then the squad — every single one, exactly as written, because we do not leave anyone out:

• pipapo_refill(9)
• pipapo_get_slow(9)
• pipapo_get(9)
• nft_pipapo_lookup(9)
• nft_pipapo_get(9)
• pipapo_realloc_mt(9)
• lt_calculate_size(9)
• pipapo_resize(9)
• pipapo_bucket_set(9)
• pipapo_lt_4b_to_8b(9)
• pipapo_lt_8b_to_4b(9)
• pipapo_lt_bits_adjust(9)
• pipapo_insert(9)
• pipapo_step_diff(9)
• pipapo_step_after_end(9)
• pipapo_base_sum(9)
• pipapo_expand(9)
• pipapo_map(9)
• pipapo_free_scratch(9)
• pipapo_realloc_scratch(9)
• pipapo_maybe_clone(9)
• nft_pipapo_insert(9)
• pipapo_clone(9)
• pipapo_rules_same_key(9)
• pipapo_unmap(9)
• pipapo_drop(9)
• pipapo_gc_scan(9)
• pipapo_gc_queue(9)
• pipapo_free_fields(9)
• pipapo_reclaim_match(9)
• nft_pipapo_commit(9)
• nft_pipapo_activate(9)
• nft_pipapo_deactivate(9)
• nft_pipapo_flush(9)
• pipapo_get_boundaries(9)
• pipapo_match_field(9)
• nft_pipapo_remove(9)
• nft_pipapo_do_walk(9)
• nft_pipapo_walk(9)
• nft_pipapo_privsize(9)
• nft_pipapo_estimate(9)
• nft_pipapo_init(9)
• nft_set_pipapo_match_destroy(9)
• nft_pipapo_destroy(9)
• nft_pipapo_gc_init(9)

and that’s the whole page, bestie ✨ this icon lives in ./net/netfilter, it’s dated October 2026, and it’s proudly titled Theory of Operation(9) — mwah 💋💖