Index: sys/netinet/libalias/alias_db.c
===================================================================
--- sys/netinet/libalias/alias_db.c
+++ sys/netinet/libalias/alias_db.c
@@ -176,17 +176,13 @@
 #endif
 
 static LIST_HEAD(, libalias) instancehead = LIST_HEAD_INITIALIZER(instancehead);
+int LibAliasTime;
 
 /*
    Constants (note: constants are also defined
 	      near relevant functions or structs)
 */
 
-/* Parameters used for cleanup of expired links */
-/* NOTE: ALIAS_CLEANUP_INTERVAL_SECS must be less then LINK_TABLE_OUT_SIZE */
-#define ALIAS_CLEANUP_INTERVAL_SECS  64
-#define ALIAS_CLEANUP_MAX_SPOKES     (LINK_TABLE_OUT_SIZE/5)
-
 /* Timeouts (in seconds) for different link types */
 #define ICMP_EXPIRE_TIME             60
 #define UDP_EXPIRE_TIME              60
@@ -330,6 +326,7 @@
 	/* Linked list of pointers for input and output lookup tables  */
 	LIST_ENTRY    (alias_link) list_out;
 	LIST_ENTRY    (alias_link) list_in;
+	TAILQ_ENTRY   (alias_link) list_expire;
 	/* Auxiliary data */
 	union {
 		char           *frag_ptr;
@@ -511,7 +508,7 @@
 
 Link creation and deletion:
     CleanupAliasData()      - remove all link chains from lookup table
-    IncrementalCleanup()    - look for stale links in a single chain
+    CleanupLink()           - look for a stale link
     DeleteLink()            - remove link
     AddLink()               - add link
     ReLink()                - change link
@@ -530,8 +527,8 @@
 static u_short	GetSocket(struct libalias *, u_short, int *, int);
 #endif
 static void	CleanupAliasData(struct libalias *);
-static void	IncrementalCleanup(struct libalias *);
-static void	DeleteLink(struct alias_link *);
+static void	CleanupLink(struct libalias *, struct alias_link **);
+static void	DeleteLink(struct alias_link **);
 
 static struct alias_link *
 ReLink(struct alias_link *,
@@ -808,41 +805,38 @@
 static void
 CleanupAliasData(struct libalias *la)
 {
-	struct alias_link *lnk;
-	int i;
+	struct alias_link *lnk, *lnk_tmp;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	for (i = 0; i < LINK_TABLE_OUT_SIZE; i++) {
-		lnk = LIST_FIRST(&la->linkTableOut[i]);
-		while (lnk != NULL) {
-			struct alias_link *link_next = LIST_NEXT(lnk, list_out);
-			DeleteLink(lnk);
-			lnk = link_next;
-		}
-	}
 
-	la->cleanupIndex = 0;
+	/* permanent entries may stay */
+	TAILQ_FOREACH_SAFE(lnk, &la->checkExpire, list_expire, lnk_tmp)
+		DeleteLink(&lnk);
 }
 
 static void
-IncrementalCleanup(struct libalias *la)
+CleanupLink(struct libalias *la, struct alias_link **lnk)
 {
-	struct alias_link *lnk, *lnk_tmp;
-
 	LIBALIAS_LOCK_ASSERT(la);
-	LIST_FOREACH_SAFE(lnk, &la->linkTableOut[la->cleanupIndex++],
-	    list_out, lnk_tmp) {
-		if (la->timeStamp - lnk->timestamp > lnk->expire_time)
-			DeleteLink(lnk);
+
+	if (lnk == NULL || *lnk == NULL)
+		return;
+
+	if (LibAliasTime - (*lnk)->timestamp > (*lnk)->expire_time) {
+		DeleteLink(lnk);
+		if ((*lnk) == NULL)
+			return;
 	}
 
-	if (la->cleanupIndex == LINK_TABLE_OUT_SIZE)
-		la->cleanupIndex = 0;
+	/* move to end, swap may fail on a single entry list */
+	TAILQ_REMOVE(&la->checkExpire, (*lnk), list_expire);
+	TAILQ_INSERT_TAIL(&la->checkExpire, (*lnk), list_expire);
 }
 
 static void
-DeleteLink(struct alias_link *lnk)
+DeleteLink(struct alias_link **plnk)
 {
+	struct alias_link *lnk = *plnk;
 	struct libalias *la = lnk->la;
 
 	LIBALIAS_LOCK_ASSERT(la);
@@ -870,6 +864,10 @@
 
 	/* Adjust input table pointers */
 	LIST_REMOVE(lnk, list_in);
+
+	/* remove from housekeeping */
+	TAILQ_REMOVE(&la->checkExpire, lnk, list_expire);
+
 #ifndef NO_USE_SOCKETS
 	/* Close socket, if one has been allocated */
 	if (lnk->sockfd != -1) {
@@ -909,6 +907,7 @@
 
 	/* Free memory */
 	free(lnk);
+	*plnk = NULL;
 
 	/* Write statistics, if logging enabled */
 	if (la->packetAliasMode & PKT_ALIAS_LOG) {
@@ -943,7 +942,7 @@
 #endif
 		lnk->flags = 0;
 		lnk->pflags = 0;
-		lnk->timestamp = la->timeStamp;
+		lnk->timestamp = LibAliasTime;
 
 		/* Expiration time */
 		switch (link_type) {
@@ -1040,6 +1039,9 @@
 		/* 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);
+
+		/* Include the element into the housekeeping list */
+		TAILQ_INSERT_TAIL(&la->checkExpire, lnk, list_expire);
 	} else {
 #ifdef LIBALIAS_DEBUG
 		fprintf(stderr, "PacketAlias/AddLink(): ");
@@ -1080,7 +1082,7 @@
 		PunchFWHole(new_lnk);
 	}
 #endif
-	DeleteLink(old_lnk);
+	DeleteLink(&old_lnk);
 	return (new_lnk);
 }
 
@@ -1103,12 +1105,14 @@
 		    lnk->src_port == src_port &&
 		    lnk->dst_port == dst_port &&
 		    lnk->link_type == link_type &&
-		    lnk->server == NULL) {
-			lnk->timestamp = la->timeStamp;
+		    lnk->server == NULL)
 			break;
-		}
 	}
 
+	CleanupLink(la, &lnk);
+	if (lnk != NULL)
+		lnk->timestamp = LibAliasTime;
+
 	/* Search for partially specified links. */
 	if (lnk == NULL && replace_partial_links) {
 		if (dst_port != 0 && dst_addr.s_addr != INADDR_ANY) {
@@ -1236,8 +1240,9 @@
 		}
 	}
 
+	CleanupLink(la, &lnk_fully_specified);
 	if (lnk_fully_specified != NULL) {
-		lnk_fully_specified->timestamp = la->timeStamp;
+		lnk_fully_specified->timestamp = LibAliasTime;
 		lnk = lnk_fully_specified;
 	} else if (lnk_unknown_dst_port != NULL)
 		lnk = lnk_unknown_dst_port;
@@ -1573,6 +1578,7 @@
 		    lnk->src_port == src_call_id)
 			break;
 
+	CleanupLink(la, &lnk);
 	return (lnk);
 }
 
