X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/35e117b36c6238dfc1d43512e60547c70f0f37c8..67336957bf4ba9077e903c3d9fe3d098cac1602b:/usr/src/sys/net/radix.c

diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c
index 12ea6bb02b..b4b5d9e343 100644
--- a/usr/src/sys/net/radix.c
+++ b/usr/src/sys/net/radix.c
@@ -1,32 +1,27 @@
 /*
- * Copyright (c) 1982, 1988 Regents of the University of California.
+ * Copyright (c) 1988, 1989  Regents of the University of California.
  * All rights reserved.
  *
- * Redistribution and use in source and binary forms are permitted
- * provided that the above copyright notice and this paragraph are
- * duplicated in all such forms and that any documentation,
- * advertising materials, and other materials related to such
- * distribution and use acknowledge that the software was developed
- * by the University of California, Berkeley.  The name of the
- * University may not be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * %sccs.include.redist.c%
  *
- *	@(#)radix.c	7.1 (Berkeley) %G%
+ *	@(#)radix.c	7.7 (Berkeley) %G%
  */
 
 /*
  * Routines to build and maintain radix trees for routing lookups.
  */
 #ifndef RNF_NORMAL
-typedef unsigned char u_char;
+#include "param.h"
 #include "radix.h"
+#include "malloc.h"
+#define	M_DONTWAIT M_NOWAIT
 #endif
-struct radix_node_head *radix_node_head;
+struct radix_node_head *mask_rnhead;
+#define rn_maskhead mask_rnhead->rnh_treetop
 struct radix_mask *rn_mkfreelist;
-#define rn_maskhead radix_node_head->rnh_treetop
+struct radix_node_head *radix_node_head;
+#undef Bcmp
+#define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
 /*
  * The data structure for the keys is a radix tree with one way
  * branching removed.  The index rn_b at an internal node n represents a bit
@@ -60,7 +55,7 @@ struct radix_mask *rn_mkfreelist;
 struct radix_node *
 rn_search(v, head)
 	struct radix_node *head;
-	register char *v;
+	register caddr_t v;
 {
 	register struct radix_node *x;
 
@@ -73,6 +68,23 @@ rn_search(v, head)
 	return x;
 };
 
+struct radix_node *
+rn_search_m(v, head, m)
+	struct radix_node *head;
+	register caddr_t v, m;
+{
+	register struct radix_node *x;
+
+	for (x = head; x->rn_b >= 0;) {
+		if ((x->rn_bmask & m[x->rn_off]) &&
+		    (x->rn_bmask & v[x->rn_off]))
+			x = x->rn_r;
+		else
+			x = x->rn_l;
+	}
+	return x;
+};
+
 
 static int gotOddMasks;
 static char maskedKey[MAXKEYLEN];
@@ -80,13 +92,13 @@ static char maskedKey[MAXKEYLEN];
 struct radix_node *
 rn_match(v, head)
 	struct radix_node *head;
-	char *v;
+	caddr_t v;
 {
 	register struct radix_node *t = head, *x;
-	register char *cp = v, *cp2, *cp3;
-	char *cplim, *mstart;
+	register caddr_t cp = v, cp2, cp3;
+	caddr_t cplim, mstart;
 	struct radix_node *saved_t;
-	int off = t->rn_off, vlen = *(u_char *)cp, head_off, matched_off;
+	int off = t->rn_off, vlen = *(u_char *)cp, matched_off;
 
 	/*
 	 * Open code rn_search(v, head) to avoid overhead of extra
@@ -105,6 +117,12 @@ rn_match(v, head)
 	for (; cp < cplim; cp++, cp2++)
 		if (*cp != *cp2)
 			goto on1;
+	/*
+	 * This extra grot is in case we are explicitly asked
+	 * to look up the default.  Ugh!
+	 */
+	if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
+		t = t->rn_dupedkey;
 	return t;
 on1:
 	matched_off = cp - v;
@@ -117,11 +135,13 @@ on1:
 		 * a route to a net.
 		 */
 		cp3 = matched_off + t->rn_mask;
