On demand routing redux (RFC 3561 AODV preparatory)

[Bruce M Simpson]

Hi all,

Here's some more stuff I'd like review on. I've written a simple bit of code
which just sits there listening for RTM_RESOLVE and redirects destination
cloned route using RTM_CHANGE.

I wrote this to prove we could implement in-demand routing protocols, in
userland, without any of the stupid kernel modifications we've seen for
Linux implementations.

Specify a CIDR network on the command line; it will configure a disc(4)
interface and add a network route via that interface. Currently, the netmask
code is broken; Bill Fenner has given me feedback on how to fix this.

You can sidestep this by creating the disc0 route before running rtmhack:
 # ifconfig disc0 create
 # route -n add 10.0.0.0/8 -iface disc0

The name 'disc0' was not chosen deliberately.

Needless to say, this code is really hackish, and will be getting cleaned
up thoroughly before it is anywhere near production quality.

Please let me know your thoughts. Comments and feedback solicited.

BMS
-------------- next part --------------

The proof of concept code simply updates the route to point to a
loopback interface (which deliberately creates a local routing loop
for the purposes of demonstration).

A cloning XRESOLVE route is bound to a local 'bit bucket' interface,
disc0, for a given network prefix. Any use of this route will cause a child
route to be created via the CLONING mechanism, and an RTM_RESOLVE message
will be generated which we later reply to.

The only information delivered in an RTM_RESOLVE message is the address for
which the kernel is requesting routing information. Therefore it will be
necessary to check the sockaddr against the list of addresses for hosts
and/or networks which we manage, and discard the message if it doesn't match.

It looks as though we can't send an RTM_RESOLVE back to the kernel.
Instead, we have to use RTM_CHANGE to modify the cloned route.

The CLONING mechanism sets the IFP. So we must reset that when sending an
RTM_CHANGE to the kernel, by using an empty sockaddr_dl for the IFP; this
means that it will be inferred from RTAX_GATEWAY.

The required fields for an RTM_CHANGE are: destination, gateway, flags
(and genmask if specifying a network route).  ifa/ifp should also be
specified if changing an interface route.

RTA_AUTHOR doesn't appear to be used anywhere in the kernel. This attribute
could be potentially useful for recording the originator of AODV routes
in-kernel; for now, this information shall reside only in aodvd's MIB.
-------------- next part --------------
/*      $FreeBSD$ */

/*
 * This is a hack to demonstrate the concept of hooking for the
 * RTM_RESOLVE message being sent from the FreeBSD routing code,
 * as a means of looking up routes on demand using a routing protocol
 * such as AODV.
 * This code will probably be vastly cleaned up and tested more thoroughly
 * before being used as the basis for a user-space BSD AODV implementation.
 */

/*
 * Copyright (c) 2003 Bruce M. Simpson <bms at spc.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *        This product includes software developed by Bruce M. Simpson.
 * 4. Neither the name of Bruce M. Simpson nor the names of co-
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Bruce M. Simpson AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL Bruce M. Simpson OR CONTRIBUTORS
 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/file.h>
#include <sys/socket.h>
#include <sys/sysctl.h>
#include <sys/ioctl.h>
#include <sys/sysctl.h>
#include <sys/types.h>

#include <net/if.h>
#include <net/if_var.h>
#include <net/if_mib.h>
#include <net/if_types.h>
#include <net/if_dl.h>
#include <net/route.h>
#include <netinet/in.h>
#include <netinet/if_ether.h>
#include <arpa/inet.h>
#include <netdb.h>

#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <paths.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sysexits.h>
#include <unistd.h>
#include <ifaddrs.h>

void usage(void);
int add_xresolve_route(char *ifname, struct sockaddr_in *sin, int bits);
int inet_cidr_aton(char *s, struct in_addr *pin, int *bits);
int get_if_index(char *ifname);
int create_if(char *ifname);
int destroy_if(char *ifname);
int if2sockaddr(char *ifname, struct sockaddr_dl *sdl);
int handle_rtmsg(struct rt_msghdr *rtm, int msglen);
int handle_rtmsg_resolve(struct rt_msghdr *rtm, int msglen);
int reply_rtmsg_resolve(struct sockaddr_in *sin);

/*
 * We check for the existence of _IFNAME.
 */
