Adds a hash table to speed local address lookup

on a per VRF basis (BSD has only one VRF currently).
Hash table is sized to 16 but may need to be adjusted
for machines with large numbers of addresses.
Reviewed by:	gnn

5 files changed, 74 insertions, 7 deletions

diff --git a/sys/netinet/sctp_os_bsd.h b/sys/netinet/sctp_os_bsd.h
index 87c17f1..6900363 100644
--- a/sys/netinet/sctp_os_bsd.h
+++ b/sys/netinet/sctp_os_bsd.h
@@ -116,6 +116,8 @@ __FBSDID("$FreeBSD$");
 #define SCTP_SIZE_OF_VRF_HASH 3
 #define SCTP_IFNAMSIZ IFNAMSIZ
 #define SCTP_DEFAULT_VRFID 0
+#define SCTP_VRF_HASH_SIZE 16
+
 
 #define SCTP_IFN_IS_IFT_LOOP(ifn) ((ifn)->ifn_type == IFT_LOOP)
 
diff --git a/sys/netinet/sctp_pcb.c b/sys/netinet/sctp_pcb.c
index 820bd98..26e0d59 100644
--- a/sys/netinet/sctp_pcb.c
+++ b/sys/netinet/sctp_pcb.c
@@ -155,6 +155,16 @@ sctp_allocate_vrf(int vrfid)
 	vrf->vrf_id = vrfid;
 	LIST_INIT(&vrf->ifnlist);
 	vrf->total_ifa_count = 0;
+	/* Init the HASH of addresses */
+	vrf->vrf_addr_hash = SCTP_HASH_INIT(SCTP_VRF_HASH_SIZE,
+	    &vrf->vrf_hashmark);
+	if (vrf->vrf_addr_hash == NULL) {
+		/* No memory */
+#ifdef INVARIANTS
+		panic("No memory for VRF:%d", vrfid);
+#endif
+		return (NULL);
+	}
 	/* Add it to the hash table */
 	bucket = &sctppcbinfo.sctp_vrfhash[(vrfid & sctppcbinfo.hashvrfmark)];
 	LIST_INSERT_HEAD(bucket, vrf, next_vrf);
@@ -217,6 +227,8 @@ sctp_add_addr_to_vrf(uint32_t vrfid, void *ifn, uint32_t ifn_index,
 	struct sctp_vrf *vrf;
 	struct sctp_ifn *sctp_ifnp = NULL;
 	struct sctp_ifa *sctp_ifap = NULL;
+	struct sctp_ifalist *hash_head;
+	uint32_t hash_of_addr;
 
 	/* How granular do we need the locks to be here? */
 	SCTP_IPI_ADDR_LOCK();
@@ -325,11 +337,15 @@ sctp_add_addr_to_vrf(uint32_t vrfid, void *ifn, uint32_t ifn_index,
 			sctp_ifap->src_is_priv = 1;
 		}
 	}
+	hash_of_addr = sctp_get_ifa_hash_val(&sctp_ifap->address.sa);
+
 	if ((sctp_ifap->src_is_priv == 0) &&
 	    (sctp_ifap->src_is_loop == 0)) {
 		sctp_ifap->src_is_glob = 1;
 	}
 	SCTP_IPI_ADDR_LOCK();
+	hash_head = &vrf->vrf_addr_hash[(hash_of_addr & vrf->vrf_hashmark)];
+	LIST_INSERT_HEAD(hash_head, sctp_ifap, next_bucket);
 	sctp_ifap->refcount = 1;
 	LIST_INSERT_HEAD(&sctp_ifnp->ifalist, sctp_ifap, next_ifa);
 	sctp_ifnp->ifa_count++;
