From efb2dfa1774240830b3f74b7fe4ab8050cc1cda0 Mon Sep 17 00:00:00 2001
From: harti <harti@FreeBSD.org>
Date: Tue, 4 Oct 2005 14:41:06 +0000
Subject: Virgin import of bsnmpd 1.11

---
 contrib/bsnmp/snmp_mibII/mibII_route.c | 428 ++++++++++++++++++++++++---------
 1 file changed, 321 insertions(+), 107 deletions(-)

(limited to 'contrib/bsnmp/snmp_mibII/mibII_route.c')

diff --git a/contrib/bsnmp/snmp_mibII/mibII_route.c b/contrib/bsnmp/snmp_mibII/mibII_route.c
index 9375be3..feb33c9 100644
--- a/contrib/bsnmp/snmp_mibII/mibII_route.c
+++ b/contrib/bsnmp/snmp_mibII/mibII_route.c
@@ -26,41 +26,218 @@
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  *
- * $Begemot: bsnmp/snmp_mibII/mibII_route.c,v 1.6 2005/05/23 09:03:41 brandt_h Exp $
+ * $Begemot: bsnmp/snmp_mibII/mibII_route.c,v 1.7 2005/06/09 12:36:53 brandt_h Exp $
  *
  * Routing table
  */
+#include <sys/tree.h>
 #include "mibII.h"
 #include "mibII_oid.h"
 
 struct sroute {
-	TAILQ_ENTRY(sroute) link;
-	struct asn_oid	index;
-	u_int		ifindex;
-	u_int		type;
-	u_int		proto;
+	RB_ENTRY(sroute) link;
+	uint32_t	ifindex;
+	uint8_t		index[13];
+	uint8_t		type;
+	uint8_t		proto;
 };
-static TAILQ_HEAD(, sroute) sroute_list = TAILQ_HEAD_INITIALIZER(sroute_list);
+RB_HEAD(sroutes, sroute) sroutes = RB_INITIALIZER(&sroutes);
 
+RB_PROTOTYPE(sroutes, sroute, link, sroute_compare);
+
+#define	ROUTE_UPDATE_INTERVAL	(100 * 60 * 10)	/* 10 min */
 static uint64_t route_tick;
 static u_int route_total;
 
+/*
+ * Compare two routes
+ */
 static int