@@ -1593,6 +1599,7 @@
 		    lnk->dst_port == dst_call_id)
 			break;
 
+	CleanupLink(la, &lnk);
 	return (lnk);
 }
 
@@ -1613,6 +1620,7 @@
 		    lnk->dst_port == dst_call_id)
 			break;
 
+	CleanupLink(la, &lnk);
 	return (lnk);
 }
 
@@ -2040,7 +2048,7 @@
 {
 	if (expire == 0) {
 		lnk->flags &= ~LINK_PERMANENT;
-		DeleteLink(lnk);
+		DeleteLink(&lnk);
 	} else if (expire == -1) {
 		lnk->flags |= LINK_PERMANENT;
 	} else if (expire > 0) {
@@ -2103,42 +2111,34 @@
 void
 HouseKeeping(struct libalias *la)
 {
-	int i, n;
-#ifndef _KERNEL
-	struct timeval tv;
-#endif
+	struct alias_link * lnk = TAILQ_FIRST(&la->checkExpire);
+	static int packets = 0;
+
+	/*
+	 * User space time/gettimeofday/... is very expensive.
+	 * Kernel space cache trashing is unnecessary.
+	 *
+	 * Reduce the amount of house keeping work substantially by
+	 * sampling over the packets.
+	 *
+	 * TODO: choose a dynamic sampling interval.
+	 */
+	if (packets++ < 1000)
+		return;
+	packets = 0;
 
 	LIBALIAS_LOCK_ASSERT(la);
 	/*
-	 * Save system time (seconds) in global variable timeStamp for use
-	 * by other functions. This is done so as not to unnecessarily
-	 * waste timeline by making system calls.
+	 * Save system time (seconds) in global variable LibAliasTime
+	 * for use by other functions. This is done so as not to
+	 * unnecessarily waste timeline by making system calls.
 	 */
 #ifdef _KERNEL
-	la->timeStamp = time_uptime;
+	LibAliasTime = time_uptime;
 #else
-	gettimeofday(&tv, NULL);
-	la->timeStamp = tv.tv_sec;
-#endif
-
-	/* Compute number of spokes (output table link chains) to cover */
-	n = LINK_TABLE_OUT_SIZE * (la->timeStamp - la->lastCleanupTime);
-	n /= ALIAS_CLEANUP_INTERVAL_SECS;
-
-	/* Handle different cases */
-	if (n > 0) {
-		if (n > ALIAS_CLEANUP_MAX_SPOKES)
-			n = ALIAS_CLEANUP_MAX_SPOKES;
-		la->lastCleanupTime = la->timeStamp;
-		for (i = 0; i < n; i++)
-			IncrementalCleanup(la);
-	} else if (n < 0) {
-#ifdef LIBALIAS_DEBUG
-		fprintf(stderr, "PacketAlias/HouseKeeping(): ");
-		fprintf(stderr, "something unexpected in time values\n");
+	LibAliasTime = time(NULL);
 #endif
-		la->lastCleanupTime = la->timeStamp;
-	}
+	CleanupLink(la, &lnk);
 }
 
 /* Init the log file and enable logging */
@@ -2365,7 +2365,7 @@
 {
 	LIBALIAS_LOCK(la);
 	la->deleteAllLinks = 1;
-	DeleteLink(lnk);
+	DeleteLink(&lnk);
 	la->deleteAllLinks = 0;
 	LIBALIAS_UNLOCK(la);
 }
@@ -2412,9 +2412,6 @@
 LibAliasInit(struct libalias *la)
 {
 	int i;
-#ifndef _KERNEL
-	struct timeval tv;
-#endif
 
 	if (la == NULL) {
 #ifdef _KERNEL
@@ -2434,18 +2431,16 @@
 		LIST_INSERT_HEAD(&instancehead, la, instancelist);
 
 #ifdef _KERNEL
-		la->timeStamp = time_uptime;
-		la->lastCleanupTime = time_uptime;
+		LibAliasTime = time_uptime;
 #else
-		gettimeofday(&tv, NULL);
-		la->timeStamp = tv.tv_sec;
-		la->lastCleanupTime = tv.tv_sec;
+		LibAliasTime = time(NULL);
 #endif
 
 		for (i = 0; i < LINK_TABLE_OUT_SIZE; i++)
 			LIST_INIT(&la->linkTableOut[i]);
 		for (i = 0; i < LINK_TABLE_IN_SIZE; i++)
 			LIST_INIT(&la->linkTableIn[i]);
+		TAILQ_INIT(&la->checkExpire);
 #ifdef _KERNEL
 		AliasSctpInit(la);
 #endif
Index: sys/netinet/libalias/alias_local.h
===================================================================
--- sys/netinet/libalias/alias_local.h
+++ sys/netinet/libalias/alias_local.h
@@ -94,6 +94,8 @@
 	 * output lookup tables. */
 	LIST_HEAD     (, alias_link) linkTableOut[LINK_TABLE_OUT_SIZE];
 	LIST_HEAD     (, alias_link) linkTableIn[LINK_TABLE_IN_SIZE];
+	/* HouseKeeping */
+	TAILQ_HEAD    (, alias_link) checkExpire;
 	/* Link statistics */
 	int		icmpLinkCount;
 	int		udpLinkCount;
@@ -105,10 +107,6 @@
 	int		sockCount;
 	/* Index to chain of link table being inspected for old links   */
 	int		cleanupIndex;
-	/* System time in seconds for current packet */
-	int		timeStamp;
-	/* Last time IncrementalCleanup() was called */
-	int		lastCleanupTime;
 	/* If equal to zero, DeleteLink()
 	 * will not remove permanent links */
 	int		deleteAllLinks;
@@ -211,6 +209,9 @@
 
 /* Prototypes */
 
+/* System time in seconds for current packet */
+extern int LibAliasTime;
+
 /*
  * SctpFunction prototypes
  *
Index: sys/netinet/libalias/alias_sctp.c
===================================================================
--- sys/netinet/libalias/alias_sctp.c
+++ sys/netinet/libalias/alias_sctp.c
@@ -298,10 +298,10 @@
 #define SN_MAX_TIMER 600
 #define SN_TIMER_QUEUE_SIZE SN_MAX_TIMER+2
 
-#define SN_I_T(la) (la->timeStamp + sysctl_init_timer)       /**< INIT State expiration time in seconds */
-#define SN_U_T(la) (la->timeStamp + sysctl_up_timer)         /**< UP State expiration time in seconds */
-#define SN_C_T(la) (la->timeStamp + sysctl_shutdown_timer)   /**< CL State expiration time in seconds */
-#define SN_X_T(la) (la->timeStamp + sysctl_holddown_timer)   /**< Wait after a shutdown complete in seconds */
+#define SN_I_T(la) (LibAliasTime + sysctl_init_timer)       /**< INIT State expiration time in seconds */
+#define SN_U_T(la) (LibAliasTime + sysctl_up_timer)         /**< UP State expiration time in seconds */
+#define SN_C_T(la) (LibAliasTime + sysctl_shutdown_timer)   /**< CL State expiration time in seconds */
+#define SN_X_T(la) (LibAliasTime + sysctl_holddown_timer)   /**< Wait after a shutdown complete in seconds */
 /** @}
  * @defgroup sysctl SysCtl Variable and callback function declarations
  *
@@ -667,9 +667,9 @@
 	for (i = 0; i < SN_TIMER_QUEUE_SIZE; i++)
 		LIST_INIT(&la->sctpNatTimer.TimerQ[i]);
 #ifdef _KERNEL
-	la->sctpNatTimer.loc_time=time_uptime; /* la->timeStamp is not set yet */
+	la->sctpNatTimer.loc_time=time_uptime; /* LibAliasTime is not set yet */
 #else
-	la->sctpNatTimer.loc_time=la->timeStamp;
+	la->sctpNatTimer.loc_time=LibAliasTime;
 #endif
 	la->sctpNatTimer.cur_loc = 0;
 	la->sctpLinkCount = 0;
@@ -2493,12 +2493,12 @@
 	struct sctp_nat_assoc *assoc;
 
 	LIBALIAS_LOCK_ASSERT(la);
-	while(la->timeStamp >= la->sctpNatTimer.loc_time) {
+	while(LibAliasTime >= la->sctpNatTimer.loc_time) {
 		while (!LIST_EMPTY(&la->sctpNatTimer.TimerQ[la->sctpNatTimer.cur_loc])) {
 			assoc = LIST_FIRST(&la->sctpNatTimer.TimerQ[la->sctpNatTimer.cur_loc]);
 			//SLIST_REMOVE_HEAD(&la->sctpNatTimer.TimerQ[la->sctpNatTimer.cur_loc], timer_Q);
 			LIST_REMOVE(assoc, timer_Q);
-			if (la->timeStamp >= assoc->exp) { /* state expired */
+			if (LibAliasTime >= assoc->exp) { /* state expired */
 				SN_LOG(((assoc->state == SN_CL) ? (SN_LOG_DEBUG) : (SN_LOG_INFO)),
 				    logsctperror("Timer Expired", assoc->g_vtag, assoc->state, SN_TO_NODIR));
 				RmSctpAssoc(la, assoc);