Implemented PCB hashing. Includes new functions in_pcbinshash, in_pcbrehash,

and in_pcblookuphash.

16 files changed, 231 insertions, 132 deletions

diff --git a/sys/netinet/in_pcb.c b/sys/netinet/in_pcb.c
index 62ea84c..ed48027 100644
--- a/sys/netinet/in_pcb.c
+++ b/sys/netinet/in_pcb.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)in_pcb.c	8.2 (Berkeley) 1/4/94
- * $Id: in_pcb.c,v 1.7 1995/03/14 21:50:55 davidg Exp $
+ * $Id: in_pcb.c,v 1.8 1995/03/16 18:14:51 bde Exp $
  */
 
 #include <sys/param.h>
@@ -45,6 +45,7 @@
 #include <sys/errno.h>
 #include <sys/time.h>
 #include <sys/proc.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -59,9 +60,9 @@
 struct	in_addr zeroin_addr;
 
 int
-in_pcballoc(so, head)
+in_pcballoc(so, pcbinfo)
 	struct socket *so;
-	struct inpcb *head;
+	struct inpcbinfo *pcbinfo;
 {
 	register struct inpcb *inp;
 
@@ -69,9 +70,10 @@ in_pcballoc(so, head)
 	if (inp == NULL)
 		return (ENOBUFS);
 	bzero((caddr_t)inp, sizeof(*inp));
-	inp->inp_head = head;
+	inp->inp_pcbinfo = pcbinfo;
 	inp->inp_socket = so;
-	insque(inp, head);
+	LIST_INSERT_HEAD(pcbinfo->listhead, inp, inp_list);
+	in_pcbinshash(inp);
 	so->so_pcb = (caddr_t)inp;
 	return (0);
 }
@@ -82,8 +84,9 @@ in_pcbbind(inp, nam)
 	struct mbuf *nam;
 {
 	register struct socket *so = inp->inp_socket;
-	register struct inpcb *head = inp->inp_head;
-	register struct sockaddr_in *sin;
+	struct inpcbhead *head = inp->inp_pcbinfo->listhead;
+	unsigned short *lastport = &inp->inp_pcbinfo->lastport;
+	struct sockaddr_in *sin;
 	struct proc *p = curproc;		/* XXX */
 	u_short lport = 0;
 	int wild = 0, reuseport = (so->so_options & SO_REUSEPORT);
@@ -141,13 +144,15 @@ in_pcbbind(inp, nam)
 	}
 	if (lport == 0)
 		do {
-			if (head->inp_lport++ < IPPORT_RESERVED ||
-			    head->inp_lport > IPPORT_USERRESERVED)
-				head->inp_lport = IPPORT_RESERVED;
-			lport = htons(head->inp_lport);
+			++*lastport;
+			if (*lastport < IPPORT_RESERVED ||
+			    *lastport > IPPORT_USERRESERVED)
+				*lastport = IPPORT_RESERVED;
+			lport = htons(*lastport);
 		} while (in_pcblookup(head,
 			    zeroin_addr, 0, inp->inp_laddr, lport, wild));
 	inp->inp_lport = lport;
+	in_pcbrehash(inp);
 	return (0);
 }
 
@@ -295,7 +300,7 @@ in_pcbconnect(inp, nam)
 	if (error = in_pcbladdr(inp, nam, &ifaddr))
 		return(error);
 
-	if (in_pcblookup(inp->inp_head,
+	if (in_pcblookup(inp->inp_pcbinfo->listhead,
 	    sin->sin_addr,
 	    sin->sin_port,
 	    inp->inp_laddr.s_addr ? inp->inp_laddr : ifaddr->sin_addr,
@@ -309,6 +314,7 @@ in_pcbconnect(inp, nam)
 	}
 	inp->inp_faddr = sin->sin_addr;
 	inp->inp_fport = sin->sin_port;
+	in_pcbrehash(inp);
 	return (0);
 }
 
@@ -319,6 +325,7 @@ in_pcbdisconnect(inp)
 
 	inp->inp_faddr.s_addr = INADDR_ANY;
 	inp->inp_fport = 0;
+	in_pcbrehash(inp);
 	if (inp->inp_socket->so_state & SS_NOFDREF)
 		in_pcbdetach(inp);
 }
@@ -336,7 +343,8 @@ in_pcbdetach(inp)
 	if (inp->inp_route.ro_rt)
 		rtfree(inp->inp_route.ro_rt);
 	ip_freemoptions(inp->inp_moptions);
-	remque(inp);
+	LIST_REMOVE(inp, inp_hash);
+	LIST_REMOVE(inp, inp_list);
 	FREE(inp, M_PCB);
 }
 
@@ -385,7 +393,7 @@ in_setpeeraddr(inp, nam)
  */
 void
 in_pcbnotify(head, dst, fport_arg, laddr, lport_arg, cmd, notify)
-	struct inpcb *head;
+	struct inpcbhead *head;
 	struct sockaddr *dst;
 	u_int fport_arg, lport_arg;
 	struct in_addr laddr;
@@ -418,17 +426,17 @@ in_pcbnotify(head, dst, fport_arg, laddr, lport_arg, cmd, notify)
 			notify = in_rtchange;
 	}
 	errno = inetctlerrmap[cmd];