-fetch_route(void)
+sroute_compare(struct sroute *s1, struct sroute *s2)
+{
+
+	return (memcmp(s1->index, s2->index, 13));
+}
+
+static void
+sroute_index_append(struct asn_oid *oid, u_int sub, const struct sroute *s)
+{
+	int i;
+
+	oid->len = sub + 13;
+	for (i = 0; i < 13; i++)
+		oid->subs[sub + i] = s->index[i];
+}
+
+#if 0
+static void
+sroute_print(const struct sroute *r)
+{
+	u_int i;
+
+	for (i = 0; i < 13 - 1; i++)
+		printf("%u.", r->index[i]);
+	printf("%u proto=%u type=%u", r->index[i], r->proto, r->type);
+}
+#endif
+
+/*
+ * process routing message
+ */
+void
+mib_sroute_process(struct rt_msghdr *rtm, struct sockaddr *gw,
+    struct sockaddr *dst, struct sockaddr *mask)
+{
+	struct sockaddr_in *in_dst, *in_gw;
+	struct in_addr in_mask;
+	struct mibif *ifp;
+	struct sroute key;
+	struct sroute *r, *r1;
+	in_addr_t ha;
+
+	if (dst == NULL || gw == NULL || dst->sa_family != AF_INET ||
+	    gw->sa_family != AF_INET)
+		return;
+
+	in_dst = (struct sockaddr_in *)(void *)dst;
+	in_gw = (struct sockaddr_in *)(void *)gw;
+
+	if (rtm->rtm_flags & RTF_HOST)
+		in_mask.s_addr = 0xffffffff;
+	else if (mask == NULL || mask->sa_len == 0)
+		in_mask.s_addr = 0;
+	else
+		in_mask = ((struct sockaddr_in *)(void *)mask)->sin_addr;
+
+	/* build the index */
+	ha = ntohl(in_dst->sin_addr.s_addr);
+	key.index[0] = (ha >> 24) & 0xff;
+	key.index[1] = (ha >> 16) & 0xff;
+	key.index[2] = (ha >>  8) & 0xff;
+	key.index[3] = (ha >>  0) & 0xff;
+
+	ha = ntohl(in_mask.s_addr);
+	key.index[4] = (ha >> 24) & 0xff;
+	key.index[5] = (ha >> 16) & 0xff;
+	key.index[6] = (ha >>  8) & 0xff;
+	key.index[7] = (ha >>  0) & 0xff;
+
+	/* ToS */
+	key.index[8] = 0;
+
+	ha = ntohl(in_gw->sin_addr.s_addr);
+	key.index[9] = (ha >> 24) & 0xff;
+	key.index[10] = (ha >> 16) & 0xff;
+	key.index[11] = (ha >>  8) & 0xff;
+	key.index[12] = (ha >>  0) & 0xff;
+
+	if (rtm->rtm_type == RTM_DELETE) {
+		r = RB_FIND(sroutes, &sroutes, &key);
+		if (r == 0) {
+#ifdef DEBUG_ROUTE
+			syslog(LOG_WARNING, "%s: DELETE: %u.%u.%u.%u "
+			    "%u.%u.%u.%u %u %u.%u.%u.%u not found", __func__,
+			    key.index[0], key.index[1], key.index[2],
+			    key.index[3], key.index[4], key.index[5],
+			    key.index[6], key.index[7], key.index[8],
+			    key.index[9], key.index[10], key.index[11],
+			    key.index[12]);
+#endif
+			return;
+		}
+		RB_REMOVE(sroutes, &sroutes, r);
+		free(r);
+		route_total--;
+#ifdef DEBUG_ROUTE
+		printf("%s: DELETE: %u.%u.%u.%u "
+		    "%u.%u.%u.%u %u %u.%u.%u.%u\n", __func__,
+		    key.index[0], key.index[1], key.index[2],
+		    key.index[3], key.index[4], key.index[5],
+		    key.index[6], key.index[7], key.index[8],
+		    key.index[9], key.index[10], key.index[11],
+		    key.index[12]);
+#endif
+		return;
+	}
+
+	/* GET or ADD */
+	ifp = NULL;
+	if ((ifp = mib_find_if_sys(rtm->rtm_index)) == NULL) {
+		if (rtm->rtm_type == RTM_ADD) {
+			/* make it a get so the kernel fills the index */
+			mib_send_rtmsg(rtm, gw, dst, mask);
+			return;
+		}
+		mib_iflist_bad = 1;
+	}
+
+	if ((r = malloc(sizeof(*r))) == NULL) {
+		syslog(LOG_ERR, "%m");
+		return;
+	}
+
+	memcpy(r->index, key.index, sizeof(r->index));
+	r->ifindex = (ifp == NULL) ? 0 : ifp->index;
+
+	r->type = (rtm->rtm_flags & RTF_LLINFO) ? 3 :
+	    (rtm->rtm_flags & RTF_REJECT) ? 2 : 4;
+
+	/* cannot really know, what protocol it runs */
+	r->proto = (rtm->rtm_flags & RTF_LOCAL) ? 2 :
+	    (rtm->rtm_flags & RTF_STATIC) ? 3 :
+	    (rtm->rtm_flags & RTF_DYNAMIC) ? 4 : 10;
+
+	r1 = RB_INSERT(sroutes, &sroutes, r);
+	if (r1 != NULL) {
+#ifdef DEBUG_ROUTE
+		syslog(LOG_WARNING, "%s: %u.%u.%u.%u "
+		    "%u.%u.%u.%u %u %u.%u.%u.%u duplicate route", __func__,
+		    key.index[0], key.index[1], key.index[2],
+		    key.index[3], key.index[4], key.index[5],
+		    key.index[6], key.index[7], key.index[8],
+		    key.index[9], key.index[10], key.index[11],
+		    key.index[12]);
+#endif
+		r1->ifindex = r->ifindex;
+		r1->type = r->type;
+		r1->proto = r->proto;
+		free(r);
+		return;
+	}
+
+	route_total++;
+#ifdef DEBUG_ROUTE
+	printf("%s: ADD/GET: %u.%u.%u.%u "
+	    "%u.%u.%u.%u %u %u.%u.%u.%u\n", __func__,
+	    key.index[0], key.index[1], key.index[2],
+	    key.index[3], key.index[4], key.index[5],
+	    key.index[6], key.index[7], key.index[8],
+	    key.index[9], key.index[10], key.index[11],
+	    key.index[12]);
+#endif
+}
+
+int
+mib_fetch_route(void)
 {
 	u_char *rtab, *next;
 	size_t len;
-	struct sroute *r;
+	struct sroute *r, *r1;
 	struct rt_msghdr *rtm;
 	struct sockaddr *addrs[RTAX_MAX];
-	struct sockaddr_in *sa, *gw;
-	struct in_addr mask, nhop;
-	in_addr_t ha;
-	struct mibif *ifp;
 
-	while ((r = TAILQ_FIRST(&sroute_list)) != NULL) {
-		TAILQ_REMOVE(&sroute_list, r, link);
+	if (route_tick != 0 && route_tick + ROUTE_UPDATE_INTERVAL > this_tick)
+		return (0);
+
+	/*
+	 * Remove all routes
+	 */
+	r = RB_MIN(sroutes, &sroutes);
+	while (r != NULL) {
+		r1 = RB_NEXT(sroutes, &sroutes, r);
+		RB_REMOVE(sroutes, &sroutes, r);
 		free(r);
+		r = r1;
 	}
 	route_total = 0;
 
@@ -75,81 +252,118 @@ fetch_route(void)
 			continue;
 		mib_extract_addrs(rtm->rtm_addrs, (u_char *)(rtm + 1), addrs);
 
-		if (addrs[RTAX_DST] == NULL || addrs[RTAX_GATEWAY] == NULL ||
-		    addrs[RTAX_DST]->sa_family != AF_INET)
-			continue;
-
-		sa = (struct sockaddr_in *)(void *)addrs[RTAX_DST];
-
-		if (rtm->rtm_flags & RTF_HOST) {
-			mask.s_addr = 0xffffffff;
-		} else {
-			if (addrs[RTAX_NETMASK] == NULL ||
-			    addrs[RTAX_NETMASK]->sa_len == 0)
-				mask.s_addr = 0;
-			else
-				mask = ((struct sockaddr_in *)(void *)
-				    addrs[RTAX_NETMASK])->sin_addr;
-		}
-		if (addrs[RTAX_GATEWAY] == NULL) {
-			nhop.s_addr = 0;
-		} else if (rtm->rtm_flags & RTF_LLINFO) {
-			nhop = sa->sin_addr;
-		} else {
-			gw = (struct sockaddr_in *)(void *)addrs[RTAX_GATEWAY];
-			if (gw->sin_family != AF_INET)
-				continue;
-			nhop = gw->sin_addr;
-		}
-		if ((ifp = mib_find_if_sys(rtm->rtm_index)) == NULL) {
-			mib_iflist_bad = 1;
-			continue;
-		}
-
-		if ((r = malloc(sizeof(*r))) == NULL) {
-			syslog(LOG_ERR, "%m");
-			continue;
-		}
-
-		route_total++;
+		
+		mib_sroute_process(rtm, addrs[RTAX_GATEWAY], addrs[RTAX_DST],
+		    addrs[RTAX_NETMASK]);
+	}
 
-		r->index.len = 13;
-		ha = ntohl(sa->sin_addr.s_addr);
-		r->index.subs[0] = (ha >> 24) & 0xff;
-		r->index.subs[1] = (ha >> 16) & 0xff;
-		r->index.subs[2] = (ha >>  8) & 0xff;
-		r->index.subs[3] = (ha >>  0) & 0xff;
-		ha = ntohl(mask.s_addr);
-		r->index.subs[4] = (ha >> 24) & 0xff;
-		r->index.subs[5] = (ha >> 16) & 0xff;
-		r->index.subs[6] = (ha >>  8) & 0xff;
-		r->index.subs[7] = (ha >>  0) & 0xff;
+#if 0
+	u_int n = 0;
+	r = RB_MIN(sroutes, &sroutes);
+	while (r != NULL) {
+		printf("%u: ", n++);
+		sroute_print(r);
+		printf("\n");
+		r = RB_NEXT(sroutes, &sroutes, r);
+	}
+#endif
+	free(rtab);
+	route_tick = get_ticks();
 
-		r->index.subs[8] = 0;
+	return (0);
+}
 