@@ -365,6 +381,7 @@ sctp_del_addr_from_vrf(uint32_t vrfid, struct sockaddr *addr,
 		sctp_ifap->localifa_flags |= SCTP_BEING_DELETED;
 		sctp_ifnp->ifa_count--;
 		vrf->total_ifa_count--;
+		LIST_REMOVE(sctp_ifap, next_bucket);
 		LIST_REMOVE(sctp_ifap, next_ifa);
 		atomic_add_int(&sctp_ifnp->refcount, -1);
 	} else {
diff --git a/sys/netinet/sctp_pcb.h b/sys/netinet/sctp_pcb.h
index 0f90503..16d03de 100644
--- a/sys/netinet/sctp_pcb.h
+++ b/sys/netinet/sctp_pcb.h
@@ -112,9 +112,11 @@ TAILQ_HEAD(sctp_streamhead, sctp_stream_queue_pending);
 
 struct sctp_vrf {
 	LIST_ENTRY(sctp_vrf) next_vrf;
+	struct sctp_ifalist *vrf_addr_hash;
 	struct sctp_ifnlist ifnlist;
 	uint32_t vrf_id;
 	uint32_t total_ifa_count;
+	u_long vrf_hashmark;
 };
 
 struct sctp_ifn {
@@ -144,6 +146,7 @@ struct sctp_ifn {
 
 struct sctp_ifa {
 	LIST_ENTRY(sctp_ifa) next_ifa;
+	LIST_ENTRY(sctp_ifa) next_bucket;
 	struct sctp_ifn *ifn_p;	/* back pointer to parent ifn */
 	void *ifa;		/* pointer to ifa, needed for flag update for
 				 * that we MUST lock appropriate locks. This
diff --git a/sys/netinet/sctputil.c b/sys/netinet/sctputil.c
index e3c240c..ea7a830 100644
--- a/sys/netinet/sctputil.c
+++ b/sys/netinet/sctputil.c
@@ -4271,26 +4271,68 @@ sctp_find_ifa_in_ifn(struct sctp_ifn *sctp_ifnp, struct sockaddr *addr,
 	return (NULL);
 }
 
+uint32_t
+sctp_get_ifa_hash_val(struct sockaddr *addr)
+{
+
+	if (addr->sa_family == AF_INET) {
+		struct sockaddr_in *sin;
+
+		sin = (struct sockaddr_in *)addr;
+		return (sin->sin_addr.s_addr ^ (sin->sin_addr.s_addr >> 16));
+	} else if (addr->sa_family == AF_INET6) {
+		struct sockaddr_in6 *sin6;
+		uint32_t hash_of_addr;
+
+		sin6 = (struct sockaddr_in6 *)addr;
+		hash_of_addr = (sin6->sin6_addr.s6_addr32[0] +
+		    sin6->sin6_addr.s6_addr32[1] +
+		    sin6->sin6_addr.s6_addr32[2] +
+		    sin6->sin6_addr.s6_addr32[3]);
+		hash_of_addr = (hash_of_addr ^ (hash_of_addr >> 16));
+		return (hash_of_addr);
+	}
+	return (0);
+}
+
 struct sctp_ifa *
 sctp_find_ifa_by_addr(struct sockaddr *addr, uint32_t vrf_id, int holds_lock)
 {
 	struct sctp_ifa *sctp_ifap;
-	struct sctp_ifn *sctp_ifnp = NULL;
 	struct sctp_vrf *vrf;
+	struct sctp_ifalist *hash_head;
+	uint32_t hash_of_addr;
 
 	vrf = sctp_find_vrf(vrf_id);
 	if (vrf == NULL)
 		return (NULL);
 
+	hash_of_addr = sctp_get_ifa_hash_val(addr);
 	if (holds_lock == 0)
 		SCTP_IPI_ADDR_LOCK();
 
-	LIST_FOREACH(sctp_ifnp, &vrf->ifnlist, next_ifn) {
-		sctp_ifap = sctp_find_ifa_in_ifn(sctp_ifnp, addr, 1);
-		if (sctp_ifap) {
-			if (holds_lock == 0)
-				SCTP_IPI_ADDR_UNLOCK();
-			return (sctp_ifap);
+	hash_head = &vrf->vrf_addr_hash[(hash_of_addr & vrf->vrf_hashmark)];
+	LIST_FOREACH(sctp_ifap, hash_head, next_bucket) {
+		if (addr->sa_family != sctp_ifap->address.sa.sa_family)
+			continue;
+		if (addr->sa_family == AF_INET) {
+			if (((struct sockaddr_in *)addr)->sin_addr.s_addr ==
+			    sctp_ifap->address.sin.sin_addr.s_addr) {
+				/* found him. */
+				if (holds_lock == 0)
+					SCTP_IPI_ADDR_UNLOCK();
+				return (sctp_ifap);
+				break;
+			}
+		} else if (addr->sa_family == AF_INET6) {
+			if (SCTP6_ARE_ADDR_EQUAL(&((struct sockaddr_in6 *)addr)->sin6_addr,
+			    &sctp_ifap->address.sin6.sin6_addr)) {
+				/* found him. */
+				if (holds_lock == 0)
+					SCTP_IPI_ADDR_UNLOCK();
+				return (sctp_ifap);
+				break;
+			}
 		}
 	}
 	if (holds_lock == 0)
diff --git a/sys/netinet/sctputil.h b/sys/netinet/sctputil.h
index 5e1ef0d..25e0c72 100644
--- a/sys/netinet/sctputil.h
+++ b/sys/netinet/sctputil.h
@@ -56,6 +56,9 @@ void sctp_m_freem(struct mbuf *m);
 /*
  * Function prototypes
  */
+uint32_t
+sctp_get_ifa_hash_val(struct sockaddr *addr);
+
 struct sctp_ifa *
          sctp_find_ifa_in_ep(struct sctp_inpcb *inp, struct sockaddr *addr, int hold_lock);
 struct sctp_ifa *