-	for (inp = head->inp_next; inp != head;) {
+	for (inp = head->lh_first; inp != NULL;) {
 		if (inp->inp_faddr.s_addr != faddr.s_addr ||
 		    inp->inp_socket == 0 ||
 		    (lport && inp->inp_lport != lport) ||
 		    (laddr.s_addr && inp->inp_laddr.s_addr != laddr.s_addr) ||
 		    (fport && inp->inp_fport != fport)) {
-			inp = inp->inp_next;
+			inp = inp->inp_list.le_next;
 			continue;
 		}
 		oinp = inp;
-		inp = inp->inp_next;
+		inp = inp->inp_list.le_next;
 		if (notify)
 			(*notify)(oinp, errno);
 	}
@@ -489,7 +497,7 @@ in_rtchange(inp, errno)
 
 struct inpcb *
 in_pcblookup(head, faddr, fport_arg, laddr, lport_arg, flags)
-	struct inpcb *head;
+	struct inpcbhead *head;
 	struct in_addr faddr, laddr;
 	u_int fport_arg, lport_arg;
 	int flags;
@@ -498,19 +506,10 @@ in_pcblookup(head, faddr, fport_arg, laddr, lport_arg, flags)
 	int matchwild = 3, wildcard;
 	u_short fport = fport_arg, lport = lport_arg;
 
-	for (inp = head->inp_next; inp != head; inp = inp->inp_next) {
+	for (inp = head->lh_first; inp != NULL; inp = inp->inp_list.le_next) {
 		if (inp->inp_lport != lport)
 			continue;
 		wildcard = 0;
-		if (inp->inp_laddr.s_addr != INADDR_ANY) {
-			if (laddr.s_addr == INADDR_ANY)
-				wildcard++;
-			else if (inp->inp_laddr.s_addr != laddr.s_addr)
-				continue;
-		} else {
-			if (laddr.s_addr != INADDR_ANY)
-				wildcard++;
-		}
 		if (inp->inp_faddr.s_addr != INADDR_ANY) {
 			if (faddr.s_addr == INADDR_ANY)
 				wildcard++;
@@ -521,19 +520,93 @@ in_pcblookup(head, faddr, fport_arg, laddr, lport_arg, flags)
 			if (faddr.s_addr != INADDR_ANY)
 				wildcard++;
 		}
+		if (inp->inp_laddr.s_addr != INADDR_ANY) {
+			if (laddr.s_addr == INADDR_ANY)
+				wildcard++;
+			else if (inp->inp_laddr.s_addr != laddr.s_addr)
+				continue;
+		} else {
+			if (laddr.s_addr != INADDR_ANY)
+				wildcard++;
+		}
 		if (wildcard && (flags & INPLOOKUP_WILDCARD) == 0)
 			continue;
 		if (wildcard < matchwild) {
 			match = inp;
 			matchwild = wildcard;
 			if (matchwild == 0) {
-				if (match->inp_prev != head) {
-					remque(match);
-					insque(match, head);
-				}
 				break;
 			}
 		}
 	}
 	return (match);
 }
+
+/*
+ * Lookup PCB in hash list.
+ */
+struct inpcb *
+in_pcblookuphash(pcbinfo, faddr, fport_arg, laddr, lport_arg)
+	struct inpcbinfo *pcbinfo;
+	struct in_addr faddr, laddr;
+	u_int fport_arg, lport_arg;
+{
+	struct inpcbhead *head;
+	register struct inpcb *inp;
+	u_short fport = fport_arg, lport = lport_arg;
+
+	/*
+	 * First look for an exact match.
+	 */
+	head = &pcbinfo->hashbase[(faddr.s_addr + lport + fport) % pcbinfo->hashsize];
+
+	for (inp = head->lh_first; inp != NULL; inp = inp->inp_hash.le_next) {
+		if (inp->inp_faddr.s_addr != faddr.s_addr ||
+		    inp->inp_fport != fport ||
+		    inp->inp_lport != lport ||
+		    inp->inp_laddr.s_addr != laddr.s_addr)
+			continue;
+		/*
+		 * Move PCB to head of this hash chain so that it can be
+		 * found more quickly in the future.
+		 */
+		if (inp != head->lh_first) {
+			LIST_REMOVE(inp, inp_hash);
+			LIST_INSERT_HEAD(head, inp, inp_hash);
+		}
+		return (inp);
+	}
+
+	/*
+	 * Didn't find an exact match, so try again looking for a matching
+	 * wildcard PCB.
+	 */
+	return (in_pcblookup(pcbinfo->listhead, faddr, fport_arg, laddr,
+	    lport_arg, INPLOOKUP_WILDCARD));
+}
+
+void
+in_pcbinshash(inp)
+	struct inpcb *inp;
+{
+	struct inpcbhead *head;
+
+	head = &inp->inp_pcbinfo->hashbase[(inp->inp_faddr.s_addr +
+		inp->inp_lport + inp->inp_fport) % inp->inp_pcbinfo->hashsize];
+
+	LIST_INSERT_HEAD(head, inp, inp_hash);
+}
+
+void
+in_pcbrehash(inp)
+	struct inpcb *inp;
+{
+	struct inpcbhead *head;
+
+	LIST_REMOVE(inp, inp_hash);
+
+	head = &inp->inp_pcbinfo->hashbase[(inp->inp_faddr.s_addr +
+		inp->inp_lport + inp->inp_fport) % inp->inp_pcbinfo->hashsize];
+
+	LIST_INSERT_HEAD(head, inp, inp_hash);
+}
diff --git a/sys/netinet/in_pcb.h b/sys/netinet/in_pcb.h
index 9946f12..5112e6e 100644
--- a/sys/netinet/in_pcb.h
+++ b/sys/netinet/in_pcb.h
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)in_pcb.h	8.1 (Berkeley) 6/10/93
- * $Id: in_pcb.h,v 1.4 1994/08/21 05:27:28 paul Exp $
+ * $Id: in_pcb.h,v 1.5 1995/03/16 18:14:52 bde Exp $
  */
 
 #ifndef _NETINET_IN_PCB_H_
