Index: sys/netinet/libalias/alias_db.c
===================================================================
--- sys/netinet/libalias/alias_db.c
+++ sys/netinet/libalias/alias_db.c
@@ -220,9 +220,8 @@
 #define NO_DEST_PORT     1
 #define NO_SRC_PORT      1
 
-/* Dummy address used for FindLinkIn/Out() and AddLink().
-   The value of this variable is never used. */
-static struct in_addr const NO_ADDR;
+/* Matches any/unknown address in FindLinkIn/Out() and AddLink(). */
+static struct in_addr const ANY_ADDR = { INADDR_ANY };
 
 /* Data Structures
 
@@ -402,6 +401,13 @@
 
 void		SctpShowAliasStats(struct libalias *la);
 
+static u_int
+StartPartialIn(u_short alias_port, int link_type)
+{
+	return (link_type == LINK_PPTP) ? 0
+	    : (alias_port % LINK_PARTIAL_SIZE);
+}
+
 static u_int
 StartPointIn(struct in_addr alias_addr,
     u_short alias_port,
@@ -833,6 +839,15 @@
 	TAILQ_INSERT_TAIL(&la->checkExpire, (*lnk), list_expire);
 }
 
+static inline struct alias_link *
+UseLink(struct libalias *la, struct alias_link *lnk)
+{
+	CleanupLink(la, &lnk);
+	if (lnk != NULL)
+		lnk->timestamp = LibAliasTime;
+	return (lnk);
+}
+
 static void
 DeleteLink(struct alias_link **plnk)
 {
@@ -1037,8 +1052,13 @@
 		LIST_INSERT_HEAD(&la->linkTableOut[start_point], lnk, list_out);
 
 		/* Set up pointers for input lookup table */
-		start_point = StartPointIn(alias_addr, lnk->alias_port, link_type);
-		LIST_INSERT_HEAD(&la->linkTableIn[start_point], lnk, list_in);
+		if (lnk->flags & LINK_PARTIALLY_SPECIFIED) {
+			start_point = StartPartialIn(lnk->alias_port, link_type);
+			LIST_INSERT_HEAD(&la->linkPartialIn[start_point], lnk, list_in);
+		} else {
+			start_point = StartPointIn(alias_addr, lnk->alias_port, link_type);
+			LIST_INSERT_HEAD(&la->linkTableIn[start_point], lnk, list_in);
+		}
 
 		/* Include the element into the housekeeping list */
 		TAILQ_INSERT_TAIL(&la->checkExpire, lnk, list_expire);
@@ -1086,46 +1106,62 @@
 	return (new_lnk);
 }
 
+
+#define OUTGUARD					\
+   if (lnk->src_port != src_port ||			\
+       lnk->src_addr.s_addr != src_addr.s_addr ||	\
+       lnk->dst_addr.s_addr != dst_addr.s_addr ||	\
+       lnk->dst_port != dst_port ||			\
+       lnk->link_type != link_type ||			\
+       lnk->server != NULL)				\
+	   continue;
+
 static struct alias_link *