+		cp2 = matched_off + t->rn_key;
 		for (; cp < cplim; cp++)
 			if ((*cp2++ ^ *cp) & *cp3++)
 				break;
 		if (cp == cplim)
 			return t;
+		cp = matched_off + v;
 	    }
 	} while (t = t->rn_dupedkey);
 	t = saved_t;
@@ -130,6 +150,12 @@ on1:
 		register struct radix_mask *m;
 		t = t->rn_p;
 		if (m = t->rn_mklist) {
+			/*
+			 * After doing measurements here, it may
+			 * turn out to be faster to open code
+			 * rn_search_m here instead of always
+			 * copying and masking.
+			 */
 			off = min(t->rn_off, matched_off);
 			mstart = maskedKey + off;
 			do {
@@ -158,7 +184,7 @@ int	rn_saveinfo;
 
 struct radix_node *
 rn_newpair(v, b, nodes)
-	char *v;
+	caddr_t v;
 	struct radix_node nodes[2];
 {
 	register struct radix_node *tt = nodes, *t = tt + 1;
@@ -176,23 +202,23 @@ rn_newpair(v, b, nodes)
 int rn_debug =  1;
 struct radix_node *
 rn_insert(v, head, dupentry, nodes)
-	char *v;
+	caddr_t v;
 	struct radix_node *head;
 	int *dupentry;
 	struct radix_node nodes[2];
 {
 	int head_off = head->rn_off, vlen = (int)*((u_char *)v);
 	register struct radix_node *t = rn_search(v, head);
-	register char *cp = v + head_off;
+	register caddr_t cp = v + head_off;
 	register int b;
 	struct radix_node *tt;
     	/*
 	 *find first bit at which v and t->rn_key differ
 	 */
     {
-	register char *cp2 = t->rn_key + head_off;
+	register caddr_t cp2 = t->rn_key + head_off;
 	register int cmp_res;
-	char *cplim = v + vlen;
+	caddr_t cplim = v + vlen;
 
 	while (cp < cplim)
 		if (*cp2++ != *cp++)
@@ -237,18 +263,62 @@ on1:
 	return (tt);
 }
 
+struct radix_node *
+rn_addmask(netmask, search, skip)
+caddr_t netmask;
+{
+	register struct radix_node *x;
+	register caddr_t cp, cplim;
+	register int b, mlen, j;
+	int maskduplicated;
+
+	mlen = *(u_char *)netmask;
+	if (search) {
+		x = rn_search(netmask, rn_maskhead);
+		mlen = *(u_char *)netmask;
+		if (Bcmp(netmask, x->rn_key, mlen) == 0)
+			return (x);
+	}
+	R_Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x));
+	if (x == 0)
+		return (0);
+	Bzero(x, MAXKEYLEN + 2 * sizeof (*x));
+	cp = (caddr_t)(x + 2);
+	Bcopy(netmask, cp, mlen);
+	netmask = cp;
+	x = rn_insert(netmask, rn_maskhead, &maskduplicated, x);
+	/*
+	 * Calculate index of mask.
+	 */
+	cplim = netmask + mlen;
+	for (cp = netmask + skip; cp < cplim; cp++)
+		if (*(u_char *)cp != 0xff)
+			break;
+	b = (cp - netmask) << 3;
+	if (cp != cplim) {
+		if (*cp != 0) {
+			gotOddMasks = 1;
+			for (j = 0x80; j; b++, j >>= 1)  
+				if ((j & *cp) == 0)
+					break;
+		}
+	}
+	x->rn_b = -1 - b;
+	return (x);
+}
+
 struct radix_node *
 rn_addroute(v, netmask, head, treenodes)
-	struct radix_node *head;
-	char *netmask, *v;
+struct radix_node *head;
+	caddr_t netmask, v;
 	struct radix_node treenodes[2];
 {
 	register int j;
-	register char *cp;
+	register caddr_t cp;
 	register struct radix_node *t, *x, *tt;
 	short b = 0, b_leaf;
-	int vlen = *(u_char *)v, maskduplicated = 0, mlen, keyduplicated;
-	char *cplim; unsigned char *maskp;
+	int vlen = *(u_char *)v, mlen, keyduplicated;
+	caddr_t cplim; unsigned char *maskp;
 	struct radix_mask *m, **mp;
 	struct radix_node *saved_tt;
 
@@ -262,22 +332,24 @@ rn_addroute(v, netmask, head, treenodes)
 	if (netmask)  {
 		x = rn_search(netmask, rn_maskhead);
 		mlen = *(u_char *)netmask;
-		if (Bcmp(netmask, x->rn_key, mlen) == 0) {
-			maskduplicated = 1;
-			netmask = x->rn_key;
-			b = -1 - x->rn_b;
+		if (Bcmp(netmask, x->rn_key, mlen) != 0) {
+			x = rn_addmask(netmask, 0, head->rn_off);
+			if (x == 0)
+				return (0);
 		}
+		netmask = x->rn_key;
+		b = -1 - x->rn_b;
 	}
 	/*
 	 * Deal with duplicated keys: attach node to previous instance
 	 */
 	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
 	if (keyduplicated) {
-		if (tt->rn_mask == netmask)
-			return (0);
-		for (; tt->rn_dupedkey; tt = tt->rn_dupedkey)
+		do {
 			if (tt->rn_mask == netmask)
 				return (0);
+			t = tt;
+		} while (tt = tt->rn_dupedkey);
 		/*
 		 * If the mask is not duplicated, we wouldn't
 		 * find it among possible duplicate key entries
@@ -288,55 +360,23 @@ rn_addroute(v, netmask, head, treenodes)
 		 * It is an unfortunate pain having to relocate
 		 * the head of the list.
 		 */
-		tt->rn_dupedkey = treenodes;
-		tt = treenodes;
+		t->rn_dupedkey = tt = treenodes;
 #ifdef RN_DEBUG
 		t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
 		tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
 #endif
 		t = saved_tt;
-		tt->rn_key = t->rn_key;
-		tt->rn_b = t->rn_b;
+		tt->rn_key = (caddr_t) v;
+		tt->rn_b = -1;
 		tt->rn_flags = t->rn_flags & ~RNF_ROOT;
 	}
 	/*
 	 * Put mask in tree.
 	 */
-	if (netmask == 0)
-		goto on1;
-	if (maskduplicated == 0) {
-		Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x));
-		if (x == 0)
-			return (0);
-		Bzero(x, MAXKEYLEN + 2 * sizeof (*x));
-		cp = (char *)(x + 2);
-		bcopy(netmask, cp, mlen);
-		netmask = cp;
-		x = rn_insert(netmask, rn_maskhead, &maskduplicated, x);
-		/*
-		 * Calculate index of mask.
-		 */
-		cplim = netmask + vlen;
-		for (cp = netmask + head->rn_off; cp < cplim; cp++)
-			if (*(u_char *)cp != 0xff)
-				break;
-		b = (cp - netmask) << 3;
-		if (cp != cplim) {
-			if (*cp != 0) {
-				gotOddMasks = 1;
-				for (j = 0x80; j; b++, j >>= 1)  
-					if ((j & *cp) == 0)
-						break;
-			}
-		}
-		x->rn_b = -1 - b;
+	if (netmask) {
+		tt->rn_mask = netmask;
+		tt->rn_b = x->rn_b;
 	}
-	/*
-	 * Set up usual parameters
-	 */
-	tt->rn_mask = netmask;
-	tt->rn_b = x->rn_b;
-on1:
 	t = saved_tt->rn_p;
 	b_leaf = -1 - t->rn_b;
 	if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r;
@@ -348,7 +388,7 @@ on1:
 				Bzero(m, sizeof *m);
 				m->rm_b = x->rn_b;
 				m->rm_mask = x->rn_mask;
-				t->rn_mklist = m;
+				x->rn_mklist = t->rn_mklist = m;
 			}
 		}
 	} else if (x->rn_mklist) {
@@ -407,13 +447,13 @@ on2:
 
 struct radix_node *
 rn_delete(v, netmask, head)
-	char *v, *netmask;
+	caddr_t v, netmask;
 	struct radix_node *head;
 {
 	register struct radix_node *t, *p, *x = head;
 	register struct radix_node *tt = rn_search(v, x);
 	int b, head_off = x->rn_off, vlen =  * (u_char *) v;
-	struct radix_mask *m, **mp;
+	struct radix_mask *m, *saved_m, **mp;
 	struct radix_node *dupedkey, *saved_tt = tt;
 
 	if (tt == 0 ||
@@ -429,9 +469,13 @@ rn_delete(v, netmask, head)
 			if (tt == 0)
 				return (0);
 	}
-	if (tt->rn_mask == 0)
+	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
+		goto on1;
+	if (m->rm_mask != tt->rn_mask) {
+		printf("rn_delete: inconsistent annotation\n");
 		goto on1;
-	if ((m = tt->rn_mklist) && --m->rm_refs >= 0)
+	}
+	if (--m->rm_refs >= 0)
 		goto on1;
 	b = -1 - tt->rn_b;
 	t = saved_tt->rn_p;
@@ -442,15 +486,13 @@ rn_delete(v, netmask, head)
 		t = t->rn_p;
 	} while (b <= t->rn_b && x != head);
 	for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist)
