VPP Fib ipv4 Debugging

logic.txt

This info was reverse engineered based on the vpp code ip4_mtrie.[ch]

VPP stores ip4 fib entries in a 16-8-8 mtrie.

This means the first 16 bits is looked up in an array of 2^16 entries (root ply). 
That first lookup points to another lookup table of 2^8 entries (for indexed using the 3rd octet) and 
another for the 4th octet.

Each table is called a ply table.

Entry point function is ip4_fib_mtrie_route_add()

Logs.md

For Example, if you are programming a route to fib 1.2.3.4/24, you will find these entries at these indices:

Suppose this route is to be added into fib table with (fib_index of 10) - get the fib pointer

#1 Get Fib pointer

(gdb) set $fib_idx=0
(gdb) ptype ip4_main.v4_fibs[$fib_idx]
type = struct ip4_fib_t_ {
    u8 cacheline0[];
    ip4_fib_mtrie_t mtrie;
    uword *fib_entry_by_dst_address[33];
    u32 table_id;
    u32 index;
}

(gdb) p &ip4_main.v4_fibs[$fib_idx]
$146 = (struct ip4_fib_t_ *) 0x7fffa7b939c0

#2 Get to the root ply and walk down

(gdb) ptype ip4_main.v4_fibs[$fib_idx].mtrie
type = struct {
    ip4_fib_mtrie_16_ply_t root_ply;
}

(gdb) ptype ip4_main.v4_fibs[$fib_idx].mtrie.root_ply
type = struct ip4_fib_mtrie_16_ply_t_ {
    union {
        ip4_fib_mtrie_leaf_t leaves[65536];
        u32x4 leaves_as_u32x4[16384];
    };
    u8 dst_address_bits_of_leaves[65536];
}

Lookup by the first 16bits of the IP address (and in the host byte order) So, the index to lookup is 0x0201 (513 decimal).

(gdb) p /x ip4_main.v4_fibs[$fib_idx].mtrie.root_ply.leaves[0x0201]
$149 = 0xa

this number decimal 10 (0xa) - indicates this is NOT the leaf ply. All leaf ply will be odd meaning the LSB will be set to 1.

to convert the leaf index to the ply - look remove the lsb 1 bit and the msb 31bits is the index into the ip4_ply_pool.

(gdb) p /x ip4_ply_pool[0xa >> 1]
$151 = {{leaves = {0x3, 0x3, 0x3, 0x10, 0x3 <repeats 252 times>}, leaves_as_u32x4 = {{0x3, 0x3, 0x3, 0x10}, {0x3, 0x3, 0x3, 
        0x3} <repeats 63 times>}}, dst_address_bits_of_leaves = {0x0, 0x0, 0x0, 0x18, 0x0 <repeats 252 times>}, n_non_empty_leafs = 0x1, 
  dst_address_bits_base = 0x10, pad = {0x0 <repeats 56 times>}}
(gdb) 

In this ply - the lookup key is 0x3 (third octect of the IP address) - this is again NOT the terminal node - hence even index is present (0x10)

Now lets look at the 3rd lookup (for the 4th octect):

(gdb) p /x ip4_ply_pool[0x10 >> 1]
$157 = {{leaves = {0x15, 0x13, 0x13, 0x13, 0x19, 0x13 <repeats 250 times>, 0x17}, leaves_as_u32x4 = {{0x15, 0x13, 0x13, 0x13}, {0x19, 0x13, 
        0x13, 0x13}, {0x13, 0x13, 0x13, 0x13} <repeats 61 times>, {0x13, 0x13, 0x13, 0x17}}}, dst_address_bits_of_leaves = {0x20, 0x18, 0x18, 
    0x18, 0x20, 0x18 <repeats 250 times>, 0x20}, n_non_empty_leafs = 0x3, dst_address_bits_base = 0x18, pad = {0x0 <repeats 56 times>}}
(gdb) 

Here the lookup index is 4 - which points to 0x19 - since this is ODD - this is the terminal NODE.

The adj index is the MSB 31bits (ie decimal 12 (0xC)).