-_FindLinkOut(struct libalias *la, struct in_addr src_addr,
+_SearchLinkOut(struct libalias *la, struct in_addr src_addr,
     struct in_addr dst_addr,
     u_short src_port,
     u_short dst_port,
-    int link_type,
-    int replace_partial_links)
-{
+    int link_type) {
 	u_int i;
 	struct alias_link *lnk;
 
-	LIBALIAS_LOCK_ASSERT(la);
 	i = StartPointOut(src_addr, dst_addr, src_port, dst_port, link_type);
 	LIST_FOREACH(lnk, &la->linkTableOut[i], list_out) {
-		if (lnk->dst_addr.s_addr == dst_addr.s_addr &&
-		    lnk->src_addr.s_addr == src_addr.s_addr &&
-		    lnk->src_port == src_port &&
-		    lnk->dst_port == dst_port &&
-		    lnk->link_type == link_type &&
-		    lnk->server == NULL)
-			break;
+		OUTGUARD;
+		return (UseLink(la, lnk));
 	}
 
-	CleanupLink(la, &lnk);
-	if (lnk != NULL)
-		lnk->timestamp = LibAliasTime;
+	return (NULL);
+}
+
+#undef OUTGUARD
+
+static struct alias_link *
+_FindLinkOut(struct libalias *la, struct in_addr src_addr,
+    struct in_addr dst_addr,
+    u_short src_port,
+    u_short dst_port,
+    int link_type,
+    int replace_partial_links)
+{
+	struct alias_link *lnk;
+
+	LIBALIAS_LOCK_ASSERT(la);
+	lnk = _SearchLinkOut(la, src_addr, dst_addr, src_port, dst_port, link_type);
 
 	/* Search for partially specified links. */
 	if (lnk == NULL && replace_partial_links) {
 		if (dst_port != 0 && dst_addr.s_addr != INADDR_ANY) {
-			lnk = _FindLinkOut(la, src_addr, dst_addr, src_port, 0,
-			    link_type, 0);
+			lnk = _SearchLinkOut(la, src_addr, dst_addr, src_port, 0,
+			    link_type);
 			if (lnk == NULL)
-				lnk = _FindLinkOut(la, src_addr, NO_ADDR, src_port,
-				    dst_port, link_type, 0);
+				lnk = _SearchLinkOut(la, src_addr, ANY_ADDR, src_port,
+				    dst_port, link_type);
 		}
 		if (lnk == NULL &&
 		    (dst_port != 0 || dst_addr.s_addr != INADDR_ANY)) {
-			lnk = _FindLinkOut(la, src_addr, NO_ADDR, src_port, 0,
-			    link_type, 0);
+			lnk = _SearchLinkOut(la, src_addr, ANY_ADDR, src_port, 0,
+			    link_type);
 		}
 		if (lnk != NULL) {
 			lnk = ReLink(lnk,
@@ -1160,7 +1196,7 @@
 		 */
 		if (la->aliasAddress.s_addr != INADDR_ANY &&
 		    src_addr.s_addr == la->aliasAddress.s_addr) {
-			lnk = _FindLinkOut(la, NO_ADDR, dst_addr, src_port, dst_port,
+			lnk = _FindLinkOut(la, ANY_ADDR, dst_addr, src_port, dst_port,
 			    link_type, replace_partial_links);
 		}
 	}
@@ -1182,6 +1218,8 @@
 	struct alias_link *lnk_unknown_all;
 	struct alias_link *lnk_unknown_dst_addr;
 	struct alias_link *lnk_unknown_dst_port;
+	struct in_addr src_addr;
+	u_short src_port;
 
 	LIBALIAS_LOCK_ASSERT(la);
 	/* Initialize pointers */
@@ -1198,80 +1236,92 @@
 	if (dst_port == 0)
 		flags_in |= LINK_UNKNOWN_DEST_PORT;
 
+#define INGUARD						\
+   if (lnk->alias_port != alias_port ||			\
+       lnk->link_type != link_type ||			\
+       lnk->alias_addr.s_addr != alias_addr.s_addr)	\
+	continue;
+
 	/* Search loop */
 	start_point = StartPointIn(alias_addr, alias_port, link_type);
-	LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
-		int flags;
-
-		flags = flags_in | lnk->flags;
-		if (!(flags & LINK_PARTIALLY_SPECIFIED)) {
-			if (lnk->alias_addr.s_addr == alias_addr.s_addr
-			    && lnk->alias_port == alias_port
-			    && lnk->dst_addr.s_addr == dst_addr.s_addr
-			    && lnk->dst_port == dst_port
-			    && lnk->link_type == link_type) {
-				lnk_fully_specified = lnk;
+	switch (flags_in) {
+	case 0:
+		LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
+			INGUARD;
+			if (lnk->dst_addr.s_addr == dst_addr.s_addr &&
+			    lnk->dst_port == dst_port)
+				return (UseLink(la, lnk));
+		}
+		break;
+	case LINK_UNKNOWN_DEST_PORT:
+		LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
+			INGUARD;
+			if(lnk->dst_addr.s_addr == dst_addr.s_addr) {
+				lnk_unknown_dst_port = lnk;
 				break;
 			}
-		} else if ((flags & LINK_UNKNOWN_DEST_ADDR)
-		    && (flags & LINK_UNKNOWN_DEST_PORT)) {
-			if (lnk->alias_addr.s_addr == alias_addr.s_addr
-			    && lnk->alias_port == alias_port
-			    && lnk->link_type == link_type) {
-				if (lnk_unknown_all == NULL)
-					lnk_unknown_all = lnk;
-			}
-		} else if (flags & LINK_UNKNOWN_DEST_ADDR) {
-			if (lnk->alias_addr.s_addr == alias_addr.s_addr
-			    && lnk->alias_port == alias_port
-			    && lnk->link_type == link_type
-			    && lnk->dst_port == dst_port) {
-				if (lnk_unknown_dst_addr == NULL)
-					lnk_unknown_dst_addr = lnk;
+		}
+		break;
+	case LINK_UNKNOWN_DEST_ADDR:
+		LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
+			INGUARD;
+			if(lnk->dst_port == dst_port) {
+				lnk_unknown_dst_addr = lnk;
+				break;
 			}
-		} else if (flags & LINK_UNKNOWN_DEST_PORT) {
-			if (lnk->alias_addr.s_addr == alias_addr.s_addr
-			    && lnk->alias_port == alias_port
-			    && lnk->link_type == link_type
-			    && lnk->dst_addr.s_addr == dst_addr.s_addr) {
-				if (lnk_unknown_dst_port == NULL)
-					lnk_unknown_dst_port = lnk;
+		}
+		break;
+	case LINK_PARTIALLY_SPECIFIED:
+		LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
+			INGUARD;
+			lnk_unknown_all = lnk;
+			break;
+		}
+		break;
+	}
+
+	if (lnk_unknown_dst_port == NULL) {
+		start_point = StartPartialIn(alias_port, link_type);
+		LIST_FOREACH(lnk, &la->linkPartialIn[start_point], list_in) {
+			int flags = (flags_in | lnk->flags) & LINK_PARTIALLY_SPECIFIED;
+
+			INGUARD;
+			if (flags == LINK_PARTIALLY_SPECIFIED &&
+			    lnk_unknown_all == NULL)
+				lnk_unknown_all = lnk;
+			if (flags == LINK_UNKNOWN_DEST_ADDR &&
+			    lnk->dst_port == dst_port &&
+			    lnk_unknown_dst_addr == NULL)
+				lnk_unknown_dst_addr = lnk;
+			if (flags == LINK_UNKNOWN_DEST_PORT &&
+			    lnk->dst_addr.s_addr == dst_addr.s_addr) {
+				lnk_unknown_dst_port = lnk;
+				break;
 			}
 		}
 	}
+#undef INGUARD
 
-	CleanupLink(la, &lnk_fully_specified);
-	if (lnk_fully_specified != NULL) {
-		lnk_fully_specified->timestamp = LibAliasTime;
-		lnk = lnk_fully_specified;
-	} else if (lnk_unknown_dst_port != NULL)
-		lnk = lnk_unknown_dst_port;
-	else if (lnk_unknown_dst_addr != NULL)
-		lnk = lnk_unknown_dst_addr;
-	else if (lnk_unknown_all != NULL)
-		lnk = lnk_unknown_all;
-	else
-		return (NULL);
+	lnk = (lnk_unknown_dst_port != NULL) ? lnk_unknown_dst_port
+	    : (lnk_unknown_dst_addr != NULL) ? lnk_unknown_dst_addr
+	    : lnk_unknown_all;
 
-	if (replace_partial_links &&
-	    (lnk->flags & LINK_PARTIALLY_SPECIFIED || lnk->server != NULL)) {
-		struct in_addr src_addr;
-		u_short src_port;
+	if (lnk == NULL || !replace_partial_links)
+		return (lnk);
 
-		if (lnk->server != NULL) {	/* LSNAT link */
-			src_addr = lnk->server->addr;
-			src_port = lnk->server->port;
-			lnk->server = lnk->server->next;
-		} else {
-			src_addr = lnk->src_addr;
-			src_port = lnk->src_port;
-		}
+	if (lnk->server != NULL) {	/* LSNAT link */
+		src_addr = lnk->server->addr;
+		src_port = lnk->server->port;
+		lnk->server = lnk->server->next;
+	} else {
+		src_addr = lnk->src_addr;
+		src_port = lnk->src_port;
+	}
 
-		if (link_type == LINK_SCTP) {
-			lnk->src_addr = src_addr;
-			lnk->src_port = src_port;
-			return (lnk);
-		}
+	if (link_type == LINK_SCTP) {
+		lnk->src_addr = src_addr;
+		lnk->src_port = src_port;
+	} else {
 		lnk = ReLink(lnk,
 		    src_addr, dst_addr, alias_addr,
 		    src_port, dst_port, alias_port,
@@ -1303,7 +1353,7 @@
 		 */
 		if (la->aliasAddress.s_addr != INADDR_ANY &&
 		    alias_addr.s_addr == la->aliasAddress.s_addr) {
-			lnk = _FindLinkIn(la, dst_addr, NO_ADDR, dst_port, alias_port,
+			lnk = _FindLinkIn(la, dst_addr, ANY_ADDR, dst_port, alias_port,
 			    link_type, replace_partial_links);
 		}
 	}
@@ -1385,7 +1435,7 @@
 	    LINK_FRAGMENT_ID, 0);
 
 	if (lnk == NULL) {
-		lnk = AddLink(la, NO_ADDR, dst_addr, alias_addr,
+		lnk = AddLink(la, ANY_ADDR, dst_addr, alias_addr,
 		    NO_SRC_PORT, NO_DEST_PORT, ip_id,
 		    LINK_FRAGMENT_ID);
 	}
@@ -1408,7 +1458,7 @@
     u_short ip_id)
 {
 	LIBALIAS_LOCK_ASSERT(la);
-	return AddLink(la, NO_ADDR, dst_addr, NO_ADDR,
+	return AddLink(la, ANY_ADDR, dst_addr, ANY_ADDR,
 	    NO_SRC_PORT, NO_DEST_PORT, ip_id,
 	    LINK_FRAGMENT_PTR);
 }
@@ -1418,7 +1468,7 @@
     u_short ip_id)
 {
 	LIBALIAS_LOCK_ASSERT(la);
-	return FindLinkIn(la, dst_addr, NO_ADDR,
+	return FindLinkIn(la, dst_addr, ANY_ADDR,
 	    NO_DEST_PORT, ip_id,
 	    LINK_FRAGMENT_PTR, 0);
 }
@@ -1608,12 +1658,10 @@
     struct in_addr alias_addr,
     u_int16_t dst_call_id)
 {
-	u_int i;
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	i = StartPointIn(alias_addr, 0, LINK_PPTP);
-	LIST_FOREACH(lnk, &la->linkTableIn[i], list_in)
+	LIST_FOREACH(lnk, &la->linkPartialIn[0], list_in)
 		if (lnk->link_type == LINK_PPTP &&
 		    lnk->dst_addr.s_addr == dst_addr.s_addr &&
 		    lnk->alias_addr.s_addr == alias_addr.s_addr &&
@@ -1681,7 +1729,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	lnk = FindLinkIn(la, NO_ADDR, alias_addr,
+	lnk = FindLinkIn(la, ANY_ADDR, alias_addr,
 	    0, 0, LINK_ADDR, 0);
 	if (lnk == NULL) {
 		la->newDefaultLink = 1;
@@ -1713,7 +1761,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	lnk = FindLinkOut(la, original_addr, NO_ADDR,
+	lnk = FindLinkOut(la, original_addr, ANY_ADDR,
 	    0, 0, LINK_ADDR, 0);
 	if (lnk == NULL) {
 		return (la->aliasAddress.s_addr != INADDR_ANY) ?
@@ -2321,7 +2369,7 @@
 	struct alias_link *lnk;
 
 	LIBALIAS_LOCK(la);
-	lnk = AddLink(la, src_addr, NO_ADDR, alias_addr,
+	lnk = AddLink(la, src_addr, ANY_ADDR, alias_addr,
 	    0, 0, 0,
 	    LINK_ADDR);
 
@@ -2440,6 +2488,8 @@
 			LIST_INIT(&la->linkTableOut[i]);
 		for (i = 0; i < LINK_TABLE_IN_SIZE; i++)
 			LIST_INIT(&la->linkTableIn[i]);
+		for (i = 0; i < LINK_PARTIAL_SIZE; i++)
+			LIST_INIT(&la->linkPartialIn[i]);
 		TAILQ_INIT(&la->checkExpire);
 #ifdef _KERNEL
 		AliasSctpInit(la);
Index: sys/netinet/libalias/alias_local.h
===================================================================
--- sys/netinet/libalias/alias_local.h
+++ sys/netinet/libalias/alias_local.h
@@ -68,6 +68,7 @@
 /* Sizes of input and output link tables */
 #define LINK_TABLE_OUT_SIZE	4001
 #define LINK_TABLE_IN_SIZE	4001
+#define LINK_PARTIAL_SIZE	401
 
 #define	GET_ALIAS_PORT		-1
 #define	GET_ALIAS_ID		GET_ALIAS_PORT
@@ -94,6 +95,7 @@
 	 * output lookup tables. */
 	LIST_HEAD     (, alias_link) linkTableOut[LINK_TABLE_OUT_SIZE];
 	LIST_HEAD     (, alias_link) linkTableIn[LINK_TABLE_IN_SIZE];
+	LIST_HEAD     (, alias_link) linkPartialIn[LINK_PARTIAL_SIZE];
 	/* HouseKeeping */
 	TAILQ_HEAD    (, alias_link) checkExpire;
 	/* Link statistics */