-		if (m->rm_mask == tt->rn_mask)
-			break;
-	if (m) {
-		if (m->rm_refs < 0) {
+		if (m == saved_m) {
 			*mp = m->rm_mklist;
 			MKFree(m);
+			break;
 		}
-	} else
-		printf("rn_delete: couldn't find our mask\n");
+	if (m == 0)
+		printf("rn_delete: couldn't find our annotation\n");
 on1:
 	/*
 	 * Eliminate us from tree
@@ -501,7 +543,11 @@ on1:
 		} else {
 			for (m = t->rn_mklist; m;) {
 				struct radix_mask *mm = m->rm_mklist;
-				MKFree(m);
+				if (m == x->rn_mklist && (--(m->rm_refs) < 0)) {
+					x->rn_mklist = 0;
+					MKFree(m);
+				} else
+					printf("rn_delete: Orphaned mask\n");
 				m = mm;
 			}
 		}
@@ -531,17 +577,17 @@ rn_inithead(head, off, af)
 struct radix_node_head **head;
 int off;
 {
-	register struct radix_node_head *hp;
+	register struct radix_node_head *rnh;
 	register struct radix_node *t, *tt, *ttt;
 	if (*head)
 		return (1);
-	Malloc(hp, struct radix_node_head *, sizeof (*hp));
-	if (hp == 0)
+	R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
+	if (rnh == 0)
 		return (0);
-	Bzero(hp, sizeof (*hp));
-	*head = hp;
-	t = rn_newpair(rn_zeros, off, hp->rnh_nrt.nrt_nodes);
-	ttt = &(hp->rnh_upper);
+	Bzero(rnh, sizeof (*rnh));
+	*head = rnh;
+	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
+	ttt = rnh->rnh_nodes + 2;
 	t->rn_r = ttt;
 	t->rn_p = t;
 	tt = t->rn_l;
@@ -549,20 +595,21 @@ int off;
 	tt->rn_b = -1 - off;
 	*ttt = *tt;
 	ttt->rn_key = rn_ones;
-	hp->rnh_af = af;
-	hp->rnh_treetop = t;
+	rnh->rnh_af = af;
+	rnh->rnh_treetop = t;
 	if (radix_node_head == 0) {
-		char *cp = rn_ones, *cplim = rn_ones + MAXKEYLEN;
+		caddr_t cp = rn_ones, cplim = rn_ones + MAXKEYLEN;
 		while (cp < cplim)
 			*cp++ = -1;
 		if (rn_inithead(&radix_node_head, 0, 0) == 0) {
-			Free(hp);
+			Free(rnh);
 			*head = 0;
 			return (0);
 		}
+		mask_rnhead = radix_node_head;
 	}
-	hp->rnh_next = radix_node_head->rnh_next;
-	if (radix_node_head != hp)
-		radix_node_head->rnh_next = hp;
+	rnh->rnh_next = radix_node_head->rnh_next;
+	if (radix_node_head != rnh)
+		radix_node_head->rnh_next = rnh;
 	return (1);
 }