Index: sys/netinet/libalias/alias_db.c
===================================================================
--- sys/netinet/libalias/alias_db.c
+++ sys/netinet/libalias/alias_db.c
@@ -219,9 +219,10 @@
 #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 };
+/* Never matches a real address.  Address is known to be ignored. */
+static struct in_addr const NO_ADDR = { 0xfffeefff };
 
 /* Data Structures
 
@@ -1033,14 +1034,21 @@
 			break;
 		}
 
-		/* Set up pointers for output lookup table */
-		start_point = StartPointOut(src_addr, dst_addr,
-		    src_port, dst_port, link_type);
-		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);
+		/* Set up pointers for lookup tables */
+		if (lnk->flags & LINK_PARTIALLY_SPECIFIED) {
+			LIST_INSERT_HEAD(&la->linkPartialOut, lnk, list_out);
+			LIST_INSERT_HEAD(&la->linkPartialIn, lnk, list_in);
+		} else {
+			start_point = StartPointOut(src_addr, dst_addr,
+			    src_port, dst_port, link_type);
+			LIST_INSERT_HEAD(&la->linkTableOut[start_point],
+			    lnk, list_out);
+
+			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);
@@ -1098,41 +1106,59 @@
 {
 	u_int i;
 	struct alias_link *lnk;
+	struct alias_link *lnk_addr = NULL;
+	struct alias_link *lnk_port = NULL;
+	struct alias_link *lnk_any = NULL;
 
 	LIBALIAS_LOCK_ASSERT(la);
+
+#define OUTGUARD					\
+	if (lnk->src_port != src_port ||		\
+	    lnk->src_addr.s_addr != src_addr.s_addr ||	\
+	    lnk->link_type != link_type ||		\
+	    lnk->server != NULL)			\
+		continue;
+
 	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) {
+		OUTGUARD;
+
+		if (lnk->dst_port == dst_port &&
+		    lnk->dst_addr.s_addr == dst_addr.s_addr) {
 			lnk->timestamp = la->timeStamp;
-			break;
+			return (lnk);
 		}
 	}
 
+	if (!replace_partial_links)
+		return (lnk);
+
 	/* 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);
-			if (lnk == NULL)
-				lnk = _FindLinkOut(la, src_addr, NO_ADDR, src_port,
-				    dst_port, link_type, 0);
-		}
-		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);
-		}
-		if (lnk != NULL) {
-			lnk = ReLink(lnk,
-			    src_addr, dst_addr, lnk->alias_addr,
-			    src_port, dst_port, lnk->alias_port,
-			    link_type);
+	LIST_FOREACH(lnk, &la->linkPartialOut, list_out) {
+		OUTGUARD;
+
+		if (lnk->dst_addr.s_addr == dst_addr.s_addr && lnk->dst_port == 0) {
+			lnk_addr = lnk;
+			break;
 		}
+
+		if (lnk->dst_addr.s_addr == INADDR_ANY && lnk->dst_port == dst_port)
+			lnk_port = lnk;
+
+		if (lnk->dst_addr.s_addr == INADDR_ANY && lnk->dst_port == 0)
+			lnk_any = lnk;
+	}
+#undef OUTGUARD
+
+	lnk = (lnk_addr != NULL) ? lnk_addr
+	    : (lnk_port != NULL) ? lnk_port
+	    : lnk_any;
+
+	if (lnk != NULL) {
+		lnk = ReLink(lnk,
+		    src_addr, dst_addr, lnk->alias_addr,
+		    src_port, dst_port, lnk->alias_port,
+		    link_type);
 	}
 	return (lnk);
 }
@@ -1160,7 +1186,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);
 		}
 	}
@@ -1175,75 +1201,73 @@
     int link_type,
     int replace_partial_links)
 {
-	int flags_in;
+	int flags_in = 0;
 	u_int start_point;
 	struct alias_link *lnk;
-	struct alias_link *lnk_fully_specified;
-	struct alias_link *lnk_unknown_all;
-	struct alias_link *lnk_unknown_dst_addr;
-	struct alias_link *lnk_unknown_dst_port;
+	struct alias_link *lnk_unknown_all = NULL;
+	struct alias_link *lnk_unknown_dst_addr = NULL;
+	struct alias_link *lnk_unknown_dst_port = NULL;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	/* Initialize pointers */
-	lnk_fully_specified = NULL;
-	lnk_unknown_all = NULL;
-	lnk_unknown_dst_addr = NULL;
-	lnk_unknown_dst_port = NULL;
 
 	/* If either the dest addr or port is unknown, the search
 	 * loop will have to know about this. */
