d678ab4c99c92dca2b45e46631379f29c52d3996
[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.11 2008/01/05 14:02:39 swildner 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 | M_ZERO);
305         if (priv == NULL)
306                 return (ENOMEM);
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 | M_ZERO);
312         if (priv->tab == NULL) {
313                 FREE(priv, M_NETGRAPH);
314                 return (ENOMEM);
315         }
316         priv->numBuckets = MIN_BUCKETS;
317         priv->hashMask = MIN_BUCKETS - 1;
318         priv->conf.debugLevel = 1;
319         priv->conf.loopTimeout = DEFAULT_LOOP_TIMEOUT;
320         priv->conf.maxStaleness = DEFAULT_MAX_STALENESS;
321         priv->conf.minStableAge = DEFAULT_MIN_STABLE_AGE;
322
323         /* Call superclass constructor */
324         if ((error = ng_make_node_common(&ng_bridge_typestruct, nodep))) {
325                 FREE(priv, M_NETGRAPH);
326                 return (error);
327         }
328         (*nodep)->private = priv;
329         priv->node = *nodep;
330
331         /* Start timer; timer is always running while node is alive */
332         callout_reset(&priv->timer, hz, ng_bridge_timeout, priv->node);
333
334         /* Done */
335         return (0);
336 }
337
338 /*
339  * Method for attaching a new hook
340  */
341 static  int
342 ng_bridge_newhook(node_p node, hook_p hook, const char *name)
343 {
344         const priv_p priv = node->private;
345
346         /* Check for a link hook */
347         if (strncmp(name, NG_BRIDGE_HOOK_LINK_PREFIX,
348             strlen(NG_BRIDGE_HOOK_LINK_PREFIX)) == 0) {
349                 const char *cp;
350                 char *eptr;
351                 u_long linkNum;
352
353                 cp = name + strlen(NG_BRIDGE_HOOK_LINK_PREFIX);
354                 if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0'))
355                         return (EINVAL);
356                 linkNum = strtoul(cp, &eptr, 10);
357                 if (*eptr != '\0' || linkNum >= NG_BRIDGE_MAX_LINKS)
358                         return (EINVAL);
359                 if (priv->links[linkNum] != NULL)
360                         return (EISCONN);
361                 MALLOC(priv->links[linkNum], struct ng_bridge_link *,
362                     sizeof(*priv->links[linkNum]), M_NETGRAPH, M_NOWAIT);
363                 if (priv->links[linkNum] == NULL)
364                         return (ENOMEM);
365                 bzero(priv->links[linkNum], sizeof(*priv->links[linkNum]));
366                 priv->links[linkNum]->hook = hook;
367                 LINK_NUM(hook) = linkNum;
368                 priv->numLinks++;
369                 return (0);
370         }
371
372         /* Unknown hook name */
373         return (EINVAL);
374 }
375
376 /*
377  * Receive a control message
378  */
379 static int
380 ng_bridge_rcvmsg(node_p node, struct ng_mesg *msg,
381         const char *retaddr, struct ng_mesg **rptr)
382 {
383         const priv_p priv = node->private;
384         struct ng_mesg *resp = NULL;
385         int error = 0;
386
387         switch (msg->header.typecookie) {
388         case NGM_BRIDGE_COOKIE:
389                 switch (msg->header.cmd) {
390                 case NGM_BRIDGE_GET_CONFIG:
391                     {
392                         struct ng_bridge_config *conf;
393
394                         NG_MKRESPONSE(resp, msg,
395                             sizeof(struct ng_bridge_config), M_NOWAIT);
396                         if (resp == NULL) {
397                                 error = ENOMEM;
398                                 break;
399                         }
400                         conf = (struct ng_bridge_config *)resp->data;
401                         *conf = priv->conf;     /* no sanity checking needed */
402                         break;
403                     }
404                 case NGM_BRIDGE_SET_CONFIG:
405                     {
406                         struct ng_bridge_config *conf;
407                         int i;
408
409                         if (msg->header.arglen
410                             != sizeof(struct ng_bridge_config)) {
411                                 error = EINVAL;
412                                 break;
413                         }
414                         conf = (struct ng_bridge_config *)msg->data;
415                         priv->conf = *conf;
416                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++)
417                                 priv->conf.ipfw[i] = !!priv->conf.ipfw[i];
418                         break;
419                     }
420                 case NGM_BRIDGE_RESET:
421                     {
422                         int i;
423
424                         /* Flush all entries in the hash table */
425                         ng_bridge_remove_hosts(priv, -1);
426
427                         /* Reset all loop detection counters and stats */
428                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++) {
429                                 if (priv->links[i] == NULL)
430                                         continue;
431                                 priv->links[i]->loopCount = 0;
432                                 bzero(&priv->links[i]->stats,
433                                     sizeof(priv->links[i]->stats));
434                         }
435                         break;
436                     }
437                 case NGM_BRIDGE_GET_STATS:
438                 case NGM_BRIDGE_CLR_STATS:
439                 case NGM_BRIDGE_GETCLR_STATS:
440                     {
441                         struct ng_bridge_link *link;
442                         int linkNum;
443
444                         /* Get link number */
445                         if (msg->header.arglen != sizeof(u_int32_t)) {
446                                 error = EINVAL;
447                                 break;
448                         }
449                         linkNum = *((u_int32_t *)msg->data);
450                         if (linkNum < 0 || linkNum >= NG_BRIDGE_MAX_LINKS) {
451                                 error = EINVAL;
452                                 break;
453                         }
454                         if ((link = priv->links[linkNum]) == NULL) {
455                                 error = ENOTCONN;
456                                 break;
457                         }
458
459                         /* Get/clear stats */
460                         if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
461                                 NG_MKRESPONSE(resp, msg,
462                                     sizeof(link->stats), M_NOWAIT);
463                                 if (resp == NULL) {
464                                         error = ENOMEM;
465                                         break;
466                                 }
467                                 bcopy(&link->stats,
468                                     resp->data, sizeof(link->stats));
469                         }
470                         if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
471                                 bzero(&link->stats, sizeof(link->stats));
472                         break;
473                     }
474                 case NGM_BRIDGE_GET_TABLE:
475                     {
476                         struct ng_bridge_host_ary *ary;
477                         struct ng_bridge_hent *hent;
478                         int i = 0, bucket;
479
480                         NG_MKRESPONSE(resp, msg, sizeof(*ary)
481                             + (priv->numHosts * sizeof(*ary->hosts)), M_NOWAIT);
482                         if (resp == NULL) {
483                                 error = ENOMEM;
484                                 break;
485                         }
486                         ary = (struct ng_bridge_host_ary *)resp->data;
487                         ary->numHosts = priv->numHosts;
488                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
489                                 SLIST_FOREACH(hent, &priv->tab[bucket], next)
490                                         ary->hosts[i++] = hent->host;
491                         }
492                         break;
493                     }
494                 default:
495                         error = EINVAL;
496                         break;
497                 }
498                 break;
499         default:
500                 error = EINVAL;
501                 break;
502         }
503
504         /* Done */
505         if (rptr)
506                 *rptr = resp;
507         else if (resp != NULL)
508                 FREE(resp, M_NETGRAPH);
509         FREE(msg, M_NETGRAPH);
510         return (error);
511 }
512
513 /*
514  * Receive data on a hook
515  */
516 static int
517 ng_bridge_rcvdata(hook_p hook, struct mbuf *m, meta_p meta)
518 {
519         const node_p node = hook->node;
520         const priv_p priv = node->private;
521         struct ng_bridge_host *host;
522         struct ng_bridge_link *link;
523         struct ether_header *eh;
524         int error = 0, linkNum;
525         int i, manycast;
526
527         /* Get link number */
528         linkNum = LINK_NUM(hook);
529         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
530             ("%s: linkNum=%u", __func__, linkNum));
531         link = priv->links[linkNum];
532         KASSERT(link != NULL, ("%s: link%d null", __func__, linkNum));
533
534         /* Sanity check packet and pull up header */
535         if (m->m_pkthdr.len < ETHER_HDR_LEN) {
536                 link->stats.recvRunts++;
537                 NG_FREE_DATA(m, meta);
538                 return (EINVAL);
539         }
540         if (m->m_len < ETHER_HDR_LEN && !(m = m_pullup(m, ETHER_HDR_LEN))) {
541                 link->stats.memoryFailures++;
542                 NG_FREE_META(meta);
543                 return (ENOBUFS);
544         }
545         eh = mtod(m, struct ether_header *);
546         if ((eh->ether_shost[0] & 1) != 0) {
547                 link->stats.recvInvalid++;
548                 NG_FREE_DATA(m, meta);
549                 return (EINVAL);
550         }
551
552         /* Is link disabled due to a loopback condition? */
553         if (link->loopCount != 0) {
554                 link->stats.loopDrops++;
555                 NG_FREE_DATA(m, meta);
556                 return (ELOOP);         /* XXX is this an appropriate error? */
557         }
558
559         /* Update stats */
560         link->stats.recvPackets++;
561         link->stats.recvOctets += m->m_pkthdr.len;
562         if ((manycast = (eh->ether_dhost[0] & 1)) != 0) {
563                 if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
564                         link->stats.recvBroadcasts++;
565                         manycast = 2;
566                 } else
567                         link->stats.recvMulticasts++;
568         }
569
570         /* Look up packet's source Ethernet address in hashtable */
571         if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
572
573                 /* Update time since last heard from this host */
574                 host->staleness = 0;
575
576                 /* Did host jump to a different link? */
577                 if (host->linkNum != linkNum) {
578
579                         /*
580                          * If the host's old link was recently established
581                          * on the old link and it's already jumped to a new
582                          * link, declare a loopback condition.
583                          */
584                         if (host->age < priv->conf.minStableAge) {
585
586                                 /* Log the problem */
587                                 if (priv->conf.debugLevel >= 2) {
588                                         struct ifnet *ifp = m->m_pkthdr.rcvif;
589                                         char suffix[32];
590
591                                         if (ifp != NULL)
592                                                 ksnprintf(suffix, sizeof(suffix),
593                                                     " (%s)", ifp->if_xname);
594                                         else
595                                                 *suffix = '\0';
596                                         log(LOG_WARNING, "ng_bridge: %s:"
597                                             " loopback detected on %s%s\n",
598                                             ng_bridge_nodename(node),
599                                             hook->name, suffix);
600                                 }
601
602                                 /* Mark link as linka non grata */
603                                 link->loopCount = priv->conf.loopTimeout;
604                                 link->stats.loopDetects++;
605
606                                 /* Forget all hosts on this link */
607                                 ng_bridge_remove_hosts(priv, linkNum);
608
609                                 /* Drop packet */
610                                 link->stats.loopDrops++;
611                                 NG_FREE_DATA(m, meta);
612                                 return (ELOOP);         /* XXX appropriate? */
613                         }
614
615                         /* Move host over to new link */
616                         host->linkNum = linkNum;
617                         host->age = 0;
618                 }
619         } else {
620                 if (!ng_bridge_put(priv, eh->ether_shost, linkNum)) {
621                         link->stats.memoryFailures++;
622                         NG_FREE_DATA(m, meta);
623                         return (ENOMEM);
624                 }
625         }
626
627         /* Run packet through ipfw processing, if enabled */
628         if (priv->conf.ipfw[linkNum] && fw_enable && ip_fw_chk_ptr != NULL) {
629                 /* XXX not implemented yet */
630         }
631
632         /*
633          * If unicast and destination host known, deliver to host's link,
634          * unless it is the same link as the packet came in on.
635          */
636         if (!manycast) {
637
638                 /* Determine packet destination link */
639                 if ((host = ng_bridge_get(priv, eh->ether_dhost)) != NULL) {
640                         struct ng_bridge_link *const destLink
641                             = priv->links[host->linkNum];
642
643                         /* If destination same as incoming link, do nothing */
644                         KASSERT(destLink != NULL,
645                             ("%s: link%d null", __func__, host->linkNum));
646                         if (destLink == link) {
647                                 NG_FREE_DATA(m, meta);
648                                 return (0);
649                         }
650
651                         /* Deliver packet out the destination link */
652                         destLink->stats.xmitPackets++;
653                         destLink->stats.xmitOctets += m->m_pkthdr.len;
654                         NG_SEND_DATA(error, destLink->hook, m, meta);
655                         return (error);
656                 }
657
658                 /* Destination host is not known */
659                 link->stats.recvUnknown++;
660         }
661
662         /* Distribute unknown, multicast, broadcast pkts to all other links */
663         for (linkNum = i = 0; i < priv->numLinks - 1; linkNum++) {
664                 struct ng_bridge_link *const destLink = priv->links[linkNum];
665                 meta_p meta2 = NULL;
666                 struct mbuf *m2;
667
668                 /* Skip incoming link and disconnected links */
669                 if (destLink == NULL || destLink == link)
670                         continue;
671
672                 /* Copy mbuf and meta info */
673                 if (++i == priv->numLinks - 1) {                /* last link */
674                         m2 = m;
675                         meta2 = meta;
676                 }  else {
677                         m2 = m_dup(m, M_NOWAIT);        /* XXX m_copypacket() */
678                         if (m2 == NULL) {
679                                 link->stats.memoryFailures++;
680                                 NG_FREE_DATA(m, meta);
681                                 return (ENOBUFS);
682                         }
683                         if (meta != NULL
684                             && (meta2 = ng_copy_meta(meta)) == NULL) {
685                                 link->stats.memoryFailures++;
686                                 m_freem(m2);
687                                 NG_FREE_DATA(m, meta);
688                                 return (ENOMEM);
689                         }
690                 }
691
692                 /* Update stats */
693                 destLink->stats.xmitPackets++;
694                 destLink->stats.xmitOctets += m->m_pkthdr.len;
695                 switch (manycast) {
696                 case 0:                                 /* unicast */
697                         break;
698                 case 1:                                 /* multicast */
699                         destLink->stats.xmitMulticasts++;
700                         break;
701                 case 2:                                 /* broadcast */
702                         destLink->stats.xmitBroadcasts++;
703                         break;
704                 }
705
706                 /* Send packet */
707                 NG_SEND_DATA(error, destLink->hook, m2, meta2);
708         }
709         return (error);
710 }
711
712 /*
713  * Shutdown node
714  */
715 static int
716 ng_bridge_rmnode(node_p node)
717 {
718         const priv_p priv = node->private;
719
720         /*
721          * Shut down everything except the timer. There's no way to
722          * avoid another possible timeout event (it may have already
723          * been dequeued), so we can't free the node yet.
724          */
725         ng_unname(node);
726         ng_cutlinks(node);              /* frees all link and host info */
727         KASSERT(priv->numLinks == 0 && priv->numHosts == 0,
728             ("%s: numLinks=%d numHosts=%d",
729             __func__, priv->numLinks, priv->numHosts));
730         FREE(priv->tab, M_NETGRAPH);
731
732         /* NG_INVALID flag is now set so node will be freed at next timeout */
733         return (0);
734 }
735
736 /*
737  * Hook disconnection.
738  */
739 static int
740 ng_bridge_disconnect(hook_p hook)
741 {
742         const priv_p priv = hook->node->private;
743         int linkNum;
744
745         /* Get link number */
746         linkNum = LINK_NUM(hook);
747         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
748             ("%s: linkNum=%u", __func__, linkNum));
749
750         /* Remove all hosts associated with this link */
751         ng_bridge_remove_hosts(priv, linkNum);
752
753         /* Free associated link information */
754         KASSERT(priv->links[linkNum] != NULL, ("%s: no link", __func__));
755         FREE(priv->links[linkNum], M_NETGRAPH);
756         priv->links[linkNum] = NULL;
757         priv->numLinks--;
758
759         /* If no more hooks, go away */
760         if (hook->node->numhooks == 0)
761                 ng_rmnode(hook->node);
762         return (0);
763 }
764
765 /******************************************************************
766                     HASH TABLE FUNCTIONS
767 ******************************************************************/
768
769 /*
770  * Hash algorithm
771  *
772  * Only hashing bytes 3-6 of the Ethernet address is sufficient and fast.
773  */
774 #define HASH(addr,mask)         ( (((const u_int16_t *)(addr))[0]       \
775                                  ^ ((const u_int16_t *)(addr))[1]       \
776                                  ^ ((const u_int16_t *)(addr))[2]) & (mask) )
777
778 /*
779  * Find a host entry in the table.
780  */
781 static struct ng_bridge_host *
782 ng_bridge_get(priv_p priv, const u_char *addr)
783 {
784         const int bucket = HASH(addr, priv->hashMask);
785         struct ng_bridge_hent *hent;
786
787         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
788                 if (ETHER_EQUAL(hent->host.addr, addr))
789                         return (&hent->host);
790         }
791         return (NULL);
792 }
793
794 /*
795  * Add a new host entry to the table. This assumes the host doesn't
796  * already exist in the table. Returns 1 on success, 0 if there
797  * was a memory allocation failure.
798  */
799 static int
800 ng_bridge_put(priv_p priv, const u_char *addr, int linkNum)
801 {
802         const int bucket = HASH(addr, priv->hashMask);
803         struct ng_bridge_hent *hent;
804
805 #ifdef INVARIANTS
806         /* Assert that entry does not already exist in hashtable */
807         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
808                 KASSERT(!ETHER_EQUAL(hent->host.addr, addr),
809                     ("%s: entry %6D exists in table", __func__, addr, ":"));
810         }
811 #endif
812
813         /* Allocate and initialize new hashtable entry */
814         MALLOC(hent, struct ng_bridge_hent *,
815             sizeof(*hent), M_NETGRAPH, M_NOWAIT);
816         if (hent == NULL)
817                 return (0);
818         bcopy(addr, hent->host.addr, ETHER_ADDR_LEN);
819         hent->host.linkNum = linkNum;
820         hent->host.staleness = 0;
821         hent->host.age = 0;
822
823         /* Add new element to hash bucket */
824         SLIST_INSERT_HEAD(&priv->tab[bucket], hent, next);
825         priv->numHosts++;
826
827         /* Resize table if necessary */
828         ng_bridge_rehash(priv);
829         return (1);
830 }
831
832 /*
833  * Resize the hash table. We try to maintain the number of buckets
834  * such that the load factor is in the range 0.25 to 1.0.
835  *
836  * If we can't get the new memory then we silently fail. This is OK
837  * because things will still work and we'll try again soon anyway.
838  */
839 static void
840 ng_bridge_rehash(priv_p priv)
841 {
842         struct ng_bridge_bucket *newTab;
843         int oldBucket, newBucket;
844         int newNumBuckets;
845         u_int newMask;
846
847         /* Is table too full or too empty? */
848         if (priv->numHosts > priv->numBuckets
849             && (priv->numBuckets << 1) <= MAX_BUCKETS)
850                 newNumBuckets = priv->numBuckets << 1;
851         else if (priv->numHosts < (priv->numBuckets >> 2)
852             && (priv->numBuckets >> 2) >= MIN_BUCKETS)
853                 newNumBuckets = priv->numBuckets >> 2;
854         else
855                 return;
856         newMask = newNumBuckets - 1;
857
858         /* Allocate and initialize new table */
859         MALLOC(newTab, struct ng_bridge_bucket *,
860             newNumBuckets * sizeof(*newTab), M_NETGRAPH, M_NOWAIT | M_ZERO);
861         if (newTab == NULL)
862                 return;
863
864         /* Move all entries from old table to new table */
865         for (oldBucket = 0; oldBucket < priv->numBuckets; oldBucket++) {
866                 struct ng_bridge_bucket *const oldList = &priv->tab[oldBucket];
867
868                 while (!SLIST_EMPTY(oldList)) {
869                         struct ng_bridge_hent *const hent
870                             = SLIST_FIRST(oldList);
871
872                         SLIST_REMOVE_HEAD(oldList, next);
873                         newBucket = HASH(hent->host.addr, newMask);
874                         SLIST_INSERT_HEAD(&newTab[newBucket], hent, next);
875                 }
876         }
877
878         /* Replace old table with new one */
879         if (priv->conf.debugLevel >= 3) {
880                 log(LOG_INFO, "ng_bridge: %s: table size %d -> %d\n",
881                     ng_bridge_nodename(priv->node),
882                     priv->numBuckets, newNumBuckets);
883         }
884         FREE(priv->tab, M_NETGRAPH);
885         priv->numBuckets = newNumBuckets;
886         priv->hashMask = newMask;
887         priv->tab = newTab;
888         return;
889 }
890
891 /******************************************************************
892                     MISC FUNCTIONS
893 ******************************************************************/
894
895 /*
896  * Remove all hosts associated with a specific link from the hashtable.
897  * If linkNum == -1, then remove all hosts in the table.
898  */
899 static void
900 ng_bridge_remove_hosts(priv_p priv, int linkNum)
901 {
902         int bucket;
903
904         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
905                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
906
907                 while (*hptr != NULL) {
908                         struct ng_bridge_hent *const hent = *hptr;
909
910                         if (linkNum == -1 || hent->host.linkNum == linkNum) {
911                                 *hptr = SLIST_NEXT(hent, next);
912                                 FREE(hent, M_NETGRAPH);
913                                 priv->numHosts--;
914                         } else
915                                 hptr = &SLIST_NEXT(hent, next);
916                 }
917         }
918 }
919
920 /*
921  * Handle our once-per-second timeout event. We do two things:
922  * we decrement link->loopCount for those links being muted due to
923  * a detected loopback condition, and we remove any hosts from
924  * the hashtable whom we haven't heard from in a long while.
925  *
926  * If the node has the NG_INVALID flag set, our job is to kill it.
927  */
928 static void
929 ng_bridge_timeout(void *arg)
930 {
931         const node_p node = arg;
932         const priv_p priv = node->private;
933         int bucket;
934         int counter = 0;
935         int linkNum;
936
937         /* If node was shut down, this is the final lingering timeout */
938         crit_enter();
939         if ((node->flags & NG_INVALID) != 0) {
940                 FREE(priv, M_NETGRAPH);
941                 node->private = NULL;
942                 ng_unref(node);
943                 crit_exit();
944                 return;
945         }
946
947         /* Register a new timeout, keeping the existing node reference */
948         callout_reset(&priv->timer, hz, ng_bridge_timeout, node);
949
950         /* Update host time counters and remove stale entries */
951         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
952                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
953
954                 while (*hptr != NULL) {
955                         struct ng_bridge_hent *const hent = *hptr;
956
957                         /* Make sure host's link really exists */
958                         KASSERT(priv->links[hent->host.linkNum] != NULL,
959                             ("%s: host %6D on nonexistent link %d\n",
960                             __func__, hent->host.addr, ":",
961                             hent->host.linkNum));
962
963                         /* Remove hosts we haven't heard from in a while */
964                         if (++hent->host.staleness >= priv->conf.maxStaleness) {
965                                 *hptr = SLIST_NEXT(hent, next);
966                                 FREE(hent, M_NETGRAPH);
967                                 priv->numHosts--;
968                         } else {
969                                 if (hent->host.age < 0xffff)
970                                         hent->host.age++;
971                                 hptr = &SLIST_NEXT(hent, next);
972                                 counter++;
973                         }
974                 }
975         }
976         KASSERT(priv->numHosts == counter,
977             ("%s: hosts: %d != %d", __func__, priv->numHosts, counter));
978
979         /* Decrease table size if necessary */
980         ng_bridge_rehash(priv);
981
982         /* Decrease loop counter on muted looped back links */
983         for (counter = linkNum = 0; linkNum < NG_BRIDGE_MAX_LINKS; linkNum++) {
984                 struct ng_bridge_link *const link = priv->links[linkNum];
985
986                 if (link != NULL) {
987                         if (link->loopCount != 0) {
988                                 link->loopCount--;
989                                 if (link->loopCount == 0
990                                     && priv->conf.debugLevel >= 2) {
991                                         log(LOG_INFO, "ng_bridge: %s:"
992                                             " restoring looped back link%d\n",
993                                             ng_bridge_nodename(node), linkNum);
994                                 }
995                         }
996                         counter++;
997                 }
998         }
999         KASSERT(priv->numLinks == counter,
1000             ("%s: links: %d != %d", __func__, priv->numLinks, counter));
1001
1002         /* Done */
1003         crit_exit();
1004 }
1005
1006 /*
1007  * Return node's "name", even if it doesn't have one.
1008  */
1009 static const char *
1010 ng_bridge_nodename(node_p node)
1011 {
1012         static char name[NG_NODESIZ];
1013
1014         if (node->name != NULL)
1015                 ksnprintf(name, sizeof(name), "%s", node->name);
1016         else
1017                 ksnprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1018         return name;
1019 }
1020