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