Make modules work again part 1: Rename netgraph's Makefile.module to
[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.5 2003/08/14 23:26:38 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
71 #include <net/if.h>
72 #include <net/ethernet.h>
73
74 #include <netinet/in.h>
75 #include <net/ipfw/ip_fw.h>
76
77 #include <netgraph/ng_message.h>
78 #include <netgraph/netgraph.h>
79 #include <netgraph/ng_parse.h>
80 #include "ng_bridge.h"
81 #include <netgraph/ether/ng_ether.h>
82
83 /* Per-link private data */
84 struct ng_bridge_link {
85         hook_p                          hook;           /* netgraph hook */
86         u_int16_t                       loopCount;      /* loop ignore timer */
87         struct ng_bridge_link_stats     stats;          /* link stats */
88 };
89
90 /* Per-node private data */
91 struct ng_bridge_private {
92         struct ng_bridge_bucket *tab;           /* hash table bucket array */
93         struct ng_bridge_link   *links[NG_BRIDGE_MAX_LINKS];
94         struct ng_bridge_config conf;           /* node configuration */
95         node_p                  node;           /* netgraph node */
96         u_int                   numHosts;       /* num entries in table */
97         u_int                   numBuckets;     /* num buckets in table */
98         u_int                   hashMask;       /* numBuckets - 1 */
99         int                     numLinks;       /* num connected links */
100         struct callout          timer;          /* one second periodic timer */
101 };
102 typedef struct ng_bridge_private *priv_p;
103
104 /* Information about a host, stored in a hash table entry */
105 struct ng_bridge_hent {
106         struct ng_bridge_host           host;   /* actual host info */
107         SLIST_ENTRY(ng_bridge_hent)     next;   /* next entry in bucket */
108 };
109
110 /* Hash table bucket declaration */
111 SLIST_HEAD(ng_bridge_bucket, ng_bridge_hent);
112
113 /* Netgraph node methods */
114 static ng_constructor_t ng_bridge_constructor;
115 static ng_rcvmsg_t      ng_bridge_rcvmsg;
116 static ng_shutdown_t    ng_bridge_rmnode;
117 static ng_newhook_t     ng_bridge_newhook;
118 static ng_rcvdata_t     ng_bridge_rcvdata;
119 static ng_disconnect_t  ng_bridge_disconnect;
120
121 /* Other internal functions */
122 static struct   ng_bridge_host *ng_bridge_get(priv_p priv, const u_char *addr);
123 static int      ng_bridge_put(priv_p priv, const u_char *addr, int linkNum);
124 static void     ng_bridge_rehash(priv_p priv);
125 static void     ng_bridge_remove_hosts(priv_p priv, int linkNum);
126 static void     ng_bridge_timeout(void *arg);
127 static const    char *ng_bridge_nodename(node_p node);
128
129 /* Ethernet broadcast */
130 static const u_char ng_bridge_bcast_addr[ETHER_ADDR_LEN] =
131     { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
132
133 /* Store each hook's link number in the private field */
134 #define LINK_NUM(hook)          (*(u_int16_t *)(&(hook)->private))
135
136 /* Compare Ethernet addresses using 32 and 16 bit words instead of bytewise */
137 #define ETHER_EQUAL(a,b)        (((const u_int32_t *)(a))[0] \
138                                         == ((const u_int32_t *)(b))[0] \
139                                     && ((const u_int16_t *)(a))[2] \
140                                         == ((const u_int16_t *)(b))[2])
141
142 /* Minimum and maximum number of hash buckets. Must be a power of two. */
143 #define MIN_BUCKETS             (1 << 5)        /* 32 */
144 #define MAX_BUCKETS             (1 << 14)       /* 16384 */
145
146 /* Configuration default values */
147 #define DEFAULT_LOOP_TIMEOUT    60
148 #define DEFAULT_MAX_STALENESS   (15 * 60)       /* same as ARP timeout */
149 #define DEFAULT_MIN_STABLE_AGE  1
150
151 /******************************************************************
152                     NETGRAPH PARSE TYPES
153 ******************************************************************/
154
155 /*
156  * How to determine the length of the table returned by NGM_BRIDGE_GET_TABLE
157  */
158 static int
159 ng_bridge_getTableLength(const struct ng_parse_type *type,
160         const u_char *start, const u_char *buf)
161 {
162         const struct ng_bridge_host_ary *const hary
163             = (const struct ng_bridge_host_ary *)(buf - sizeof(u_int32_t));
164
165         return hary->numHosts;
166 }
167
168 /* Parse type for struct ng_bridge_host_ary */
169 static const struct ng_parse_struct_field ng_bridge_host_type_fields[]
170         = NG_BRIDGE_HOST_TYPE_INFO(&ng_ether_enaddr_type);
171 static const struct ng_parse_type ng_bridge_host_type = {
172         &ng_parse_struct_type,
173         &ng_bridge_host_type_fields
174 };
175 static const struct ng_parse_array_info ng_bridge_hary_type_info = {
176         &ng_bridge_host_type,
177         ng_bridge_getTableLength
178 };
179 static const struct ng_parse_type ng_bridge_hary_type = {
180         &ng_parse_array_type,
181         &ng_bridge_hary_type_info
182 };
183 static const struct ng_parse_struct_field ng_bridge_host_ary_type_fields[]
184         = NG_BRIDGE_HOST_ARY_TYPE_INFO(&ng_bridge_hary_type);
185 static const struct ng_parse_type ng_bridge_host_ary_type = {
186         &ng_parse_struct_type,
187         &ng_bridge_host_ary_type_fields
188 };
189
190 /* Parse type for struct ng_bridge_config */
191 static const struct ng_parse_fixedarray_info ng_bridge_ipfwary_type_info = {
192         &ng_parse_uint8_type,
193         NG_BRIDGE_MAX_LINKS
194 };
195 static const struct ng_parse_type ng_bridge_ipfwary_type = {
196         &ng_parse_fixedarray_type,
197         &ng_bridge_ipfwary_type_info
198 };
199 static const struct ng_parse_struct_field ng_bridge_config_type_fields[]
200         = NG_BRIDGE_CONFIG_TYPE_INFO(&ng_bridge_ipfwary_type);
201 static const struct ng_parse_type ng_bridge_config_type = {
202         &ng_parse_struct_type,
203         &ng_bridge_config_type_fields
204 };
205
206 /* Parse type for struct ng_bridge_link_stat */
207 static const struct ng_parse_struct_field ng_bridge_stats_type_fields[]
208         = NG_BRIDGE_STATS_TYPE_INFO;
209 static const struct ng_parse_type ng_bridge_stats_type = {
210         &ng_parse_struct_type,
211         &ng_bridge_stats_type_fields
212 };
213
214 /* List of commands and how to convert arguments to/from ASCII */
215 static const struct ng_cmdlist ng_bridge_cmdlist[] = {
216         {
217           NGM_BRIDGE_COOKIE,
218           NGM_BRIDGE_SET_CONFIG,
219           "setconfig",
220           &ng_bridge_config_type,
221           NULL
222         },
223         {
224           NGM_BRIDGE_COOKIE,
225           NGM_BRIDGE_GET_CONFIG,
226           "getconfig",
227           NULL,
228           &ng_bridge_config_type
229         },
230         {
231           NGM_BRIDGE_COOKIE,
232           NGM_BRIDGE_RESET,
233           "reset",
234           NULL,
235           NULL
236         },
237         {
238           NGM_BRIDGE_COOKIE,
239           NGM_BRIDGE_GET_STATS,
240           "getstats",
241           &ng_parse_uint32_type,
242           &ng_bridge_stats_type
243         },
244         {
245           NGM_BRIDGE_COOKIE,
246           NGM_BRIDGE_CLR_STATS,
247           "clrstats",
248           &ng_parse_uint32_type,
249           NULL
250         },
251         {
252           NGM_BRIDGE_COOKIE,
253           NGM_BRIDGE_GETCLR_STATS,
254           "getclrstats",
255           &ng_parse_uint32_type,
256           &ng_bridge_stats_type
257         },
258         {
259           NGM_BRIDGE_COOKIE,
260           NGM_BRIDGE_GET_TABLE,
261           "gettable",
262           NULL,
263           &ng_bridge_host_ary_type
264         },
265         { 0 }
266 };
267
268 /* Node type descriptor */
269 static struct ng_type ng_bridge_typestruct = {
270         NG_VERSION,
271         NG_BRIDGE_NODE_TYPE,
272         NULL,
273         ng_bridge_constructor,
274         ng_bridge_rcvmsg,
275         ng_bridge_rmnode,
276         ng_bridge_newhook,
277         NULL,
278         NULL,
279         ng_bridge_rcvdata,
280         ng_bridge_rcvdata,
281         ng_bridge_disconnect,
282         ng_bridge_cmdlist,
283 };
284 NETGRAPH_INIT(bridge, &ng_bridge_typestruct);
285
286 /* Depend on ng_ether so we can use the Ethernet parse type */
287 MODULE_DEPEND(ng_bridge, ng_ether, 1, 1, 1);
288
289 /******************************************************************
290                     NETGRAPH NODE METHODS
291 ******************************************************************/
292
293 /*
294  * Node constructor
295  */
296 static int
297 ng_bridge_constructor(node_p *nodep)
298 {
299         priv_p priv;
300         int error;
301
302         /* Allocate and initialize private info */
303         MALLOC(priv, priv_p, sizeof(*priv), M_NETGRAPH, M_NOWAIT);
304         if (priv == NULL)
305                 return (ENOMEM);
306         bzero(priv, sizeof(*priv));
307         callout_init(&priv->timer);
308
309         /* Allocate and initialize hash table, etc. */
310         MALLOC(priv->tab, struct ng_bridge_bucket *,
311             MIN_BUCKETS * sizeof(*priv->tab), M_NETGRAPH, M_NOWAIT);
312         if (priv->tab == NULL) {
313                 FREE(priv, M_NETGRAPH);
314                 return (ENOMEM);
315         }
316         bzero(priv->tab, MIN_BUCKETS * sizeof(*priv->tab));  /* init SLIST's */
317         priv->numBuckets = MIN_BUCKETS;
318         priv->hashMask = MIN_BUCKETS - 1;
319         priv->conf.debugLevel = 1;
320         priv->conf.loopTimeout = DEFAULT_LOOP_TIMEOUT;
321         priv->conf.maxStaleness = DEFAULT_MAX_STALENESS;
322         priv->conf.minStableAge = DEFAULT_MIN_STABLE_AGE;
323
324         /* Call superclass constructor */
325         if ((error = ng_make_node_common(&ng_bridge_typestruct, nodep))) {
326                 FREE(priv, M_NETGRAPH);
327                 return (error);
328         }
329         (*nodep)->private = priv;
330         priv->node = *nodep;
331
332         /* Start timer; timer is always running while node is alive */
333         callout_reset(&priv->timer, hz, ng_bridge_timeout, priv->node);
334
335         /* Done */
336         return (0);
337 }
338
339 /*
340  * Method for attaching a new hook
341  */
342 static  int
343 ng_bridge_newhook(node_p node, hook_p hook, const char *name)
344 {
345         const priv_p priv = node->private;
346
347         /* Check for a link hook */
348         if (strncmp(name, NG_BRIDGE_HOOK_LINK_PREFIX,
349             strlen(NG_BRIDGE_HOOK_LINK_PREFIX)) == 0) {
350                 const char *cp;
351                 char *eptr;
352                 u_long linkNum;
353
354                 cp = name + strlen(NG_BRIDGE_HOOK_LINK_PREFIX);
355                 if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0'))
356                         return (EINVAL);
357                 linkNum = strtoul(cp, &eptr, 10);
358                 if (*eptr != '\0' || linkNum >= NG_BRIDGE_MAX_LINKS)
359                         return (EINVAL);
360                 if (priv->links[linkNum] != NULL)
361                         return (EISCONN);
362                 MALLOC(priv->links[linkNum], struct ng_bridge_link *,
363                     sizeof(*priv->links[linkNum]), M_NETGRAPH, M_NOWAIT);
364                 if (priv->links[linkNum] == NULL)
365                         return (ENOMEM);
366                 bzero(priv->links[linkNum], sizeof(*priv->links[linkNum]));
367                 priv->links[linkNum]->hook = hook;
368                 LINK_NUM(hook) = linkNum;
369                 priv->numLinks++;
370                 return (0);
371         }
372
373         /* Unknown hook name */
374         return (EINVAL);
375 }
376
377 /*
378  * Receive a control message
379  */
380 static int
381 ng_bridge_rcvmsg(node_p node, struct ng_mesg *msg,
382         const char *retaddr, struct ng_mesg **rptr)
383 {
384         const priv_p priv = node->private;
385         struct ng_mesg *resp = NULL;
386         int error = 0;
387
388         switch (msg->header.typecookie) {
389         case NGM_BRIDGE_COOKIE:
390                 switch (msg->header.cmd) {
391                 case NGM_BRIDGE_GET_CONFIG:
392                     {
393                         struct ng_bridge_config *conf;
394
395                         NG_MKRESPONSE(resp, msg,
396                             sizeof(struct ng_bridge_config), M_NOWAIT);
397                         if (resp == NULL) {
398                                 error = ENOMEM;
399                                 break;
400                         }
401                         conf = (struct ng_bridge_config *)resp->data;
402                         *conf = priv->conf;     /* no sanity checking needed */
403                         break;
404                     }
405                 case NGM_BRIDGE_SET_CONFIG:
406                     {
407                         struct ng_bridge_config *conf;
408                         int i;
409
410                         if (msg->header.arglen
411                             != sizeof(struct ng_bridge_config)) {
412                                 error = EINVAL;
413                                 break;
414                         }
415                         conf = (struct ng_bridge_config *)msg->data;
416                         priv->conf = *conf;
417                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++)
418                                 priv->conf.ipfw[i] = !!priv->conf.ipfw[i];
419                         break;
420                     }
421                 case NGM_BRIDGE_RESET:
422                     {
423                         int i;
424
425                         /* Flush all entries in the hash table */
426                         ng_bridge_remove_hosts(priv, -1);
427
428                         /* Reset all loop detection counters and stats */
429                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++) {
430                                 if (priv->links[i] == NULL)
431                                         continue;
432                                 priv->links[i]->loopCount = 0;
433                                 bzero(&priv->links[i]->stats,
434                                     sizeof(priv->links[i]->stats));
435                         }
436                         break;
437                     }
438                 case NGM_BRIDGE_GET_STATS:
439                 case NGM_BRIDGE_CLR_STATS:
440                 case NGM_BRIDGE_GETCLR_STATS:
441                     {
442                         struct ng_bridge_link *link;
443                         int linkNum;
444
445                         /* Get link number */
446                         if (msg->header.arglen != sizeof(u_int32_t)) {
447                                 error = EINVAL;
448                                 break;
449                         }
450                         linkNum = *((u_int32_t *)msg->data);
451                         if (linkNum < 0 || linkNum >= NG_BRIDGE_MAX_LINKS) {
452                                 error = EINVAL;
453                                 break;
454                         }
455                         if ((link = priv->links[linkNum]) == NULL) {
456                                 error = ENOTCONN;
457                                 break;
458                         }
459
460                         /* Get/clear stats */
461                         if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
462                                 NG_MKRESPONSE(resp, msg,
463                                     sizeof(link->stats), M_NOWAIT);
464                                 if (resp == NULL) {
465                                         error = ENOMEM;
466                                         break;
467                                 }
468                                 bcopy(&link->stats,
469                                     resp->data, sizeof(link->stats));
470                         }
471                         if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
472                                 bzero(&link->stats, sizeof(link->stats));
473                         break;
474                     }
475                 case NGM_BRIDGE_GET_TABLE:
476                     {
477                         struct ng_bridge_host_ary *ary;
478                         struct ng_bridge_hent *hent;
479                         int i = 0, bucket;
480
481                         NG_MKRESPONSE(resp, msg, sizeof(*ary)
482                             + (priv->numHosts * sizeof(*ary->hosts)), M_NOWAIT);
483                         if (resp == NULL) {
484                                 error = ENOMEM;
485                                 break;
486                         }
487                         ary = (struct ng_bridge_host_ary *)resp->data;
488                         ary->numHosts = priv->numHosts;
489                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
490                                 SLIST_FOREACH(hent, &priv->tab[bucket], next)
491                                         ary->hosts[i++] = hent->host;
492                         }
493                         break;
494                     }
495                 default:
496                         error = EINVAL;
497                         break;
498                 }
499                 break;
500         default:
501                 error = EINVAL;
502                 break;
503         }
504
505         /* Done */
506         if (rptr)
507                 *rptr = resp;
508         else if (resp != NULL)
509                 FREE(resp, M_NETGRAPH);
510         FREE(msg, M_NETGRAPH);
511         return (error);
512 }
513
514 /*
515  * Receive data on a hook
516  */
517 static int
518 ng_bridge_rcvdata(hook_p hook, struct mbuf *m, meta_p meta)
519 {
520         const node_p node = hook->node;
521         const priv_p priv = node->private;
522         struct ng_bridge_host *host;
523         struct ng_bridge_link *link;
524         struct ether_header *eh;
525         int error = 0, linkNum;
526         int i, manycast;
527
528         /* Get link number */
529         linkNum = LINK_NUM(hook);
530         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
531             ("%s: linkNum=%u", __FUNCTION__, linkNum));
532         link = priv->links[linkNum];
533         KASSERT(link != NULL, ("%s: link%d null", __FUNCTION__, linkNum));
534
535         /* Sanity check packet and pull up header */
536         if (m->m_pkthdr.len < ETHER_HDR_LEN) {
537                 link->stats.recvRunts++;
538                 NG_FREE_DATA(m, meta);
539                 return (EINVAL);
540         }
541         if (m->m_len < ETHER_HDR_LEN && !(m = m_pullup(m, ETHER_HDR_LEN))) {
542                 link->stats.memoryFailures++;
543                 NG_FREE_META(meta);
544                 return (ENOBUFS);
545         }
546         eh = mtod(m, struct ether_header *);
547         if ((eh->ether_shost[0] & 1) != 0) {
548                 link->stats.recvInvalid++;
549                 NG_FREE_DATA(m, meta);
550                 return (EINVAL);
551         }
552
553         /* Is link disabled due to a loopback condition? */
554         if (link->loopCount != 0) {
555                 link->stats.loopDrops++;
556                 NG_FREE_DATA(m, meta);
557                 return (ELOOP);         /* XXX is this an appropriate error? */
558         }
559
560         /* Update stats */
561         link->stats.recvPackets++;
562         link->stats.recvOctets += m->m_pkthdr.len;
563         if ((manycast = (eh->ether_dhost[0] & 1)) != 0) {
564                 if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
565                         link->stats.recvBroadcasts++;
566                         manycast = 2;
567                 } else
568                         link->stats.recvMulticasts++;
569         }
570
571         /* Look up packet's source Ethernet address in hashtable */
572         if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
573
574                 /* Update time since last heard from this host */
575                 host->staleness = 0;
576
577                 /* Did host jump to a different link? */
578                 if (host->linkNum != linkNum) {
579
580                         /*
581                          * If the host's old link was recently established
582                          * on the old link and it's already jumped to a new
583                          * link, declare a loopback condition.
584                          */
585                         if (host->age < priv->conf.minStableAge) {
586
587                                 /* Log the problem */
588                                 if (priv->conf.debugLevel >= 2) {
589                                         struct ifnet *ifp = m->m_pkthdr.rcvif;
590                                         char suffix[32];
591
592                                         if (ifp != NULL)
593                                                 snprintf(suffix, sizeof(suffix),
594                                                     " (%s%d)", ifp->if_name,
595                                                     ifp->if_unit);
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", __FUNCTION__, 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             __FUNCTION__, 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", __FUNCTION__, 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", __FUNCTION__));
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", __FUNCTION__, 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 s, bucket;
937         int counter = 0;
938         int linkNum;
939
940         /* If node was shut down, this is the final lingering timeout */
941         s = splnet();
942         if ((node->flags & NG_INVALID) != 0) {
943                 FREE(priv, M_NETGRAPH);
944                 node->private = NULL;
945                 ng_unref(node);
946                 splx(s);
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                             __FUNCTION__, 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", __FUNCTION__, 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", __FUNCTION__, priv->numLinks, counter));
1004
1005         /* Done */
1006         splx(s);
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_NODELEN+1];
1016
1017         if (node->name != NULL)
1018                 snprintf(name, sizeof(name), "%s", node->name);
1019         else
1020                 snprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1021         return name;
1022 }
1023