#if 1
#define _IFNAME "disc0"
#else
#define _IFNAME "lo0"
#endif

int rtsock;

int
main(int argc, char *argv[])
{
	int n;
	int bits;
	char msg[2048];
	struct sockaddr_in sin;

	if (geteuid() != 0)
		errx(1, "must be root to alter routing table");

	memset(&sin, 0, sizeof(sin));
	sin.sin_family = AF_INET;
	sin.sin_len = sizeof(sin);

	/* Parse network argument */
	if ((argc != 2)
	    || (inet_cidr_aton(argv[1], &sin.sin_addr, &bits) != 1))
		usage();

	/* Open routing socket */
	rtsock = socket(PF_ROUTE, SOCK_RAW, 0);
	if (rtsock == -1)
		err(EX_OSERR, "socket");

	/* Check that the target interface exists; create it if it doesn't. */
	if (get_if_index(_IFNAME) == -1) {
		warnx("interface %s does not exist, creating.", _IFNAME);

		create_if(_IFNAME);
		add_xresolve_route(_IFNAME, &sin, bits);
	}

	/* Routing event loop */
	for (;;) {
		n = read(rtsock, msg, sizeof(msg));
		handle_rtmsg((struct rt_msghdr *)msg, n);
	}

	if (rtsock != -1)
		close(rtsock);

	exit (EXIT_SUCCESS);
}

void
usage(void)
{
	fprintf(stderr, "usage: rtmhack <testnet>\n"
		"<testnet> specifies the test network in CIDR notation\n");
	exit(EXIT_FAILURE);
}

/*
 * Like inet_aton(), but handle an optional CIDR prefix.
 */
int
inet_cidr_aton(char *s, struct in_addr *pin, int *bits)
{
	char *q;

	q = NULL;
	*bits = 32;

	if ((q = strchr(s, '/')) != NULL) {
		*bits = strtoul(q+1, 0, 0);
		*q = '\0';
	}

	return (inet_aton(s, pin));
}

/*
 * Return the index of a named interface in the MIB, or -1 if it does
 * not exist.
 */
int
get_if_index(char *ifname)
{
	int name[6];
	int i;
	size_t len;
	int maxifno;
	int indx;
	struct ifmibdata ifmd;
	int ifnamelen;

	ifnamelen = strlen(ifname);
	indx = -1;

	name[0] = CTL_NET;
	name[1] = PF_LINK;
	name[2] = NETLINK_GENERIC;
	name[3] = IFMIB_SYSTEM;
	name[4] = IFMIB_IFCOUNT;
	len = sizeof(maxifno);
	if (sysctl(name, 5, &maxifno, &len, 0, 0) < 0)
		err(1, "sysctl net.link.generic.system.ifcount");

	name[3] = IFMIB_IFDATA;
	name[5] = IFDATA_GENERAL;
	len = sizeof(ifmd);
	for (i = 1; i <= maxifno; i++) {
		name[4] = i;
		if (sysctl(name, 6, &ifmd, &len, 0, 0) < 0) {
			if (errno == ENOENT)
				continue;
			err(1, "sysctl");
		}
		if (strncmp(ifname, ifmd.ifmd_name, ifnamelen) == 0) {
			indx = i;
			break;
		}
	}

	return (indx);
}

/*
 * create an instance of a named clonable interface.
 * Return 0 if successful, or -1 if an error occurred.
 */
int
create_if(char *ifname)
{
	int s, retval;
	struct ifreq ifr;

	retval = 0;

	s = socket(AF_INET, SOCK_DGRAM, 0);
	if (s == -1)
		err(1, "socket");

	memset(&ifr, 0, sizeof(ifr));
	(void) strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name));
	if (ioctl(s, SIOCIFCREATE, &ifr) < 0) {
		retval = -1;
		warn("SIOCIFCREATE");
	}

	close(s);
	return (retval);
}

/*
 * destroy an instance of a named clonable interface.
 * Return 0 if successful, or -1 if an error occurred.
 */
