Improved connection establishment performance by doing local port lookups via

a hashed port list. In the new scheme, in_pcblookup() goes away and is
replaced by a new routine, in_pcblookup_local() for doing the local port
check. Note that this implementation is space inefficient in that the PCB
struct is now too large to fit into 128 bytes. I might deal with this in the
future by using the new zone allocator, but I wanted these changes to be
extensively tested in their current form first.

Also:
1) Fixed off-by-one errors in the port lookup loops in in_pcbbind().
2) Got rid of some unneeded rehashing. Adding a new routine, in_pcbinshash()
   to do the initialial hash insertion.
3) Renamed in_pcblookuphash() to in_pcblookup_hash() for easier readability.
4) Added a new routine, in_pcbremlists() to remove the PCB from the various
   hash lists.
5) Added/deleted comments where appropriate.
6) Removed unnecessary splnet() locking. In general, the PCB functions should
   be called at splnet()...there are unfortunately a few exceptions, however.
7) Reorganized a few structs for better cache line behavior.
8) Killed my TCP_ACK_HACK kludge. It may come back in a different form in
   the future, however.

These changes have been tested on wcarchive for more than a month. In tests
done here, connection establishment overhead is reduced by more than 50
times, thus getting rid of one of the major networking scalability problems.

Still to do: make tcp_fastimo/tcp_slowtimo scale well for systems with a
large number of connections. tcp_fastimo is easy; tcp_slowtimo is difficult.

WARNING: Anything that knows about inpcb and tcpcb structs will have to be
         recompiled; at the very least, this includes netstat(1).

1 files changed, 34 insertions, 23 deletions

diff --git a/sys/netinet/in_pcb.h b/sys/netinet/in_pcb.h
index 18e40e9..27f3586 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.21 1997/04/27 20:01:04 wollman Exp $
+ * $Id: in_pcb.h,v 1.22 1997/08/16 19:15:36 wollman Exp $
  */
 
 #ifndef _NETINET_IN_PCB_H_
@@ -47,16 +47,17 @@
  * control block.
  */
 LIST_HEAD(inpcbhead, inpcb);
+LIST_HEAD(inpcbporthead, inpcbport);
 
 struct inpcb {
-	LIST_ENTRY(inpcb) inp_list;		/* list for all PCBs of this proto */
-	LIST_ENTRY(inpcb) inp_hash;		/* hash list */
-	struct	inpcbinfo *inp_pcbinfo;	/* PCB list info */
+	LIST_ENTRY(inpcb) inp_hash;	/* hash list */
 	struct	in_addr inp_faddr;	/* foreign host table entry */
 	struct	in_addr inp_laddr;	/* local host table entry */
 	u_short	inp_fport;		/* foreign port */
 	u_short	inp_lport;		/* local port */
+	LIST_ENTRY(inpcb) inp_list;	/* list for all PCBs of this proto */
 	caddr_t	inp_ppcb;		/* pointer to per-protocol pcb */
+	struct	inpcbinfo *inp_pcbinfo;	/* PCB list info */
 	struct	socket *inp_socket;	/* back pointer to socket */
 	struct	mbuf *inp_options;	/* IP options */
 	struct	route inp_route;	/* placeholder for routing entry */
@@ -66,22 +67,31 @@ struct inpcb {
 	u_char	inp_ip_p;		/* protocol proto */
 	u_char	pad[1];			/* alignment */
 	struct	ip_moptions *inp_moptions; /* IP multicast options */
-#if 0 /* Someday, perhaps... */
-	struct	ip inp_ip;		/* header prototype; should have more */
-#endif
+	LIST_ENTRY(inpcb) inp_portlist;	/* list for this PCB's local port */
+	struct	inpcbport *inp_phd;	/* head of list for this PCB's local port */
+};
+
+struct inpcbport {
+	LIST_ENTRY(inpcbport) phd_hash;
+	struct inpcbhead phd_pcblist;
+	u_short phd_port;
 };
 
 struct inpcbinfo {
-	struct inpcbhead *listhead;
 	struct inpcbhead *hashbase;
 	unsigned long hashmask;
+	struct inpcbporthead *porthashbase;
+	unsigned long porthashmask;
+	struct inpcbhead *listhead;
 	unsigned short lastport;
 	unsigned short lastlow;
 	unsigned short lasthi;
 };
 
 #define INP_PCBHASH(faddr, lport, fport, mask) \
-	(((faddr) ^ ((faddr) >> 16) ^ (lport) ^ (fport)) & (mask))
+	(((faddr) ^ ((faddr) >> 16) ^ ntohs((lport) ^ (fport))) & (mask))
+#define INP_PCBPORTHASH(lport, mask) \
+	(ntohs((lport)) & (mask))
 
 /* flags in inp_flags: */
 #define	INP_RECVOPTS		0x01	/* receive incoming IP options */
@@ -101,25 +111,26 @@ struct inpcbinfo {
 #define	sotoinpcb(so)	((struct inpcb *)(so)->so_pcb)
 
 #ifdef KERNEL
-void	 in_losing __P((struct inpcb *));
-int	 in_pcballoc __P((struct socket *, struct inpcbinfo *, struct proc *));
-int	 in_pcbbind __P((struct inpcb *, struct sockaddr *, struct proc *));
-int	 in_pcbconnect __P((struct inpcb *, struct sockaddr *, struct proc *));
-void	 in_pcbdetach __P((struct inpcb *));
-void	 in_pcbdisconnect __P((struct inpcb *));
-int	 in_pcbladdr __P((struct inpcb *, struct sockaddr *,
+void	in_losing __P((struct inpcb *));
+int	in_pcballoc __P((struct socket *, struct inpcbinfo *, struct proc *));
+int	in_pcbbind __P((struct inpcb *, struct sockaddr *, struct proc *));
+int	in_pcbconnect __P((struct inpcb *, struct sockaddr *, struct proc *));
+void	in_pcbdetach __P((struct inpcb *));
+void	in_pcbdisconnect __P((struct inpcb *));
+int	in_pcbinshash __P((struct inpcb *));
+int	in_pcbladdr __P((struct inpcb *, struct sockaddr *,
 	    struct sockaddr_in **));
 struct inpcb *
-	 in_pcblookup __P((struct inpcbinfo *,
-	    struct in_addr, u_int, struct in_addr, u_int, int));
+	in_pcblookup_local __P((struct inpcbinfo *,
+	    struct in_addr, u_int, int));
 struct inpcb *
-	 in_pcblookuphash __P((struct inpcbinfo *,
+	in_pcblookup_hash __P((struct inpcbinfo *,
 	    struct in_addr, u_int, struct in_addr, u_int, int));
-void	 in_pcbnotify __P((struct inpcbhead *, struct sockaddr *,
+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 *));
-int	 in_setpeeraddr __P((struct socket *so, struct sockaddr **nam));
-int	 in_setsockaddr __P((struct socket *so, struct sockaddr **nam));
+void	in_pcbrehash __P((struct inpcb *));
+int	in_setpeeraddr __P((struct socket *so, struct sockaddr **nam));
+int	in_setsockaddr __P((struct socket *so, struct sockaddr **nam));
 #endif
 
 #endif