address memory layout used by radix tree

[Matthew Hall]

Hello,

I had a few questions about how the FreeBSD radix tree for LPM (longest-prefix match) works. I am working on a fully zero-copy user-space open-source network stack, and I need a radix tree to perform some of the operations. Of course I was looking at the reliable and proven code in BSD to see how I should do this properly.

While reading through everything I was confused about this macro and how it is used in the code:

#define LEN(x) ( (int) (*(const u_char *)(x)) )

The macro seems to assume, effectively, that all the inputs are struct sockaddr and friends, with a length byte in the front. However real addresses in packets don't have length bytes, so it prevents zero-copy operations with minimal manipulation of the packet data. In my case, I'm interested in matching the raw address bytes directly without manipulation, or perhaps just a byte-swap or other minimal change.

After reading through the radix code in radix.[ch] and the radix table manipulation code in ip_fw_table_algo.c, it looks like they need to track the length because they are storing all of the AF_INET entries and all of the AF_INET6 entries into the same radix tree.

To me it seems much simpler if I would just maintain one radix tree for AF_INET4, and a second one for AF_INET6, and store the current address key length in the radix tree's own struct instead. Then the client lookup code can just point to starts of addresses for lookups and tree updates, and the radix tree will already know how many bytes to match with, and I won't need the weird sockaddr memory layout or the secret byte for the LEN macro at all.

Is this reasoning correct or did I miss anything?

Thanks,
Matthew.