@@ -44,11 +44,12 @@
  * up (to a socket structure) and down (to a protocol-specific)
  * control block.
  */
+LIST_HEAD(inpcbhead, inpcb);
+
 struct inpcb {
-	struct	inpcb *inp_next,*inp_prev;
-					/* pointers to other pcb's */
-	struct	inpcb *inp_head;	/* pointer back to chain of inpcb's
-					   for this protocol */
+	LIST_ENTRY(inpcb) inp_list;		/* list for all PCBs of this proto */
+	LIST_ENTRY(inpcb) inp_hash;		/* hash list */
+	struct	inpcbinfo *inp_pcbinfo;
 	struct	in_addr inp_faddr;	/* foreign host table entry */
 	u_short	inp_fport;		/* foreign port */
 	struct	in_addr inp_laddr;	/* local host table entry */
@@ -62,6 +63,13 @@ struct inpcb {
 	struct	ip_moptions *inp_moptions; /* IP multicast options */
 };
 
+struct inpcbinfo {
+	struct inpcbhead *listhead;
+	struct inpcbhead *hashbase;
+	unsigned long hashsize;
+	unsigned short lastport;
+};
+
 /* flags in inp_flags: */
 #define	INP_RECVOPTS		0x01	/* receive incoming IP options */
 #define	INP_RECVRETOPTS		0x02	/* receive IP options for reply */
@@ -70,24 +78,28 @@ struct inpcb {
 #define	INP_HDRINCL		0x08	/* user supplies entire IP header */
 
 #define	INPLOOKUP_WILDCARD	1
-#define	INPLOOKUP_SETLOCAL	2
 
 #define	sotoinpcb(so)	((struct inpcb *)(so)->so_pcb)
 
 #ifdef KERNEL
 void	 in_losing __P((struct inpcb *));
-int	 in_pcballoc __P((struct socket *, struct inpcb *));
+int	 in_pcballoc __P((struct socket *, struct inpcbinfo *));
 int	 in_pcbbind __P((struct inpcb *, struct mbuf *));
 int	 in_pcbconnect __P((struct inpcb *, struct mbuf *));
 void	 in_pcbdetach __P((struct inpcb *));
 void	 in_pcbdisconnect __P((struct inpcb *));
+void	 in_pcbinshash __P((struct inpcb *));
 int	 in_pcbladdr __P((struct inpcb *, struct mbuf *,
 	    struct sockaddr_in **));
 struct inpcb *
-	 in_pcblookup __P((struct inpcb *,
+	 in_pcblookup __P((struct inpcbhead *,
 	    struct in_addr, u_int, struct in_addr, u_int, int));
-void	 in_pcbnotify __P((struct inpcb *, struct sockaddr *,
+struct inpcb *
+	 in_pcblookuphash __P((struct inpcbinfo *,
+	    struct in_addr, u_int, struct in_addr, u_int));
+void	 in_pcbnotify __P((struct inpcbhead *, struct sockaddr *,
 	    u_int, struct in_addr, u_int, int, void (*)(struct inpcb *, int)));
+void	 in_pcbrehash __P((struct inpcb *));
 void	 in_rtchange __P((struct inpcb *, int));
 void	 in_setpeeraddr __P((struct inpcb *, struct mbuf *));
 void	 in_setsockaddr __P((struct inpcb *, struct mbuf *));
diff --git a/sys/netinet/in_proto.c b/sys/netinet/in_proto.c
index fe9aa55..54eb8cd 100644
--- a/sys/netinet/in_proto.c
+++ b/sys/netinet/in_proto.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)in_proto.c	8.1 (Berkeley) 6/10/93
- * $Id: in_proto.c,v 1.11 1995/02/09 23:13:20 wollman Exp $
+ * $Id: in_proto.c,v 1.12 1995/02/16 00:55:38 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -39,6 +39,7 @@
 #include <sys/protosw.h>
 #include <sys/domain.h>
 #include <sys/mbuf.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/radix.h>
diff --git a/sys/netinet/ip_mroute.c b/sys/netinet/ip_mroute.c
index bbc02e4..fc5b618 100644
--- a/sys/netinet/ip_mroute.c
+++ b/sys/netinet/ip_mroute.c
@@ -21,6 +21,7 @@
 #include <sys/time.h>
 #include <sys/ioctl.h>
 #include <sys/syslog.h>
+#include <sys/queue.h>
 #include <net/if.h>
 #include <net/route.h>
 #include <netinet/in.h>
diff --git a/sys/netinet/ip_output.c b/sys/netinet/ip_output.c
index e4936ce..18ebe02 100644
--- a/sys/netinet/ip_output.c
+++ b/sys/netinet/ip_output.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)ip_output.c	8.3 (Berkeley) 1/21/94
- * $Id: ip_output.c,v 1.14 1995/03/20 18:11:31 wollman Exp $
+ * $Id: ip_output.c,v 1.15 1995/03/20 18:31:51 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -42,6 +42,7 @@
 #include <sys/protosw.h>
 #include <sys/socket.h>
 #include <sys/socketvar.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
diff --git a/sys/netinet/raw_ip.c b/sys/netinet/raw_ip.c
index 95fe7a6..3e31416 100644
--- a/sys/netinet/raw_ip.c
+++ b/sys/netinet/raw_ip.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)raw_ip.c	8.2 (Berkeley) 1/4/94
- * $Id: raw_ip.c,v 1.15 1995/02/14 06:24:40 phk Exp $
+ * $Id: raw_ip.c,v 1.16 1995/03/16 16:25:43 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -42,6 +42,7 @@
 #include <sys/socketvar.h>
 #include <sys/errno.h>
 #include <sys/systm.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -55,7 +56,8 @@
 
 #include <netinet/ip_fw.h>
 
-struct inpcb rawinpcb;
+struct inpcbhead ripcb;
+struct inpcbinfo ripcbinfo;
 
 /*
  * Nominal space allocated to a raw ip socket.
@@ -73,8 +75,14 @@ struct inpcb rawinpcb;
 void
 rip_init()
 {
-
-	rawinpcb.inp_next = rawinpcb.inp_prev = &rawinpcb;
+	LIST_INIT(&ripcb);
+	ripcbinfo.listhead = &ripcb;
+	/*
+	 * XXX We don't use the hash list for raw IP, but it's easier
+	 * to allocate a one entry hash list than it is to check all
+	 * over the place for hashbase == NULL.
+	 */
+	ripcbinfo.hashbase = phashinit(1, M_PCB, &ripcbinfo.hashsize);
 }
 
 struct	sockaddr_in ripsrc = { sizeof(ripsrc), AF_INET };
@@ -92,7 +100,7 @@ rip_input(m)
 	struct socket *last = 0;
 
 	ripsrc.sin_addr = ip->ip_src;
-	for (inp = rawinpcb.inp_next; inp != &rawinpcb; inp = inp->inp_next) {
+	for (inp = ripcb.lh_first; inp != NULL; inp = inp->inp_list.le_next) {
 		if (inp->inp_ip.ip_p && inp->inp_ip.ip_p != ip->ip_p)
 			continue;
 		if (inp->inp_laddr.s_addr &&
@@ -317,7 +325,7 @@ rip_usrreq(so, req, m, nam, control)
 			break;
 		}
 		if ((error = soreserve(so, rip_sendspace, rip_recvspace)) ||
-		    (error = in_pcballoc(so, &rawinpcb)))
+		    (error = in_pcballoc(so, &ripcbinfo)))
 			break;
 		inp = (struct inpcb *)so->so_pcb;
 		inp->inp_ip.ip_p = (int)nam;
diff --git a/sys/netinet/tcp_input.c b/sys/netinet/tcp_input.c
index d9f287d..0ec0643 100644
--- a/sys/netinet/tcp_input.c
+++ b/sys/netinet/tcp_input.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	From: @(#)tcp_input.c	8.5 (Berkeley) 4/10/94
- *	$Id: tcp_input.c,v 1.17 1995/03/27 07:12:24 davidg Exp $
+ *	$Id: tcp_input.c,v 1.18 1995/04/05 10:32:14 olah Exp $
  */
 
 #ifndef TUBA_INCLUDE
@@ -43,6 +43,7 @@
 #include <sys/socket.h>
 #include <sys/socketvar.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -64,12 +65,12 @@ struct	tcpiphdr tcp_saveti;
 #endif
 
 int	tcprexmtthresh = 3;
-struct	inpcb *tcp_last_inpcb = &tcb;
 tcp_seq	tcp_iss;
 tcp_cc	tcp_ccgen;
-struct	inpcb tcb;
 struct	tcpstat tcpstat;
 u_long	tcp_now;
+struct inpcbhead tcb;
+struct inpcbinfo tcbinfo;
 
 #endif /* TUBA_INCLUDE */
 
@@ -333,17 +334,7 @@ tcp_input(m, iphlen)
 	 * Locate pcb for segment.
 	 */
 findpcb:
-	inp = tcp_last_inpcb;
-	if (inp->inp_lport != ti->ti_dport ||
-	    inp->inp_fport != ti->ti_sport ||
-	    inp->inp_faddr.s_addr != ti->ti_src.s_addr ||
-	    inp->inp_laddr.s_addr != ti->ti_dst.s_addr) {
-		inp = in_pcblookup(&tcb, ti->ti_src, ti->ti_sport,
-		    ti->ti_dst, ti->ti_dport, INPLOOKUP_WILDCARD);
-		if (inp)
-			tcp_last_inpcb = inp;
-		++tcpstat.tcps_pcbcachemiss;
-	}
+	inp = in_pcblookuphash(&tcbinfo, ti->ti_src, ti->ti_sport, ti->ti_dst, ti->ti_dport);
 
 	/*
 	 * If the state is CLOSED (i.e., TCB does not exist) then
@@ -393,6 +384,7 @@ findpcb:
 			inp = (struct inpcb *)so->so_pcb;
 			inp->inp_laddr = ti->ti_dst;
 			inp->inp_lport = ti->ti_dport;
+			in_pcbrehash(inp);
 #if BSD>=43
 			inp->inp_options = ip_srcroute();
 #endif
diff --git a/sys/netinet/tcp_output.c b/sys/netinet/tcp_output.c
index ca60732..f471b3b 100644
--- a/sys/netinet/tcp_output.c
+++ b/sys/netinet/tcp_output.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_output.c	8.3 (Berkeley) 12/30/93
- * $Id: tcp_output.c,v 1.7 1995/02/09 23:13:24 wollman Exp $
+ * $Id: tcp_output.c,v 1.8 1995/02/16 00:55:40 wollman Exp $
  */
 
 #include <sys/param.h>
@@ -42,6 +42,7 @@
 #include <sys/socket.h>
 #include <sys/socketvar.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/route.h>
 
diff --git a/sys/netinet/tcp_reass.c b/sys/netinet/tcp_reass.c
index d9f287d..0ec0643 100644
--- a/sys/netinet/tcp_reass.c
+++ b/sys/netinet/tcp_reass.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	From: @(#)tcp_input.c	8.5 (Berkeley) 4/10/94
- *	$Id: tcp_input.c,v 1.17 1995/03/27 07:12:24 davidg Exp $
+ *	$Id: tcp_input.c,v 1.18 1995/04/05 10:32:14 olah Exp $
  */
 
 #ifndef TUBA_INCLUDE
@@ -43,6 +43,7 @@
 #include <sys/socket.h>
 #include <sys/socketvar.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -64,12 +65,12 @@ struct	tcpiphdr tcp_saveti;
 #endif
 
 int	tcprexmtthresh = 3;
-struct	inpcb *tcp_last_inpcb = &tcb;
 tcp_seq	tcp_iss;
 tcp_cc	tcp_ccgen;
-struct	inpcb tcb;
 struct	tcpstat tcpstat;
 u_long	tcp_now;
+struct inpcbhead tcb;
+struct inpcbinfo tcbinfo;
 
 #endif /* TUBA_INCLUDE */
 
@@ -333,17 +334,7 @@ tcp_input(m, iphlen)
 	 * Locate pcb for segment.
 	 */
 findpcb:
-	inp = tcp_last_inpcb;
-	if (inp->inp_lport != ti->ti_dport ||
-	    inp->inp_fport != ti->ti_sport ||
-	    inp->inp_faddr.s_addr != ti->ti_src.s_addr ||
-	    inp->inp_laddr.s_addr != ti->ti_dst.s_addr) {
-		inp = in_pcblookup(&tcb, ti->ti_src, ti->ti_sport,
-		    ti->ti_dst, ti->ti_dport, INPLOOKUP_WILDCARD);
-		if (inp)
-			tcp_last_inpcb = inp;
-		++tcpstat.tcps_pcbcachemiss;
-	}
+	inp = in_pcblookuphash(&tcbinfo, ti->ti_src, ti->ti_sport, ti->ti_dst, ti->ti_dport);
 
 	/*
 	 * If the state is CLOSED (i.e., TCB does not exist) then
@@ -393,6 +384,7 @@ findpcb:
 			inp = (struct inpcb *)so->so_pcb;
 			inp->inp_laddr = ti->ti_dst;
 			inp->inp_lport = ti->ti_dport;
+			in_pcbrehash(inp);
 #if BSD>=43
 			inp->inp_options = ip_srcroute();
 #endif
diff --git a/sys/netinet/tcp_subr.c b/sys/netinet/tcp_subr.c
index fbbff78..ea68652 100644
--- a/sys/netinet/tcp_subr.c
+++ b/sys/netinet/tcp_subr.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_subr.c	8.1 (Berkeley) 6/10/93
- * $Id: tcp_subr.c,v 1.8 1995/03/06 02:49:24 nate Exp $
+ * $Id: tcp_subr.c,v 1.9 1995/03/16 18:15:05 bde Exp $
  */
 
 #include <sys/param.h>
@@ -43,6 +43,7 @@
 #include <sys/socketvar.h>
 #include <sys/protosw.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/route.h>
 #include <net/if.h>
@@ -71,7 +72,13 @@ int	tcp_do_rfc1323 = 1;
 int	tcp_do_rfc1644 = 1;
 static	void tcp_cleartaocache(void);
 
-extern	struct inpcb *tcp_last_inpcb;
+/*
+ * Target size of TCP PCB hash table. Will be rounded down to a prime
+ * number.
+ */
+#ifndef TCBHASHSIZE
+#define TCBHASHSIZE	128
+#endif
 
 /*
  * Tcp initialization
@@ -83,7 +90,9 @@ tcp_init()
 	tcp_iss = 1;		/* wrong */
 	tcp_ccgen = 1;
 	tcp_cleartaocache();
-	tcb.inp_next = tcb.inp_prev = &tcb;
+	LIST_INIT(&tcb);
+	tcbinfo.listhead = &tcb;
+	tcbinfo.hashbase = phashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashsize);
 	if (max_protohdr < sizeof(struct tcpiphdr))
 		max_protohdr = sizeof(struct tcpiphdr);
 	if (max_linkhdr + sizeof(struct tcpiphdr) > MHLEN)
@@ -373,9 +382,6 @@ tcp_close(tp)
 	free(tp, M_PCB);
 	inp->inp_ppcb = 0;
 	soisdisconnected(so);
-	/* clobber input pcb cache if we're closing the cached connection */
-	if (inp == tcp_last_inpcb)
-		tcp_last_inpcb = &tcb;
 	in_pcbdetach(inp);
 	tcpstat.tcps_closed++;
 	return ((struct tcpcb *)0);
diff --git a/sys/netinet/tcp_timer.c b/sys/netinet/tcp_timer.c
index e302003..426b749 100644
--- a/sys/netinet/tcp_timer.c
+++ b/sys/netinet/tcp_timer.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_timer.c	8.1 (Berkeley) 6/10/93
- * $Id: tcp_timer.c,v 1.3 1995/02/09 23:13:26 wollman Exp $
+ * $Id: tcp_timer.c,v 1.4 1995/02/16 00:55:42 wollman Exp $
  */
 
 #ifndef TUBA_INCLUDE
@@ -43,6 +43,7 @@
 #include <sys/socketvar.h>
 #include <sys/protosw.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/if.h>
 #include <net/route.h>
@@ -71,11 +72,11 @@ tcp_fasttimo()
 {
 	register struct inpcb *inp;
 	register struct tcpcb *tp;
-	int s = splnet();
+	int s;
 
-	inp = tcb.inp_next;
-	if (inp)
-	for (; inp != &tcb; inp = inp->inp_next)
+	s = splnet();
+
+	for (inp = tcb.lh_first; inp != NULL; inp = inp->inp_list.le_next) {
 		if ((tp = (struct tcpcb *)inp->inp_ppcb) &&
 		    (tp->t_flags & TF_DELACK)) {
 			tp->t_flags &= ~TF_DELACK;
@@ -83,6 +84,7 @@ tcp_fasttimo()
 			tcpstat.tcps_delack++;
 			(void) tcp_output(tp);
 		}
+	}
 	splx(s);
 }
 
@@ -96,20 +98,23 @@ tcp_slowtimo()
 {
 	register struct inpcb *ip, *ipnxt;
 	register struct tcpcb *tp;
-	int s = splnet();
 	register int i;
+	int s;
+
+	s = splnet();
 
 	tcp_maxidle = TCPTV_KEEPCNT * tcp_keepintvl;
-	/*
-	 * Search through tcb's and update active timers.
-	 */
-	ip = tcb.inp_next;
-	if (ip == 0) {
+
+	ip = tcb.lh_first;
+	if (ip == NULL) {
 		splx(s);
 		return;
 	}
-	for (; ip != &tcb; ip = ipnxt) {
-		ipnxt = ip->inp_next;
+	/*
+	 * Search through tcb's and update active timers.
+	 */
+	for (; ip != NULL; ip = ipnxt) {
+		ipnxt = ip->inp_list.le_next;
 		tp = intotcpcb(ip);
 		if (tp == 0)
 			continue;
@@ -118,7 +123,7 @@ tcp_slowtimo()
 				(void) tcp_usrreq(tp->t_inpcb->inp_socket,
 				    PRU_SLOWTIMO, (struct mbuf *)0,
 				    (struct mbuf *)i, (struct mbuf *)0);
-				if (ipnxt->inp_prev != ip)
+				if (*ipnxt->inp_list.le_prev != ip)
 					goto tpgone;
 			}
 		}
diff --git a/sys/netinet/tcp_timewait.c b/sys/netinet/tcp_timewait.c
index fbbff78..ea68652 100644
--- a/sys/netinet/tcp_timewait.c
+++ b/sys/netinet/tcp_timewait.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_subr.c	8.1 (Berkeley) 6/10/93
- * $Id: tcp_subr.c,v 1.8 1995/03/06 02:49:24 nate Exp $
+ * $Id: tcp_subr.c,v 1.9 1995/03/16 18:15:05 bde Exp $
  */
 
 #include <sys/param.h>
@@ -43,6 +43,7 @@
 #include <sys/socketvar.h>
 #include <sys/protosw.h>
 #include <sys/errno.h>
+#include <sys/queue.h>
 
 #include <net/route.h>
 #include <net/if.h>
@@ -71,7 +72,13 @@ int	tcp_do_rfc1323 = 1;
 int	tcp_do_rfc1644 = 1;
 static	void tcp_cleartaocache(void);
 
-extern	struct inpcb *tcp_last_inpcb;
+/*
+ * Target size of TCP PCB hash table. Will be rounded down to a prime
+ * number.
+ */
+#ifndef TCBHASHSIZE
+#define TCBHASHSIZE	128
+#endif
 
 /*
  * Tcp initialization
@@ -83,7 +90,9 @@ tcp_init()
 	tcp_iss = 1;		/* wrong */
 	tcp_ccgen = 1;
 	tcp_cleartaocache();
-	tcb.inp_next = tcb.inp_prev = &tcb;
+	LIST_INIT(&tcb);
+	tcbinfo.listhead = &tcb;
+	tcbinfo.hashbase = phashinit(TCBHASHSIZE, M_PCB, &tcbinfo.hashsize);
 	if (max_protohdr < sizeof(struct tcpiphdr))
 		max_protohdr = sizeof(struct tcpiphdr);
 	if (max_linkhdr + sizeof(struct tcpiphdr) > MHLEN)
@@ -373,9 +382,6 @@ tcp_close(tp)
 	free(tp, M_PCB);
 	inp->inp_ppcb = 0;
 	soisdisconnected(so);
-	/* clobber input pcb cache if we're closing the cached connection */
-	if (inp == tcp_last_inpcb)
-		tcp_last_inpcb = &tcb;
 	in_pcbdetach(inp);
 	tcpstat.tcps_closed++;
 	return ((struct tcpcb *)0);
diff --git a/sys/netinet/tcp_usrreq.c b/sys/netinet/tcp_usrreq.c
index 9a412b5..eb8237c 100644
--- a/sys/netinet/tcp_usrreq.c
+++ b/sys/netinet/tcp_usrreq.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	From: @(#)tcp_usrreq.c	8.2 (Berkeley) 1/3/94
- *	$Id: tcp_usrreq.c,v 1.11 1995/02/17 00:29:42 wollman Exp $
+ *	$Id: tcp_usrreq.c,v 1.12 1995/03/16 18:15:06 bde Exp $
  */
 
 #include <sys/param.h>
@@ -184,7 +184,7 @@ tcp_usrreq(so, req, m, nam, control)
 	 */
 	case PRU_LISTEN:
 		if (inp->inp_lport == 0)
-			error = in_pcbbind(inp, (struct mbuf *)0);
+			error = in_pcbbind(inp, NULL);
 		if (error == 0)
 			tp->t_state = TCPS_LISTEN;
 		break;
@@ -408,7 +408,7 @@ tcp_connect(tp, nam)
 	 * TIME_WAIT state, creating an ADDRINUSE error.
 	 */
 	error = in_pcbladdr(inp, nam, &ifaddr);
-	oinp = in_pcblookup(inp->inp_head,
+	oinp = in_pcblookup(inp->inp_pcbinfo->listhead,
 	    sin->sin_addr, sin->sin_port,
 	    inp->inp_laddr.s_addr != INADDR_ANY ? inp->inp_laddr
 						: ifaddr->sin_addr,
@@ -426,6 +426,7 @@ tcp_connect(tp, nam)
 		inp->inp_laddr = ifaddr->sin_addr;
 	inp->inp_faddr = sin->sin_addr;
 	inp->inp_fport = sin->sin_port;
+	in_pcbrehash(inp);
 
 	tp->t_template = tcp_template(tp);
 	if (tp->t_template == 0) {
@@ -578,7 +579,7 @@ tcp_attach(so)
 		if (error)
 			return (error);
 	}
-	error = in_pcballoc(so, &tcb);
+	error = in_pcballoc(so, &tcbinfo);
 	if (error)
 		return (error);
 	inp = sotoinpcb(so);
diff --git a/sys/netinet/tcp_var.h b/sys/netinet/tcp_var.h
index bd4705e..56d9f3e 100644
--- a/sys/netinet/tcp_var.h
+++ b/sys/netinet/tcp_var.h
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)tcp_var.h	8.3 (Berkeley) 4/10/94
- * $Id: tcp_var.h,v 1.9 1995/02/16 00:55:44 wollman Exp $
+ * $Id: tcp_var.h,v 1.10 1995/03/16 18:15:07 bde Exp $
  */
 
 #ifndef _NETINET_TCP_VAR_H_
@@ -307,13 +307,15 @@ struct	tcpstat {
 }
 
 #ifdef KERNEL
-extern	struct inpcb tcb;	/* head of queue of active tcpcb's */
+extern	struct inpcbhead tcb;		/* head of queue of active tcpcb's */
+extern	struct inpcbinfo tcbinfo;
 extern	struct tcpstat tcpstat;	/* tcp statistics */
 extern	int tcp_do_rfc1323;	/* XXX */
 extern	int tcp_do_rfc1644;	/* XXX */
 extern	int tcp_mssdflt;	/* XXX */
 extern	u_long tcp_now;		/* for RFC 1323 timestamps */
 extern	int tcp_rttdflt;	/* XXX */
+extern  u_short tcp_lastport;	/* last assigned port */
 
 int	 tcp_attach __P((struct socket *));
 void	 tcp_canceltimers __P((struct tcpcb *));
diff --git a/sys/netinet/udp_usrreq.c b/sys/netinet/udp_usrreq.c
index ec7ea3e..8a6ff92 100644
--- a/sys/netinet/udp_usrreq.c
+++ b/sys/netinet/udp_usrreq.c
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)udp_usrreq.c	8.4 (Berkeley) 1/21/94
- * $Id: udp_usrreq.c,v 1.7 1995/02/16 01:47:36 wollman Exp $
+ * $Id: udp_usrreq.c,v 1.8 1995/03/16 18:15:09 bde Exp $
  */
 
 #include <sys/param.h>
@@ -43,6 +43,7 @@
 #include <sys/socketvar.h>
 #include <sys/errno.h>
 #include <sys/stat.h>
+#include <sys/queue.h>
 #include <vm/vm.h>
 #include <sys/sysctl.h>
 
@@ -69,11 +70,16 @@ int	udpcksum = 1;
 int	udpcksum = 0;		/* XXX */
 #endif
 
-struct	inpcb udb;		/* from udp_var.h */
+struct	inpcbhead udb;		/* from udp_var.h */
+struct	inpcbinfo udbinfo;
+
+#ifndef UDBHASHSIZE
+#define UDBHASHSIZE 64
+#endif
+
 struct	udpstat udpstat;	/* from udp_var.h */
 
 struct	sockaddr_in udp_in = { sizeof(udp_in), AF_INET };
-struct	inpcb *udp_last_inpcb = &udb;
 
 static	void udp_detach __P((struct inpcb *));
 static	void udp_notify __P((struct inpcb *, int));
@@ -82,7 +88,9 @@ static	struct mbuf *udp_saveopt __P((caddr_t, int, int));
 void
 udp_init()
 {
-	udb.inp_next = udb.inp_prev = &udb;
+	LIST_INIT(&udb);
+	udbinfo.listhead = &udb;
+	udbinfo.hashbase = phashinit(UDBHASHSIZE, M_PCB, &udbinfo.hashsize);
 }
 
 void
@@ -189,7 +197,7 @@ udp_input(m, iphlen)
 		 * (Algorithm copied from raw_intr().)
 		 */
 		last = NULL;
-		for (inp = udb.inp_next; inp != &udb; inp = inp->inp_next) {
+		for (inp = udb.lh_first; inp != NULL; inp = inp->inp_list.le_next) {
 			if (inp->inp_lport != uh->uh_dport)
 				continue;
 			if (inp->inp_laddr.s_addr != INADDR_ANY) {
@@ -250,18 +258,9 @@ udp_input(m, iphlen)
 	/*
 	 * Locate pcb for datagram.
 	 */
-	inp = udp_last_inpcb;
-	if (inp->inp_lport != uh->uh_dport ||
-	    inp->inp_fport != uh->uh_sport ||
-	    inp->inp_faddr.s_addr != ip->ip_src.s_addr ||
-	    inp->inp_laddr.s_addr != ip->ip_dst.s_addr) {
-		inp = in_pcblookup(&udb, ip->ip_src, uh->uh_sport,
-		    ip->ip_dst, uh->uh_dport, INPLOOKUP_WILDCARD);
-		if (inp)
-			udp_last_inpcb = inp;
-		udpstat.udpps_pcbcachemiss++;
-	}
-	if (inp == 0) {
+	inp = in_pcblookuphash(&udbinfo, ip->ip_src, uh->uh_sport,
+	    ip->ip_dst, uh->uh_dport);
+	if (inp == NULL) {
 		udpstat.udps_noport++;
 		if (m->m_flags & (M_BCAST | M_MCAST)) {
 			udpstat.udps_noportbcast++;
@@ -503,7 +502,7 @@ udp_usrreq(so, req, m, addr, control)
 			break;
 		}
 		s = splnet();
-		error = in_pcballoc(so, &udb);
+		error = in_pcballoc(so, &udbinfo);
 		splx(s);
 		if (error)
 			break;
@@ -617,8 +616,6 @@ udp_detach(inp)
 {
 	int s = splnet();
 
-	if (inp == udp_last_inpcb)
-		udp_last_inpcb = &udb;
 	in_pcbdetach(inp);
 	splx(s);
 }
diff --git a/sys/netinet/udp_var.h b/sys/netinet/udp_var.h
index eb9caa9..6e98e9c 100644
--- a/sys/netinet/udp_var.h
+++ b/sys/netinet/udp_var.h
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  *	@(#)udp_var.h	8.1 (Berkeley) 6/10/93
- * $Id: udp_var.h,v 1.3 1994/08/21 05:27:42 paul Exp $
+ * $Id: udp_var.h,v 1.4 1995/02/16 00:27:47 wollman Exp $
  */
 
 #ifndef _NETINET_UDP_VAR_H_
@@ -88,7 +88,8 @@ struct	udpstat {
 }
 
 #ifdef KERNEL
-extern struct	inpcb udb;
+extern struct	inpcbhead udb;
+extern struct	inpcbinfo udbinfo;
 extern struct	udpstat udpstat;
 
 void	 udp_ctlinput __P((int, struct sockaddr *, struct ip *));