int
destroy_if(char *ifname)
{
	int s, retval;
	struct ifreq ifr;

	retval = 0;

	s = socket(AF_INET, SOCK_DGRAM, 0);
	if (s == -1)
		err(1, "socket");

	memset(&ifr, 0, sizeof(ifr));
	(void) strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name));
	if (ioctl(s, SIOCIFDESTROY, &ifr) < 0) {
		retval = -1;
		warn("SIOCIFDESTROY");
	}

	close(s);
	return (retval);
}

/*
 * Copy the sockaddr_dl structure corresponding to the named interface
 * into the structure pointed to by sdl.
 * Returns 0 if successful, or -1 if the structure found was not valid.
 */
int
if2sockaddr(char *ifname, struct sockaddr_dl *sdl)
{
	struct ifaddrs *ifap, *ifa;
	struct sockaddr_dl *isdl;

	if (getifaddrs(&ifap))
		err(1, "getifaddrs");

	isdl = NULL;

	for (ifa = ifap; ifa; ifa = ifa->ifa_next) {
		if (ifa->ifa_addr->sa_family != AF_LINK)
			continue;

		if (strcmp(ifname, ifa->ifa_name))
			continue;

		isdl = (struct sockaddr_dl *)ifa->ifa_addr;
	}

	if (sdl)
		memcpy(sdl, isdl, isdl->sdl_len);

	return ((isdl != NULL) ? 0 : -1);
}

/*
 * Bind an cloning XRESOLVE route, for the given network/host,
 * to a named interface.
 * Return 0 if successful, or -1 if an error occurred.
 *
 * XXX there is a glaring bug here - the netmask is not set correctly
 * when adding the route. what could be the problem? this is a real mess.
 */
