Date: Sat, 20 Jun 2015 10:54:37 -0700 From: Matthew Hall <mhall@mhcomputing.net> To: freebsd-net@freebsd.org Subject: address memory layout used by radix tree Message-ID: <F6ED3CE8-9786-414A-A75F-1660104B5670@mhcomputing.net>
next in thread | raw e-mail | index | archive | help
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.=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?F6ED3CE8-9786-414A-A75F-1660104B5670>