Index: sys/netinet/libalias/alias_db.c =================================================================== --- sys/netinet/libalias/alias_db.c +++ sys/netinet/libalias/alias_db.c @@ -182,11 +182,6 @@ 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 @@ -224,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 @@ -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 + IncrementalCleanup() - look for a stale link DeleteLink() - remove link AddLink() - add link ReLink() - change link @@ -531,7 +528,7 @@ #endif static void CleanupAliasData(struct libalias *); static void IncrementalCleanup(struct libalias *); -static void DeleteLink(struct alias_link *); +static void DeleteLink(struct alias_link **); static struct alias_link * ReLink(struct alias_link *, @@ -808,41 +805,41 @@ 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) { - struct alias_link *lnk, *lnk_tmp; + struct alias_link *lnk; 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); + + lnk = TAILQ_FIRST(&la->checkExpire); + if (lnk == NULL) + return; + + if (la->timeStamp - 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 +867,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 +910,7 @@ /* Free memory */ free(lnk); + *plnk = NULL; /* Write statistics, if logging enabled */ if (la->packetAliasMode & PKT_ALIAS_LOG) { @@ -1032,14 +1034,23 @@ 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 lookup tables */ + if (lnk->flags & LINK_PARTIALLY_SPECIFIED) { + LIST_INSERT_HEAD(&la->linkPartial, lnk, list_out); + } 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); + } - /* 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 +1091,7 @@ PunchFWHole(new_lnk); } #endif - DeleteLink(old_lnk); + DeleteLink(&old_lnk); return (new_lnk); } @@ -1094,8 +1105,12 @@ { 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); + 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 && @@ -1105,30 +1120,42 @@ lnk->link_type == link_type && lnk->server == NULL) { 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->linkPartial, list_out) { + if (lnk->src_port != src_port || + lnk->src_addr.s_addr != src_addr.s_addr || + lnk->link_type != link_type || + lnk->server != NULL) + continue; + + 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; + } + + 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); } @@ -1156,7 +1183,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); } } @@ -1171,75 +1198,67 @@ 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 */ - start_point = StartPointIn(alias_addr, alias_port, link_type); - LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) { - int flags; +#define INCMP(f) { \ + int flags = f; \ + \ + if (lnk->alias_port != alias_port || \ + lnk->link_type != link_type || \ + lnk->alias_addr.s_addr != alias_addr.s_addr)\ + continue; \ + \ + if ((flags & LINK_UNKNOWN_DEST_ADDR) && \ + (flags & LINK_UNKNOWN_DEST_PORT) && \ + 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 == NULL) \ + lnk_unknown_dst_port = lnk; \ +} - flags = flags_in | lnk->flags; - if (!(flags & LINK_PARTIALLY_SPECIFIED)) { + start_point = StartPointIn(alias_addr, alias_port, link_type); + if (!(flags_in & LINK_PARTIALLY_SPECIFIED)) { + LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) 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; + lnk->timestamp = la->timeStamp; + return (lnk); } - } + } else { + LIST_FOREACH(lnk, &la->linkTableIn[start_point], list_in) + INCMP(flags_in); } + LIST_FOREACH(lnk, &la->linkPartial, list_in) + INCMP(flags_in | lnk->flags); +#undef INCMP - 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; @@ -1298,7 +1317,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); } } @@ -1403,7 +1422,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); } @@ -1413,7 +1432,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); } @@ -1673,7 +1692,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; @@ -1705,7 +1724,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) ? @@ -2040,7 +2059,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,7 +2122,6 @@ void HouseKeeping(struct libalias *la) { - int i, n; #ifndef _KERNEL struct timeval tv; #endif @@ -2120,25 +2138,7 @@ 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"); -#endif - la->lastCleanupTime = la->timeStamp; - } + IncrementalCleanup(la); } /* Init the log file and enable logging */ @@ -2321,7 +2321,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); @@ -2365,7 +2365,7 @@ { LIBALIAS_LOCK(la); la->deleteAllLinks = 1; - DeleteLink(lnk); + DeleteLink(&lnk); la->deleteAllLinks = 0; LIBALIAS_UNLOCK(la); } @@ -2435,17 +2435,17 @@ #ifdef _KERNEL la->timeStamp = time_uptime; - la->lastCleanupTime = time_uptime; #else gettimeofday(&tv, NULL); la->timeStamp = tv.tv_sec; - la->lastCleanupTime = tv.tv_sec; #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]); + LIST_INIT(&la->linkPartial); + 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 @@ -46,16 +46,17 @@ */ #ifndef _ALIAS_LOCAL_H_ -#define _ALIAS_LOCAL_H_ +#define _ALIAS_LOCAL_H_ -#include #include +#include +#include #ifdef _KERNEL -#include -#include #include +#include #include +#include /* XXX: LibAliasSetTarget() uses this constant. */ #define INADDR_NONE 0xffffffff @@ -94,6 +95,9 @@ * 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) linkPartial; + /* HouseKeeping */ + TAILQ_HEAD (, alias_link) checkExpire; /* Link statistics */ int icmpLinkCount; int udpLinkCount; @@ -107,8 +111,6 @@ 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;