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