int
add_xresolve_route(char *ifname, struct sockaddr_in *sin, int bits)
{
	int len;
	struct {
		struct rt_msghdr rtm;
		struct sockaddr addrs[RTAX_MAX];
	} r;
	char *cp;
	int l;
	struct sockaddr_dl sdl;
	struct sockaddr_in sin_mask;
	unsigned long mask;

#define ROUNDUP(a) \
	((a) > 0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
#define ADVANCE(x, n) (x += ROUNDUP((n)->sa_len))
#define NEXTADDR(rtm, w, u) \
	if (rtm.rtm_addrs & (w)) {\
		l = ROUNDUP(u.sa.sa_len); memmove(cp, &(u), l); cp += l;\
	}

	/*
	RTM_ADD: Add Route: len 172, pid: 31485, seq 1, errno 0
	flags:<UP,DONE,STATIC>
	locks:
	inits:
	sockaddrs: <DST,GATEWAY,NETMASK>
	 1.0.0.0 disc0 (0) 0 ff
	*/

	cp = (char *) &r.addrs[0];

	memset(&r, 0, sizeof(r));
	r.rtm.rtm_version = RTM_VERSION;
	r.rtm.rtm_type = RTM_ADD;
	r.rtm.rtm_msglen = sizeof(r);
	r.rtm.rtm_pid = getpid();
	r.rtm.rtm_seq = 0;
	r.rtm.rtm_flags = RTF_XRESOLVE | RTF_CLONING | RTF_UP;
	r.rtm.rtm_addrs = RTA_DST | RTA_GATEWAY | RTA_NETMASK;

	if2sockaddr(ifname, &sdl);

	memmove(&r.addrs[RTAX_DST], sin, sin->sin_len);
	memmove(&r.addrs[RTAX_GATEWAY], &sdl, sdl.sdl_len);
#if 0
	NEXTADDR(RTA_DST, sin);
	NEXTADDR(RTA_GATEWAY, sdl);
	NEXTADDR(RTA_NETMASK, sin_mask);
#endif

	memset(&sin_mask, 0x0, sizeof(sin_mask));
	mask = 0xffffffff << (32 - bits);
	sin_mask.sin_addr.s_addr = htonl(mask);

	cp = (char *)(&sin_mask.sin_addr + 1);
	while (*--cp == 0 && cp > (char *)&sin_mask)
		;
	sin->sin_len = 1 + cp - (char *)&sin_mask;

	fprintf(stderr, "sin_len %d\n", sin_mask.sin_len);
	fprintf(stderr, "sin_family %d\n", sin_mask.sin_family);
	fprintf(stderr, "sin_port %d\n", sin_mask.sin_port);
	fprintf(stderr, "sin_addr %s\n", inet_ntoa(sin_mask.sin_addr));

	memmove(&r.addrs[RTAX_NETMASK], &sin_mask, sin_mask.sin_len);

	len = write(rtsock, &r, r.rtm.rtm_msglen);
	if (len != r.rtm.rtm_msglen)
		warn("write");

	return ((len > 0) ? 0 : -1);
#undef NEXTADDR
#undef ADVANCE
#undef ROUNDUP
}

/*
 * routing socket message dispatcher
 */
int
handle_rtmsg(struct rt_msghdr *rtm, int msglen)
{
	if (rtm->rtm_version != RTM_VERSION) {
		(void) printf("bad routing message version %d\n",
			rtm->rtm_version);
		return (-1);
	}

	switch (rtm->rtm_type) {
	case RTM_RESOLVE:
		(void) printf("rtm_type %d: RTM_RESOLVE\n", rtm->rtm_type);
		handle_rtmsg_resolve(rtm, msglen);
		break;
	default:
		(void) printf("rtm_type %d: ignored\n", rtm->rtm_type);
	}

	return (0);
}

/*
 * Dispatch routine for RTM_RESOLVE routing messages.
 * Return 0 if successful; otherwise, return -1 if an error occurred.
 */
int
handle_rtmsg_resolve(struct rt_msghdr *rtm, int msglen)
{
	void *sp;
	struct sockaddr *sa;
	struct sockaddr_in *sin;

	/*
	 * ignore messages from ourselves
	 */
	if (rtm->rtm_pid == getpid()) {
		printf("heard own message, ignoring\n");
		return (0);
	}

	printf("rtm_index: %04x rtm_addrs: %08x\n",
		rtm->rtm_index, rtm->rtm_addrs);

	/*
	 * The message must contain the address for which a route is
	 * being requested, otherwise it is invalid.
	 */
	if (!(rtm->rtm_addrs & RTA_DST)) {
		warnx("RTM_RESOLVE message does not contain destination");
		return (-1);
	}

	sa = sp = (rtm + 1);
	if (sa->sa_family != AF_INET) {
		warnx("RTM_RESOLVE contains non-AF_INET destination %d",
			sa->sa_family);
		return (-1);
	}
	sin = (struct sockaddr_in *)sa;
	printf("route requested for %s\n", inet_ntoa(sin->sin_addr));

	/*
	 * XXX: Should check if the requested destination is within the
	 * network prefix specified on the command line.
	 */
	reply_rtmsg_resolve(sin);
	printf("route resolved for %s\n", inet_ntoa(sin->sin_addr));

	return (0);
}

/*
 * Modify a given route in response to an RTM_RESOLVE message from the kernel.
 * Return 0 if successful; otherwise, return -1.
 */
int
reply_rtmsg_resolve(struct sockaddr_in *sin)
{
	int len;
	struct {
		struct rt_msghdr rtm;
		struct sockaddr addrs[RTAX_MAX];
	} r;
	struct sockaddr_dl sdl;

	memset(&r, 0, sizeof(r));
	r.rtm.rtm_version = RTM_VERSION;
	r.rtm.rtm_type = RTM_CHANGE;
	r.rtm.rtm_pid = getpid();
	r.rtm.rtm_seq = 0;

	if2sockaddr("lo0", &sdl);
	memcpy(&r.addrs[RTAX_DST], sin, sin->sin_len);
	memcpy(&r.addrs[RTAX_GATEWAY], &sdl, sdl.sdl_len);
	memset(&r.addrs[RTAX_IFP], 0, sizeof(r.addrs[RTAX_IFP]));
	memset(&r.addrs[RTAX_IFA], 0, sizeof(r.addrs[RTAX_IFA]));
	r.rtm.rtm_addrs = RTA_DST | RTA_GATEWAY | RTA_IFP | RTA_IFA;

	r.rtm.rtm_flags = RTF_DONE;
	r.rtm.rtm_msglen = sizeof(r);

	len = write(rtsock, &r, r.rtm.rtm_msglen);
	if (len != r.rtm.rtm_msglen)
		warn("write");

	return ((len > 0) ? 0 : -1);
}