From owner-freebsd-net@FreeBSD.ORG Sat Jun 20 17:54:50 2015 Return-Path: Delivered-To: freebsd-net@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 34D5A710 for ; Sat, 20 Jun 2015 17:54:50 +0000 (UTC) (envelope-from mhall@mhcomputing.net) Received: from mail.mhcomputing.net (ipv6.mhcomputing.net [IPv6:2607:f1c0:800:100::1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 181ECE9 for ; Sat, 20 Jun 2015 17:54:50 +0000 (UTC) (envelope-from mhall@mhcomputing.net) Received: from [192.168.1.160] (99-34-229-174.lightspeed.sntcca.sbcglobal.net [99.34.229.174]) by mail.mhcomputing.net (Postfix) with ESMTPSA id 9B74780BDAB for ; Sat, 20 Jun 2015 10:52:07 -0700 (PDT) From: Matthew Hall Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Subject: address memory layout used by radix tree Message-Id: Date: Sat, 20 Jun 2015 10:54:37 -0700 To: freebsd-net@freebsd.org Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) X-Mailer: Apple Mail (2.1878.6) X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 20 Jun 2015 17:54:50 -0000 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.=