-	flags_in = 0;
 	if (dst_addr.s_addr == INADDR_ANY)
 		flags_in |= LINK_UNKNOWN_DEST_ADDR;
 	if (dst_port == 0)
 		flags_in |= LINK_UNKNOWN_DEST_PORT;
 
 	/* Search loop */
+#define INGUARD					\
+	if (lnk->alias_port != alias_port ||		\
+	    lnk->link_type != link_type ||		\
+	    lnk->alias_addr.s_addr != alias_addr.s_addr)\
+		continue;
+
+#define INPART(flags)	{				\
+	if ((flags & LINK_UNKNOWN_DEST_PORT) &&		\
+	    lnk->dst_addr.s_addr == dst_addr.s_addr &&	\
+	    lnk_unknown_dst_port == NULL) {		\
+		lnk_unknown_dst_port = lnk;		\
+		break;					\
+	}						\
+	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_ADDR) &&		\
+	    (flags & LINK_UNKNOWN_DEST_PORT) &&		\
+	    lnk_unknown_all == NULL)			\
+		lnk_unknown_all = lnk;			\
+}
+
 	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;
-				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;
-			}
-		} 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;
+	if (!(flags_in & LINK_PARTIALLY_SPECIFIED)) {
+		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) {
+				lnk->timestamp = la->timeStamp;
+				return (lnk);
 			}
 		}
+	} else {
+		LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) {
+			INGUARD;
+			INPART(flags_in);
+		}
+	}
+	if (lnk_unknown_dst_port == NULL) {
+		LIST_FOREACH(lnk, &la->linkPartialIn, list_in) {
+			INGUARD;
+			INPART(flags_in | lnk->flags);
+		}
 	}
+#undef INPART
+#undef INGUARD
 
-	if (lnk_fully_specified != NULL) {
-		lnk_fully_specified->timestamp = la->timeStamp;
-		lnk = lnk_fully_specified;
-	} else if (lnk_unknown_dst_port != NULL)
+	if (lnk_unknown_dst_port != NULL)
 		lnk = lnk_unknown_dst_port;
 	else if (lnk_unknown_dst_addr != NULL)
 		lnk = lnk_unknown_dst_addr;
@@ -1302,7 +1326,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);
 		}
 	}
@@ -1407,7 +1431,7 @@
     u_short ip_id)
 {
 	LIBALIAS_LOCK_ASSERT(la);
-	return AddLink(la, NO_ADDR, dst_addr, NO_ADDR,
+	return AddLink(la, NO_ADDR, dst_addr, ANY_ADDR,
 	    NO_SRC_PORT, NO_DEST_PORT, ip_id,
 	    LINK_FRAGMENT_PTR);
 }
@@ -1417,7 +1441,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);
 }
@@ -1677,7 +1701,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;
@@ -1709,7 +1733,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) ?
@@ -2306,7 +2330,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);
 
@@ -2429,6 +2453,8 @@
 			LIST_INIT(&la->linkTableOut[i]);
 		for (i = 0; i < LINK_TABLE_IN_SIZE; i++)
 			LIST_INIT(&la->linkTableIn[i]);
+		LIST_INIT(&la->linkPartialOut);
+		LIST_INIT(&la->linkPartialIn);
 		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
@@ -46,16 +46,17 @@
  */
 
 #ifndef _ALIAS_LOCAL_H_
-#define	_ALIAS_LOCAL_H_
+#define _ALIAS_LOCAL_H_
 
-#include <sys/types.h>
 #include <sys/sysctl.h>
+#include <sys/tree.h>
+#include <sys/types.h>
 
 #ifdef _KERNEL
-#include <sys/malloc.h>
-#include <sys/param.h>
 #include <sys/lock.h>
+#include <sys/malloc.h>
 #include <sys/mutex.h>
+#include <sys/param.h>
 
 /* XXX: LibAliasSetTarget() uses this constant. */
 #define	INADDR_NONE	0xffffffff
@@ -94,6 +95,8 @@
 	 * 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) linkPartialOut;
+	LIST_HEAD     (, alias_link) linkPartialIn;
 	/* HouseKeeping */
 	TAILQ_HEAD    (, alias_link) checkExpire;
 	/* Link statistics */