-		ha = ntohl(nhop.s_addr);
-		r->index.subs[9] = (ha >> 24) & 0xff;
-		r->index.subs[10] = (ha >> 16) & 0xff;
-		r->index.subs[11] = (ha >>  8) & 0xff;
-		r->index.subs[12] = (ha >>  0) & 0xff;
+/**
+ * Find a route in the table.
+ */
+static struct sroute *
+sroute_get(const struct asn_oid *oid, u_int sub)
+{
+	struct sroute key;
+	int i;
+
+	if (oid->len - sub != 13)
+		return (NULL);
+	for (i = 0; i < 13; i++)
+		key.index[i] = oid->subs[sub + i];
+	return (RB_FIND(sroutes, &sroutes, &key));
+}
 
-		r->ifindex = ifp->index;
+/**
+ * Find next route in the table. There is no such RB_ macro, so must
+ * dig into the innards of the RB stuff.
+ */
+static struct sroute *
+sroute_getnext(struct asn_oid *oid, u_int sub)
+{
+	u_int i;
+	int comp;
+	struct sroute key;
+	struct sroute *best;
+	struct sroute *s;
+
+	/*
+	 * We now, that the OID is at least the tableEntry OID. If it is,
+	 * the user wants the first route.
+	 */
+	if (oid->len == sub)
+		return (RB_MIN(sroutes, &sroutes));
+
+	/*
+	 * This is also true for any index that consists of zeros and is
+	 * shorter than the full index.
+	 */
+	if (oid->len < sub + 13) {
+		for (i = sub; i < oid->len; i++)
+			if (oid->subs[i] != 0)
+				break;
+		if (i == oid->len)
+			return (RB_MIN(sroutes, &sroutes));
+
+		/*
+		 * Now if the index is too short, we fill it with zeros and then
+		 * subtract one from the index. We can do this, because we now,
+		 * that there is at least one index element that is not zero.
+		 */
+		for (i = oid->len; i < sub + 13; i++)
+			oid->subs[i] = 0;
+
+		for (i = sub + 13 - 1; i >= sub; i--) {
+			if (oid->subs[i] != 0) {
+				oid->subs[i]--;
+				break;
+			}
+			oid->subs[i] = ASN_MAXID;
+		}
+		oid->len = sub + 13;
+	}
 
-		r->type = (rtm->rtm_flags & RTF_LLINFO) ? 3 :
-		    (rtm->rtm_flags & RTF_REJECT) ? 2 : 4;
+	/* build the index */
+	for (i = sub; i < sub + 13; i++)
+		key.index[i - sub] = oid->subs[i];
 
-		/* cannot really know, what protocol it runs */
-		r->proto = (rtm->rtm_flags & RTF_LOCAL) ? 2 :
-		    (rtm->rtm_flags & RTF_STATIC) ? 3 :
-		    (rtm->rtm_flags & RTF_DYNAMIC) ? 4 : 10;
+	/* now find the element */
+	best = NULL;
+	s = RB_ROOT(&sroutes);
 
-		INSERT_OBJECT_OID(r, &sroute_list);
+	while (s != NULL) {
+		comp = sroute_compare(&key, s);
+		if (comp >= 0) {
+			/* The current element is smaller than what we search.
+			 * Forget about it and move to the right subtree. */
+			s = RB_RIGHT(s, link);
+			continue;
+		}
+		/* the current element is larger than what we search.
+		 * forget about the right subtree (its even larger), but
+		 * the current element may be what we need. */
+		if (best == NULL || sroute_compare(s, best) < 0)
+			/* this one's better */
+			best = s;
+
+		s = RB_LEFT(s, link);
 	}
-
-	free(rtab);
-	route_tick = get_ticks();
-
-	return (0);
+	return (best);
 }
 
 /*
@@ -159,28 +373,27 @@ int
 op_route_table(struct snmp_context *ctx __unused, struct snmp_value *value,
     u_int sub, u_int iidx __unused, enum snmp_op op)
 {
-	static struct sroute *r;
+	struct sroute *r;
 
-	if (route_tick < this_tick)
-		if (fetch_route() == -1)
-			return (SNMP_ERR_GENERR);
+	if (mib_fetch_route() == -1)
+		return (SNMP_ERR_GENERR);
 
 	switch (op) {
 
 	  case SNMP_OP_GETNEXT:
-		if ((r = NEXT_OBJECT_OID(&sroute_list, &value->var, sub)) == NULL)
+		if ((r = sroute_getnext(&value->var, sub)) == NULL)
 			return (SNMP_ERR_NOSUCHNAME);
-		index_append(&value->var, sub, &r->index);
+		sroute_index_append(&value->var, sub, r);
 		break;
 
 	  case SNMP_OP_GET:
-		if ((r = FIND_OBJECT_OID(&sroute_list, &value->var, sub)) == NULL)
+		if ((r = sroute_get(&value->var, sub)) == NULL)
 			return (SNMP_ERR_NOSUCHNAME);
 		break;
 
 	  case SNMP_OP_SET:
-		if ((r = FIND_OBJECT_OID(&sroute_list, &value->var, sub)) == NULL)
-			return (SNMP_ERR_NO_CREATION);
+		if ((r = sroute_get(&value->var, sub)) == NULL)
+			return (SNMP_ERR_NOSUCHNAME);
 		return (SNMP_ERR_NOT_WRITEABLE);
 
 	  case SNMP_OP_ROLLBACK:
@@ -194,28 +407,28 @@ op_route_table(struct snmp_context *ctx __unused, struct snmp_value *value,
 	switch (value->var.subs[sub - 1]) {
 
 	  case LEAF_ipCidrRouteDest:
-		value->v.ipaddress[0] = r->index.subs[0];
-		value->v.ipaddress[1] = r->index.subs[1];
-		value->v.ipaddress[2] = r->index.subs[2];
-		value->v.ipaddress[3] = r->index.subs[3];
+		value->v.ipaddress[0] = r->index[0];
+		value->v.ipaddress[1] = r->index[1];
+		value->v.ipaddress[2] = r->index[2];
+		value->v.ipaddress[3] = r->index[3];
 		break;
 
 	  case LEAF_ipCidrRouteMask:
-		value->v.ipaddress[0] = r->index.subs[4];
-		value->v.ipaddress[1] = r->index.subs[5];
-		value->v.ipaddress[2] = r->index.subs[6];
-		value->v.ipaddress[3] = r->index.subs[7];
+		value->v.ipaddress[0] = r->index[4];
+		value->v.ipaddress[1] = r->index[5];
+		value->v.ipaddress[2] = r->index[6];
+		value->v.ipaddress[3] = r->index[7];
 		break;
 
 	  case LEAF_ipCidrRouteTos:
-		value->v.integer = r->index.subs[8];
+		value->v.integer = r->index[8];
 		break;
 
 	  case LEAF_ipCidrRouteNextHop:
-		value->v.ipaddress[0] = r->index.subs[9];
-		value->v.ipaddress[1] = r->index.subs[10];
-		value->v.ipaddress[2] = r->index.subs[11];
-		value->v.ipaddress[3] = r->index.subs[12];
+		value->v.ipaddress[0] = r->index[9];
+		value->v.ipaddress[1] = r->index[10];
+		value->v.ipaddress[2] = r->index[11];
+		value->v.ipaddress[3] = r->index[12];
 		break;
 
 	  case LEAF_ipCidrRouteIfIndex:
@@ -280,9 +493,8 @@ op_route(struct snmp_context *ctx __unused, struct snmp_value *value,
 		abort();
 	}
 
-	if (route_tick < this_tick)
-		if (fetch_route() == -1)
-			return (SNMP_ERR_GENERR);
+	if (mib_fetch_route() == -1)
+		return (SNMP_ERR_GENERR);
 
 	switch (value->var.subs[sub - 1]) {
 
@@ -293,3 +505,5 @@ op_route(struct snmp_context *ctx __unused, struct snmp_value *value,
 	}
 	return (SNMP_ERR_NOERROR);
 }
+
+RB_GENERATE(sroutes, sroute, link, sroute_compare);
-- 
cgit v1.1