xref: /freebsd/sys/netgraph/ng_bridge.c (revision aa77200569e397d6ff1fdb4d255d0fa254d0a128)
1 /*
2  * ng_bridge.c
3  */
4 
5 /*-
6  * Copyright (c) 2000 Whistle Communications, Inc.
7  * All rights reserved.
8  *
9  * Subject to the following obligations and disclaimer of warranty, use and
10  * redistribution of this software, in source or object code forms, with or
11  * without modifications are expressly permitted by Whistle Communications;
12  * provided, however, that:
13  * 1. Any and all reproductions of the source or object code must include the
14  *    copyright notice above and the following disclaimer of warranties; and
15  * 2. No rights are granted, in any manner or form, to use Whistle
16  *    Communications, Inc. trademarks, including the mark "WHISTLE
17  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
18  *    such appears in the above copyright notice or in the software.
19  *
20  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
21  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
22  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
23  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
24  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
25  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
26  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
27  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
28  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
29  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
30  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
31  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
32  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
33  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
35  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
36  * OF SUCH DAMAGE.
37  *
38  * Author: Archie Cobbs <archie@freebsd.org>
39  *
40  * $FreeBSD$
41  */
42 
43 /*
44  * ng_bridge(4) netgraph node type
45  *
46  * The node performs standard intelligent Ethernet bridging over
47  * each of its connected hooks, or links.  A simple loop detection
48  * algorithm is included which disables a link for priv->conf.loopTimeout
49  * seconds when a host is seen to have jumped from one link to
50  * another within priv->conf.minStableAge seconds.
51  *
52  * We keep a hashtable that maps Ethernet addresses to host info,
53  * which is contained in struct ng_bridge_host's. These structures
54  * tell us on which link the host may be found. A host's entry will
55  * expire after priv->conf.maxStaleness seconds.
56  *
57  * This node is optimzed for stable networks, where machines jump
58  * from one port to the other only rarely.
59  */
60 
61 #include <sys/param.h>
62 #include <sys/systm.h>
63 #include <sys/kernel.h>
64 #include <sys/lock.h>
65 #include <sys/malloc.h>
66 #include <sys/mbuf.h>
67 #include <sys/errno.h>
68 #include <sys/rwlock.h>
69 #include <sys/syslog.h>
70 #include <sys/socket.h>
71 #include <sys/ctype.h>
72 
73 #include <net/if.h>
74 #include <net/ethernet.h>
75 #include <net/vnet.h>
76 
77 #include <netinet/in.h>
78 #if 0	/* not used yet */
79 #include <netinet/ip_fw.h>
80 #endif
81 #include <netgraph/ng_message.h>
82 #include <netgraph/netgraph.h>
83 #include <netgraph/ng_parse.h>
84 #include <netgraph/ng_bridge.h>
85 
86 #ifdef NG_SEPARATE_MALLOC
87 static MALLOC_DEFINE(M_NETGRAPH_BRIDGE, "netgraph_bridge",
88     "netgraph bridge node");
89 #else
90 #define M_NETGRAPH_BRIDGE M_NETGRAPH
91 #endif
92 
93 /* Per-link private data */
94 struct ng_bridge_link {
95 	hook_p				hook;		/* netgraph hook */
96 	u_int16_t			loopCount;	/* loop ignore timer */
97 	struct ng_bridge_link_stats	stats;		/* link stats */
98 };
99 
100 /* Per-node private data */
101 struct ng_bridge_private {
102 	struct ng_bridge_bucket	*tab;		/* hash table bucket array */
103 	struct ng_bridge_link	*links[NG_BRIDGE_MAX_LINKS];
104 	struct ng_bridge_config	conf;		/* node configuration */
105 	node_p			node;		/* netgraph node */
106 	u_int			numHosts;	/* num entries in table */
107 	u_int			numBuckets;	/* num buckets in table */
108 	u_int			hashMask;	/* numBuckets - 1 */
109 	int			numLinks;	/* num connected links */
110 	int			persistent;	/* can exist w/o hooks */
111 	struct callout		timer;		/* one second periodic timer */
112 };
113 typedef struct ng_bridge_private *priv_p;
114 
115 /* Information about a host, stored in a hash table entry */
116 struct ng_bridge_hent {
117 	struct ng_bridge_host		host;	/* actual host info */
118 	SLIST_ENTRY(ng_bridge_hent)	next;	/* next entry in bucket */
119 };
120 
121 /* Hash table bucket declaration */
122 SLIST_HEAD(ng_bridge_bucket, ng_bridge_hent);
123 
124 /* Netgraph node methods */
125 static ng_constructor_t	ng_bridge_constructor;
126 static ng_rcvmsg_t	ng_bridge_rcvmsg;
127 static ng_shutdown_t	ng_bridge_shutdown;
128 static ng_newhook_t	ng_bridge_newhook;
129 static ng_rcvdata_t	ng_bridge_rcvdata;
130 static ng_disconnect_t	ng_bridge_disconnect;
131 
132 /* Other internal functions */
133 static struct	ng_bridge_host *ng_bridge_get(priv_p priv, const u_char *addr);
134 static int	ng_bridge_put(priv_p priv, const u_char *addr, int linkNum);
135 static void	ng_bridge_rehash(priv_p priv);
136 static void	ng_bridge_remove_hosts(priv_p priv, int linkNum);
137 static void	ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2);
138 static const	char *ng_bridge_nodename(node_p node);
139 
140 /* Ethernet broadcast */
141 static const u_char ng_bridge_bcast_addr[ETHER_ADDR_LEN] =
142     { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
143 
144 /* Store each hook's link number in the private field */
145 #define LINK_NUM(hook)		(*(u_int16_t *)(&(hook)->private))
146 
147 /* Compare Ethernet addresses using 32 and 16 bit words instead of bytewise */
148 #define ETHER_EQUAL(a,b)	(((const u_int32_t *)(a))[0] \
149 					== ((const u_int32_t *)(b))[0] \
150 				    && ((const u_int16_t *)(a))[2] \
151 					== ((const u_int16_t *)(b))[2])
152 
153 /* Minimum and maximum number of hash buckets. Must be a power of two. */
154 #define MIN_BUCKETS		(1 << 5)	/* 32 */
155 #define MAX_BUCKETS		(1 << 14)	/* 16384 */
156 
157 /* Configuration default values */
158 #define DEFAULT_LOOP_TIMEOUT	60
159 #define DEFAULT_MAX_STALENESS	(15 * 60)	/* same as ARP timeout */
160 #define DEFAULT_MIN_STABLE_AGE	1
161 
162 /******************************************************************
163 		    NETGRAPH PARSE TYPES
164 ******************************************************************/
165 
166 /*
167  * How to determine the length of the table returned by NGM_BRIDGE_GET_TABLE
168  */
169 static int
170 ng_bridge_getTableLength(const struct ng_parse_type *type,
171 	const u_char *start, const u_char *buf)
172 {
173 	const struct ng_bridge_host_ary *const hary
174 	    = (const struct ng_bridge_host_ary *)(buf - sizeof(u_int32_t));
175 
176 	return hary->numHosts;
177 }
178 
179 /* Parse type for struct ng_bridge_host_ary */
180 static const struct ng_parse_struct_field ng_bridge_host_type_fields[]
181 	= NG_BRIDGE_HOST_TYPE_INFO(&ng_parse_enaddr_type);
182 static const struct ng_parse_type ng_bridge_host_type = {
183 	&ng_parse_struct_type,
184 	&ng_bridge_host_type_fields
185 };
186 static const struct ng_parse_array_info ng_bridge_hary_type_info = {
187 	&ng_bridge_host_type,
188 	ng_bridge_getTableLength
189 };
190 static const struct ng_parse_type ng_bridge_hary_type = {
191 	&ng_parse_array_type,
192 	&ng_bridge_hary_type_info
193 };
194 static const struct ng_parse_struct_field ng_bridge_host_ary_type_fields[]
195 	= NG_BRIDGE_HOST_ARY_TYPE_INFO(&ng_bridge_hary_type);
196 static const struct ng_parse_type ng_bridge_host_ary_type = {
197 	&ng_parse_struct_type,
198 	&ng_bridge_host_ary_type_fields
199 };
200 
201 /* Parse type for struct ng_bridge_config */
202 static const struct ng_parse_fixedarray_info ng_bridge_ipfwary_type_info = {
203 	&ng_parse_uint8_type,
204 	NG_BRIDGE_MAX_LINKS
205 };
206 static const struct ng_parse_type ng_bridge_ipfwary_type = {
207 	&ng_parse_fixedarray_type,
208 	&ng_bridge_ipfwary_type_info
209 };
210 static const struct ng_parse_struct_field ng_bridge_config_type_fields[]
211 	= NG_BRIDGE_CONFIG_TYPE_INFO(&ng_bridge_ipfwary_type);
212 static const struct ng_parse_type ng_bridge_config_type = {
213 	&ng_parse_struct_type,
214 	&ng_bridge_config_type_fields
215 };
216 
217 /* Parse type for struct ng_bridge_link_stat */
218 static const struct ng_parse_struct_field ng_bridge_stats_type_fields[]
219 	= NG_BRIDGE_STATS_TYPE_INFO;
220 static const struct ng_parse_type ng_bridge_stats_type = {
221 	&ng_parse_struct_type,
222 	&ng_bridge_stats_type_fields
223 };
224 
225 /* List of commands and how to convert arguments to/from ASCII */
226 static const struct ng_cmdlist ng_bridge_cmdlist[] = {
227 	{
228 	  NGM_BRIDGE_COOKIE,
229 	  NGM_BRIDGE_SET_CONFIG,
230 	  "setconfig",
231 	  &ng_bridge_config_type,
232 	  NULL
233 	},
234 	{
235 	  NGM_BRIDGE_COOKIE,
236 	  NGM_BRIDGE_GET_CONFIG,
237 	  "getconfig",
238 	  NULL,
239 	  &ng_bridge_config_type
240 	},
241 	{
242 	  NGM_BRIDGE_COOKIE,
243 	  NGM_BRIDGE_RESET,
244 	  "reset",
245 	  NULL,
246 	  NULL
247 	},
248 	{
249 	  NGM_BRIDGE_COOKIE,
250 	  NGM_BRIDGE_GET_STATS,
251 	  "getstats",
252 	  &ng_parse_uint32_type,
253 	  &ng_bridge_stats_type
254 	},
255 	{
256 	  NGM_BRIDGE_COOKIE,
257 	  NGM_BRIDGE_CLR_STATS,
258 	  "clrstats",
259 	  &ng_parse_uint32_type,
260 	  NULL
261 	},
262 	{
263 	  NGM_BRIDGE_COOKIE,
264 	  NGM_BRIDGE_GETCLR_STATS,
265 	  "getclrstats",
266 	  &ng_parse_uint32_type,
267 	  &ng_bridge_stats_type
268 	},
269 	{
270 	  NGM_BRIDGE_COOKIE,
271 	  NGM_BRIDGE_GET_TABLE,
272 	  "gettable",
273 	  NULL,
274 	  &ng_bridge_host_ary_type
275 	},
276 	{
277 	  NGM_BRIDGE_COOKIE,
278 	  NGM_BRIDGE_SET_PERSISTENT,
279 	  "setpersistent",
280 	  NULL,
281 	  NULL
282 	},
283 	{ 0 }
284 };
285 
286 /* Node type descriptor */
287 static struct ng_type ng_bridge_typestruct = {
288 	.version =	NG_ABI_VERSION,
289 	.name =		NG_BRIDGE_NODE_TYPE,
290 	.constructor =	ng_bridge_constructor,
291 	.rcvmsg =	ng_bridge_rcvmsg,
292 	.shutdown =	ng_bridge_shutdown,
293 	.newhook =	ng_bridge_newhook,
294 	.rcvdata =	ng_bridge_rcvdata,
295 	.disconnect =	ng_bridge_disconnect,
296 	.cmdlist =	ng_bridge_cmdlist,
297 };
298 NETGRAPH_INIT(bridge, &ng_bridge_typestruct);
299 
300 /******************************************************************
301 		    NETGRAPH NODE METHODS
302 ******************************************************************/
303 
304 /*
305  * Node constructor
306  */
307 static int
308 ng_bridge_constructor(node_p node)
309 {
310 	priv_p priv;
311 
312 	/* Allocate and initialize private info */
313 	priv = malloc(sizeof(*priv), M_NETGRAPH_BRIDGE, M_WAITOK | M_ZERO);
314 	ng_callout_init(&priv->timer);
315 
316 	/* Allocate and initialize hash table, etc. */
317 	priv->tab = malloc(MIN_BUCKETS * sizeof(*priv->tab),
318 	    M_NETGRAPH_BRIDGE, M_WAITOK | M_ZERO);
319 	priv->numBuckets = MIN_BUCKETS;
320 	priv->hashMask = MIN_BUCKETS - 1;
321 	priv->conf.debugLevel = 1;
322 	priv->conf.loopTimeout = DEFAULT_LOOP_TIMEOUT;
323 	priv->conf.maxStaleness = DEFAULT_MAX_STALENESS;
324 	priv->conf.minStableAge = DEFAULT_MIN_STABLE_AGE;
325 
326 	/*
327 	 * This node has all kinds of stuff that could be screwed by SMP.
328 	 * Until it gets it's own internal protection, we go through in
329 	 * single file. This could hurt a machine bridging beteen two
330 	 * GB ethernets so it should be fixed.
331 	 * When it's fixed the process SHOULD NOT SLEEP, spinlocks please!
332 	 * (and atomic ops )
333 	 */
334 	NG_NODE_FORCE_WRITER(node);
335 	NG_NODE_SET_PRIVATE(node, priv);
336 	priv->node = node;
337 
338 	/* Start timer; timer is always running while node is alive */
339 	ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
340 
341 	/* Done */
342 	return (0);
343 }
344 
345 /*
346  * Method for attaching a new hook
347  */
348 static	int
349 ng_bridge_newhook(node_p node, hook_p hook, const char *name)
350 {
351 	const priv_p priv = NG_NODE_PRIVATE(node);
352 
353 	/* Check for a link hook */
354 	if (strncmp(name, NG_BRIDGE_HOOK_LINK_PREFIX,
355 	    strlen(NG_BRIDGE_HOOK_LINK_PREFIX)) == 0) {
356 		const char *cp;
357 		char *eptr;
358 		u_long linkNum;
359 
360 		cp = name + strlen(NG_BRIDGE_HOOK_LINK_PREFIX);
361 		if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0'))
362 			return (EINVAL);
363 		linkNum = strtoul(cp, &eptr, 10);
364 		if (*eptr != '\0' || linkNum >= NG_BRIDGE_MAX_LINKS)
365 			return (EINVAL);
366 		if (priv->links[linkNum] != NULL)
367 			return (EISCONN);
368 		priv->links[linkNum] = malloc(sizeof(*priv->links[linkNum]),
369 		    M_NETGRAPH_BRIDGE, M_NOWAIT|M_ZERO);
370 		if (priv->links[linkNum] == NULL)
371 			return (ENOMEM);
372 		priv->links[linkNum]->hook = hook;
373 		NG_HOOK_SET_PRIVATE(hook, (void *)linkNum);
374 		priv->numLinks++;
375 		return (0);
376 	}
377 
378 	/* Unknown hook name */
379 	return (EINVAL);
380 }
381 
382 /*
383  * Receive a control message
384  */
385 static int
386 ng_bridge_rcvmsg(node_p node, item_p item, hook_p lasthook)
387 {
388 	const priv_p priv = NG_NODE_PRIVATE(node);
389 	struct ng_mesg *resp = NULL;
390 	int error = 0;
391 	struct ng_mesg *msg;
392 
393 	NGI_GET_MSG(item, msg);
394 	switch (msg->header.typecookie) {
395 	case NGM_BRIDGE_COOKIE:
396 		switch (msg->header.cmd) {
397 		case NGM_BRIDGE_GET_CONFIG:
398 		    {
399 			struct ng_bridge_config *conf;
400 
401 			NG_MKRESPONSE(resp, msg,
402 			    sizeof(struct ng_bridge_config), M_NOWAIT);
403 			if (resp == NULL) {
404 				error = ENOMEM;
405 				break;
406 			}
407 			conf = (struct ng_bridge_config *)resp->data;
408 			*conf = priv->conf;	/* no sanity checking needed */
409 			break;
410 		    }
411 		case NGM_BRIDGE_SET_CONFIG:
412 		    {
413 			struct ng_bridge_config *conf;
414 			int i;
415 
416 			if (msg->header.arglen
417 			    != sizeof(struct ng_bridge_config)) {
418 				error = EINVAL;
419 				break;
420 			}
421 			conf = (struct ng_bridge_config *)msg->data;
422 			priv->conf = *conf;
423 			for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++)
424 				priv->conf.ipfw[i] = !!priv->conf.ipfw[i];
425 			break;
426 		    }
427 		case NGM_BRIDGE_RESET:
428 		    {
429 			int i;
430 
431 			/* Flush all entries in the hash table */
432 			ng_bridge_remove_hosts(priv, -1);
433 
434 			/* Reset all loop detection counters and stats */
435 			for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++) {
436 				if (priv->links[i] == NULL)
437 					continue;
438 				priv->links[i]->loopCount = 0;
439 				bzero(&priv->links[i]->stats,
440 				    sizeof(priv->links[i]->stats));
441 			}
442 			break;
443 		    }
444 		case NGM_BRIDGE_GET_STATS:
445 		case NGM_BRIDGE_CLR_STATS:
446 		case NGM_BRIDGE_GETCLR_STATS:
447 		    {
448 			struct ng_bridge_link *link;
449 			int linkNum;
450 
451 			/* Get link number */
452 			if (msg->header.arglen != sizeof(u_int32_t)) {
453 				error = EINVAL;
454 				break;
455 			}
456 			linkNum = *((u_int32_t *)msg->data);
457 			if (linkNum < 0 || linkNum >= NG_BRIDGE_MAX_LINKS) {
458 				error = EINVAL;
459 				break;
460 			}
461 			if ((link = priv->links[linkNum]) == NULL) {
462 				error = ENOTCONN;
463 				break;
464 			}
465 
466 			/* Get/clear stats */
467 			if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
468 				NG_MKRESPONSE(resp, msg,
469 				    sizeof(link->stats), M_NOWAIT);
470 				if (resp == NULL) {
471 					error = ENOMEM;
472 					break;
473 				}
474 				bcopy(&link->stats,
475 				    resp->data, sizeof(link->stats));
476 			}
477 			if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
478 				bzero(&link->stats, sizeof(link->stats));
479 			break;
480 		    }
481 		case NGM_BRIDGE_GET_TABLE:
482 		    {
483 			struct ng_bridge_host_ary *ary;
484 			struct ng_bridge_hent *hent;
485 			int i = 0, bucket;
486 
487 			NG_MKRESPONSE(resp, msg, sizeof(*ary)
488 			    + (priv->numHosts * sizeof(*ary->hosts)), M_NOWAIT);
489 			if (resp == NULL) {
490 				error = ENOMEM;
491 				break;
492 			}
493 			ary = (struct ng_bridge_host_ary *)resp->data;
494 			ary->numHosts = priv->numHosts;
495 			for (bucket = 0; bucket < priv->numBuckets; bucket++) {
496 				SLIST_FOREACH(hent, &priv->tab[bucket], next)
497 					ary->hosts[i++] = hent->host;
498 			}
499 			break;
500 		    }
501 		case NGM_BRIDGE_SET_PERSISTENT:
502 		    {
503 			priv->persistent = 1;
504 			break;
505 		    }
506 		default:
507 			error = EINVAL;
508 			break;
509 		}
510 		break;
511 	default:
512 		error = EINVAL;
513 		break;
514 	}
515 
516 	/* Done */
517 	NG_RESPOND_MSG(error, node, item, resp);
518 	NG_FREE_MSG(msg);
519 	return (error);
520 }
521 
522 /*
523  * Receive data on a hook
524  */
525 static int
526 ng_bridge_rcvdata(hook_p hook, item_p item)
527 {
528 	const node_p node = NG_HOOK_NODE(hook);
529 	const priv_p priv = NG_NODE_PRIVATE(node);
530 	struct ng_bridge_host *host;
531 	struct ng_bridge_link *link;
532 	struct ether_header *eh;
533 	int error = 0, linkNum, linksSeen;
534 	int manycast;
535 	struct mbuf *m;
536 	struct ng_bridge_link *firstLink;
537 
538 	NGI_GET_M(item, m);
539 	/* Get link number */
540 	linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
541 	KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
542 	    ("%s: linkNum=%u", __func__, linkNum));
543 	link = priv->links[linkNum];
544 	KASSERT(link != NULL, ("%s: link%d null", __func__, linkNum));
545 
546 	/* Sanity check packet and pull up header */
547 	if (m->m_pkthdr.len < ETHER_HDR_LEN) {
548 		link->stats.recvRunts++;
549 		NG_FREE_ITEM(item);
550 		NG_FREE_M(m);
551 		return (EINVAL);
552 	}
553 	if (m->m_len < ETHER_HDR_LEN && !(m = m_pullup(m, ETHER_HDR_LEN))) {
554 		link->stats.memoryFailures++;
555 		NG_FREE_ITEM(item);
556 		return (ENOBUFS);
557 	}
558 	eh = mtod(m, struct ether_header *);
559 	if ((eh->ether_shost[0] & 1) != 0) {
560 		link->stats.recvInvalid++;
561 		NG_FREE_ITEM(item);
562 		NG_FREE_M(m);
563 		return (EINVAL);
564 	}
565 
566 	/* Is link disabled due to a loopback condition? */
567 	if (link->loopCount != 0) {
568 		link->stats.loopDrops++;
569 		NG_FREE_ITEM(item);
570 		NG_FREE_M(m);
571 		return (ELOOP);		/* XXX is this an appropriate error? */
572 	}
573 
574 	/* Update stats */
575 	link->stats.recvPackets++;
576 	link->stats.recvOctets += m->m_pkthdr.len;
577 	if ((manycast = (eh->ether_dhost[0] & 1)) != 0) {
578 		if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
579 			link->stats.recvBroadcasts++;
580 			manycast = 2;
581 		} else
582 			link->stats.recvMulticasts++;
583 	}
584 
585 	/* Look up packet's source Ethernet address in hashtable */
586 	if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
587 
588 		/* Update time since last heard from this host */
589 		host->staleness = 0;
590 
591 		/* Did host jump to a different link? */
592 		if (host->linkNum != linkNum) {
593 
594 			/*
595 			 * If the host's old link was recently established
596 			 * on the old link and it's already jumped to a new
597 			 * link, declare a loopback condition.
598 			 */
599 			if (host->age < priv->conf.minStableAge) {
600 
601 				/* Log the problem */
602 				if (priv->conf.debugLevel >= 2) {
603 					struct ifnet *ifp = m->m_pkthdr.rcvif;
604 					char suffix[32];
605 
606 					if (ifp != NULL)
607 						snprintf(suffix, sizeof(suffix),
608 						    " (%s)", ifp->if_xname);
609 					else
610 						*suffix = '\0';
611 					log(LOG_WARNING, "ng_bridge: %s:"
612 					    " loopback detected on %s%s\n",
613 					    ng_bridge_nodename(node),
614 					    NG_HOOK_NAME(hook), suffix);
615 				}
616 
617 				/* Mark link as linka non grata */
618 				link->loopCount = priv->conf.loopTimeout;
619 				link->stats.loopDetects++;
620 
621 				/* Forget all hosts on this link */
622 				ng_bridge_remove_hosts(priv, linkNum);
623 
624 				/* Drop packet */
625 				link->stats.loopDrops++;
626 				NG_FREE_ITEM(item);
627 				NG_FREE_M(m);
628 				return (ELOOP);		/* XXX appropriate? */
629 			}
630 
631 			/* Move host over to new link */
632 			host->linkNum = linkNum;
633 			host->age = 0;
634 		}
635 	} else {
636 		if (!ng_bridge_put(priv, eh->ether_shost, linkNum)) {
637 			link->stats.memoryFailures++;
638 			NG_FREE_ITEM(item);
639 			NG_FREE_M(m);
640 			return (ENOMEM);
641 		}
642 	}
643 
644 	/* Run packet through ipfw processing, if enabled */
645 #if 0
646 	if (priv->conf.ipfw[linkNum] && V_fw_enable && V_ip_fw_chk_ptr != NULL) {
647 		/* XXX not implemented yet */
648 	}
649 #endif
650 
651 	/*
652 	 * If unicast and destination host known, deliver to host's link,
653 	 * unless it is the same link as the packet came in on.
654 	 */
655 	if (!manycast) {
656 
657 		/* Determine packet destination link */
658 		if ((host = ng_bridge_get(priv, eh->ether_dhost)) != NULL) {
659 			struct ng_bridge_link *const destLink
660 			    = priv->links[host->linkNum];
661 
662 			/* If destination same as incoming link, do nothing */
663 			KASSERT(destLink != NULL,
664 			    ("%s: link%d null", __func__, host->linkNum));
665 			if (destLink == link) {
666 				NG_FREE_ITEM(item);
667 				NG_FREE_M(m);
668 				return (0);
669 			}
670 
671 			/* Deliver packet out the destination link */
672 			destLink->stats.xmitPackets++;
673 			destLink->stats.xmitOctets += m->m_pkthdr.len;
674 			NG_FWD_NEW_DATA(error, item, destLink->hook, m);
675 			return (error);
676 		}
677 
678 		/* Destination host is not known */
679 		link->stats.recvUnknown++;
680 	}
681 
682 	/* Distribute unknown, multicast, broadcast pkts to all other links */
683 	firstLink = NULL;
684 	for (linkNum = linksSeen = 0; linksSeen <= priv->numLinks; linkNum++) {
685 		struct ng_bridge_link *destLink;
686 		struct mbuf *m2 = NULL;
687 
688 		/*
689 		 * If we have checked all the links then now
690 		 * send the original on its reserved link
691 		 */
692 		if (linksSeen == priv->numLinks) {
693 			/* If we never saw a good link, leave. */
694 			if (firstLink == NULL) {
695 				NG_FREE_ITEM(item);
696 				NG_FREE_M(m);
697 				return (0);
698 			}
699 			destLink = firstLink;
700 		} else {
701 			destLink = priv->links[linkNum];
702 			if (destLink != NULL)
703 				linksSeen++;
704 			/* Skip incoming link and disconnected links */
705 			if (destLink == NULL || destLink == link) {
706 				continue;
707 			}
708 			if (firstLink == NULL) {
709 				/*
710 				 * This is the first usable link we have found.
711 				 * Reserve it for the originals.
712 				 * If we never find another we save a copy.
713 				 */
714 				firstLink = destLink;
715 				continue;
716 			}
717 
718 			/*
719 			 * It's usable link but not the reserved (first) one.
720 			 * Copy mbuf info for sending.
721 			 */
722 			m2 = m_dup(m, M_DONTWAIT);	/* XXX m_copypacket() */
723 			if (m2 == NULL) {
724 				link->stats.memoryFailures++;
725 				NG_FREE_ITEM(item);
726 				NG_FREE_M(m);
727 				return (ENOBUFS);
728 			}
729 		}
730 
731 		/* Update stats */
732 		destLink->stats.xmitPackets++;
733 		destLink->stats.xmitOctets += m->m_pkthdr.len;
734 		switch (manycast) {
735 		case 0:					/* unicast */
736 			break;
737 		case 1:					/* multicast */
738 			destLink->stats.xmitMulticasts++;
739 			break;
740 		case 2:					/* broadcast */
741 			destLink->stats.xmitBroadcasts++;
742 			break;
743 		}
744 
745 		/* Send packet */
746 		if (destLink == firstLink) {
747 			/*
748 			 * If we've sent all the others, send the original
749 			 * on the first link we found.
750 			 */
751 			NG_FWD_NEW_DATA(error, item, destLink->hook, m);
752 			break; /* always done last - not really needed. */
753 		} else {
754 			NG_SEND_DATA_ONLY(error, destLink->hook, m2);
755 		}
756 	}
757 	return (error);
758 }
759 
760 /*
761  * Shutdown node
762  */
763 static int
764 ng_bridge_shutdown(node_p node)
765 {
766 	const priv_p priv = NG_NODE_PRIVATE(node);
767 
768 	/*
769 	 * Shut down everything including the timer.  Even if the
770 	 * callout has already been dequeued and is about to be
771 	 * run, ng_bridge_timeout() won't be fired as the node
772 	 * is already marked NGF_INVALID, so we're safe to free
773 	 * the node now.
774 	 */
775 	KASSERT(priv->numLinks == 0 && priv->numHosts == 0,
776 	    ("%s: numLinks=%d numHosts=%d",
777 	    __func__, priv->numLinks, priv->numHosts));
778 	ng_uncallout(&priv->timer, node);
779 	NG_NODE_SET_PRIVATE(node, NULL);
780 	NG_NODE_UNREF(node);
781 	free(priv->tab, M_NETGRAPH_BRIDGE);
782 	free(priv, M_NETGRAPH_BRIDGE);
783 	return (0);
784 }
785 
786 /*
787  * Hook disconnection.
788  */
789 static int
790 ng_bridge_disconnect(hook_p hook)
791 {
792 	const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hook));
793 	int linkNum;
794 
795 	/* Get link number */
796 	linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
797 	KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
798 	    ("%s: linkNum=%u", __func__, linkNum));
799 
800 	/* Remove all hosts associated with this link */
801 	ng_bridge_remove_hosts(priv, linkNum);
802 
803 	/* Free associated link information */
804 	KASSERT(priv->links[linkNum] != NULL, ("%s: no link", __func__));
805 	free(priv->links[linkNum], M_NETGRAPH_BRIDGE);
806 	priv->links[linkNum] = NULL;
807 	priv->numLinks--;
808 
809 	/* If no more hooks, go away */
810 	if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
811 	    && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))
812 	    && !priv->persistent) {
813 		ng_rmnode_self(NG_HOOK_NODE(hook));
814 	}
815 	return (0);
816 }
817 
818 /******************************************************************
819 		    HASH TABLE FUNCTIONS
820 ******************************************************************/
821 
822 /*
823  * Hash algorithm
824  */
825 #define HASH(addr,mask)		( (((const u_int16_t *)(addr))[0] 	\
826 				 ^ ((const u_int16_t *)(addr))[1] 	\
827 				 ^ ((const u_int16_t *)(addr))[2]) & (mask) )
828 
829 /*
830  * Find a host entry in the table.
831  */
832 static struct ng_bridge_host *
833 ng_bridge_get(priv_p priv, const u_char *addr)
834 {
835 	const int bucket = HASH(addr, priv->hashMask);
836 	struct ng_bridge_hent *hent;
837 
838 	SLIST_FOREACH(hent, &priv->tab[bucket], next) {
839 		if (ETHER_EQUAL(hent->host.addr, addr))
840 			return (&hent->host);
841 	}
842 	return (NULL);
843 }
844 
845 /*
846  * Add a new host entry to the table. This assumes the host doesn't
847  * already exist in the table. Returns 1 on success, 0 if there
848  * was a memory allocation failure.
849  */
850 static int
851 ng_bridge_put(priv_p priv, const u_char *addr, int linkNum)
852 {
853 	const int bucket = HASH(addr, priv->hashMask);
854 	struct ng_bridge_hent *hent;
855 
856 #ifdef INVARIANTS
857 	/* Assert that entry does not already exist in hashtable */
858 	SLIST_FOREACH(hent, &priv->tab[bucket], next) {
859 		KASSERT(!ETHER_EQUAL(hent->host.addr, addr),
860 		    ("%s: entry %6D exists in table", __func__, addr, ":"));
861 	}
862 #endif
863 
864 	/* Allocate and initialize new hashtable entry */
865 	hent = malloc(sizeof(*hent), M_NETGRAPH_BRIDGE, M_NOWAIT);
866 	if (hent == NULL)
867 		return (0);
868 	bcopy(addr, hent->host.addr, ETHER_ADDR_LEN);
869 	hent->host.linkNum = linkNum;
870 	hent->host.staleness = 0;
871 	hent->host.age = 0;
872 
873 	/* Add new element to hash bucket */
874 	SLIST_INSERT_HEAD(&priv->tab[bucket], hent, next);
875 	priv->numHosts++;
876 
877 	/* Resize table if necessary */
878 	ng_bridge_rehash(priv);
879 	return (1);
880 }
881 
882 /*
883  * Resize the hash table. We try to maintain the number of buckets
884  * such that the load factor is in the range 0.25 to 1.0.
885  *
886  * If we can't get the new memory then we silently fail. This is OK
887  * because things will still work and we'll try again soon anyway.
888  */
889 static void
890 ng_bridge_rehash(priv_p priv)
891 {
892 	struct ng_bridge_bucket *newTab;
893 	int oldBucket, newBucket;
894 	int newNumBuckets;
895 	u_int newMask;
896 
897 	/* Is table too full or too empty? */
898 	if (priv->numHosts > priv->numBuckets
899 	    && (priv->numBuckets << 1) <= MAX_BUCKETS)
900 		newNumBuckets = priv->numBuckets << 1;
901 	else if (priv->numHosts < (priv->numBuckets >> 2)
902 	    && (priv->numBuckets >> 2) >= MIN_BUCKETS)
903 		newNumBuckets = priv->numBuckets >> 2;
904 	else
905 		return;
906 	newMask = newNumBuckets - 1;
907 
908 	/* Allocate and initialize new table */
909 	newTab = malloc(newNumBuckets * sizeof(*newTab),
910 	    M_NETGRAPH_BRIDGE, M_NOWAIT | M_ZERO);
911 	if (newTab == NULL)
912 		return;
913 
914 	/* Move all entries from old table to new table */
915 	for (oldBucket = 0; oldBucket < priv->numBuckets; oldBucket++) {
916 		struct ng_bridge_bucket *const oldList = &priv->tab[oldBucket];
917 
918 		while (!SLIST_EMPTY(oldList)) {
919 			struct ng_bridge_hent *const hent
920 			    = SLIST_FIRST(oldList);
921 
922 			SLIST_REMOVE_HEAD(oldList, next);
923 			newBucket = HASH(hent->host.addr, newMask);
924 			SLIST_INSERT_HEAD(&newTab[newBucket], hent, next);
925 		}
926 	}
927 
928 	/* Replace old table with new one */
929 	if (priv->conf.debugLevel >= 3) {
930 		log(LOG_INFO, "ng_bridge: %s: table size %d -> %d\n",
931 		    ng_bridge_nodename(priv->node),
932 		    priv->numBuckets, newNumBuckets);
933 	}
934 	free(priv->tab, M_NETGRAPH_BRIDGE);
935 	priv->numBuckets = newNumBuckets;
936 	priv->hashMask = newMask;
937 	priv->tab = newTab;
938 	return;
939 }
940 
941 /******************************************************************
942 		    MISC FUNCTIONS
943 ******************************************************************/
944 
945 /*
946  * Remove all hosts associated with a specific link from the hashtable.
947  * If linkNum == -1, then remove all hosts in the table.
948  */
949 static void
950 ng_bridge_remove_hosts(priv_p priv, int linkNum)
951 {
952 	int bucket;
953 
954 	for (bucket = 0; bucket < priv->numBuckets; bucket++) {
955 		struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
956 
957 		while (*hptr != NULL) {
958 			struct ng_bridge_hent *const hent = *hptr;
959 
960 			if (linkNum == -1 || hent->host.linkNum == linkNum) {
961 				*hptr = SLIST_NEXT(hent, next);
962 				free(hent, M_NETGRAPH_BRIDGE);
963 				priv->numHosts--;
964 			} else
965 				hptr = &SLIST_NEXT(hent, next);
966 		}
967 	}
968 }
969 
970 /*
971  * Handle our once-per-second timeout event. We do two things:
972  * we decrement link->loopCount for those links being muted due to
973  * a detected loopback condition, and we remove any hosts from
974  * the hashtable whom we haven't heard from in a long while.
975  */
976 static void
977 ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2)
978 {
979 	const priv_p priv = NG_NODE_PRIVATE(node);
980 	int bucket;
981 	int counter = 0;
982 	int linkNum;
983 
984 	/* Update host time counters and remove stale entries */
985 	for (bucket = 0; bucket < priv->numBuckets; bucket++) {
986 		struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
987 
988 		while (*hptr != NULL) {
989 			struct ng_bridge_hent *const hent = *hptr;
990 
991 			/* Make sure host's link really exists */
992 			KASSERT(priv->links[hent->host.linkNum] != NULL,
993 			    ("%s: host %6D on nonexistent link %d\n",
994 			    __func__, hent->host.addr, ":",
995 			    hent->host.linkNum));
996 
997 			/* Remove hosts we haven't heard from in a while */
998 			if (++hent->host.staleness >= priv->conf.maxStaleness) {
999 				*hptr = SLIST_NEXT(hent, next);
1000 				free(hent, M_NETGRAPH_BRIDGE);
1001 				priv->numHosts--;
1002 			} else {
1003 				if (hent->host.age < 0xffff)
1004 					hent->host.age++;
1005 				hptr = &SLIST_NEXT(hent, next);
1006 				counter++;
1007 			}
1008 		}
1009 	}
1010 	KASSERT(priv->numHosts == counter,
1011 	    ("%s: hosts: %d != %d", __func__, priv->numHosts, counter));
1012 
1013 	/* Decrease table size if necessary */
1014 	ng_bridge_rehash(priv);
1015 
1016 	/* Decrease loop counter on muted looped back links */
1017 	for (counter = linkNum = 0; linkNum < NG_BRIDGE_MAX_LINKS; linkNum++) {
1018 		struct ng_bridge_link *const link = priv->links[linkNum];
1019 
1020 		if (link != NULL) {
1021 			if (link->loopCount != 0) {
1022 				link->loopCount--;
1023 				if (link->loopCount == 0
1024 				    && priv->conf.debugLevel >= 2) {
1025 					log(LOG_INFO, "ng_bridge: %s:"
1026 					    " restoring looped back link%d\n",
1027 					    ng_bridge_nodename(node), linkNum);
1028 				}
1029 			}
1030 			counter++;
1031 		}
1032 	}
1033 	KASSERT(priv->numLinks == counter,
1034 	    ("%s: links: %d != %d", __func__, priv->numLinks, counter));
1035 
1036 	/* Register a new timeout, keeping the existing node reference */
1037 	ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
1038 }
1039 
1040 /*
1041  * Return node's "name", even if it doesn't have one.
1042  */
1043 static const char *
1044 ng_bridge_nodename(node_p node)
1045 {
1046 	static char name[NG_NODESIZ];
1047 
1048 	if (NG_NODE_NAME(node) != NULL)
1049 		snprintf(name, sizeof(name), "%s", NG_NODE_NAME(node));
1050 	else
1051 		snprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1052 	return name;
1053 }
1054 
1055