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