kernel/netgraph7: Use kether_ntoa().
[dragonfly.git] / sys / netgraph7 / bridge / 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  */
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 <netgraph7/ng_message.h>
78 #include <netgraph7/netgraph.h>
79 #include <netgraph7/ng_parse.h>
80 #include "ng_bridge.h"
81
82 #ifdef NG_SEPARATE_MALLOC
83 MALLOC_DEFINE(M_NETGRAPH_BRIDGE, "netgraph_bridge", "netgraph bridge node ");
84 #else
85 #define M_NETGRAPH_BRIDGE M_NETGRAPH
86 #endif
87
88 /* Per-link private data */
89 struct ng_bridge_link {
90         hook_p                          hook;           /* netgraph hook */
91         u_int16_t                       loopCount;      /* loop ignore timer */
92         struct ng_bridge_link_stats     stats;          /* link stats */
93 };
94
95 /* Per-node private data */
96 struct ng_bridge_private {
97         struct ng_bridge_bucket *tab;           /* hash table bucket array */
98         struct ng_bridge_link   *links[NG_BRIDGE_MAX_LINKS];
99         struct ng_bridge_config conf;           /* node configuration */
100         node_p                  node;           /* netgraph node */
101         u_int                   numHosts;       /* num entries in table */
102         u_int                   numBuckets;     /* num buckets in table */
103         u_int                   hashMask;       /* numBuckets - 1 */
104         int                     numLinks;       /* num connected links */
105         struct callout          timer;          /* one second periodic timer */
106 };
107 typedef struct ng_bridge_private *priv_p;
108
109 /* Information about a host, stored in a hash table entry */
110 struct ng_bridge_hent {
111         struct ng_bridge_host           host;   /* actual host info */
112         SLIST_ENTRY(ng_bridge_hent)     next;   /* next entry in bucket */
113 };
114
115 /* Hash table bucket declaration */
116 SLIST_HEAD(ng_bridge_bucket, ng_bridge_hent);
117
118 /* Netgraph node methods */
119 static ng_constructor_t ng_bridge_constructor;
120 static ng_rcvmsg_t      ng_bridge_rcvmsg;
121 static ng_shutdown_t    ng_bridge_shutdown;
122 static ng_newhook_t     ng_bridge_newhook;
123 static ng_rcvdata_t     ng_bridge_rcvdata;
124 static ng_disconnect_t  ng_bridge_disconnect;
125
126 /* Other internal functions */
127 static struct   ng_bridge_host *ng_bridge_get(priv_p priv, const u_char *addr);
128 static int      ng_bridge_put(priv_p priv, const u_char *addr, int linkNum);
129 static void     ng_bridge_rehash(priv_p priv);
130 static void     ng_bridge_remove_hosts(priv_p priv, int linkNum);
131 static void     ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2);
132 static const    char *ng_bridge_nodename(node_p node);
133
134 /* Ethernet broadcast */
135 static const u_char ng_bridge_bcast_addr[ETHER_ADDR_LEN] =
136     { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
137
138 /* Store each hook's link number in the private field */
139 #define LINK_NUM(hook)          (*(u_int16_t *)(&(hook)->private))
140
141 /* Compare Ethernet addresses using 32 and 16 bit words instead of bytewise */
142 #define ETHER_EQUAL(a,b)        (((const u_int32_t *)(a))[0] \
143                                         == ((const u_int32_t *)(b))[0] \
144                                     && ((const u_int16_t *)(a))[2] \
145                                         == ((const u_int16_t *)(b))[2])
146
147 /* Minimum and maximum number of hash buckets. Must be a power of two. */
148 #define MIN_BUCKETS             (1 << 5)        /* 32 */
149 #define MAX_BUCKETS             (1 << 14)       /* 16384 */
150
151 /* Configuration default values */
152 #define DEFAULT_LOOP_TIMEOUT    60
153 #define DEFAULT_MAX_STALENESS   (15 * 60)       /* same as ARP timeout */
154 #define DEFAULT_MIN_STABLE_AGE  1
155
156 /******************************************************************
157                     NETGRAPH PARSE TYPES
158 ******************************************************************/
159
160 /*
161  * How to determine the length of the table returned by NGM_BRIDGE_GET_TABLE
162  */
163 static int
164 ng_bridge_getTableLength(const struct ng_parse_type *type,
165         const u_char *start, const u_char *buf)
166 {
167         const struct ng_bridge_host_ary *const hary
168             = (const struct ng_bridge_host_ary *)(buf - sizeof(u_int32_t));
169
170         return hary->numHosts;
171 }
172
173 /* Parse type for struct ng_bridge_host_ary */
174 static const struct ng_parse_struct_field ng_bridge_host_type_fields[]
175         = NG_BRIDGE_HOST_TYPE_INFO(&ng_parse_enaddr_type);
176 static const struct ng_parse_type ng_bridge_host_type = {
177         &ng_parse_struct_type,
178         &ng_bridge_host_type_fields
179 };
180 static const struct ng_parse_array_info ng_bridge_hary_type_info = {
181         &ng_bridge_host_type,
182         ng_bridge_getTableLength
183 };
184 static const struct ng_parse_type ng_bridge_hary_type = {
185         &ng_parse_array_type,
186         &ng_bridge_hary_type_info
187 };
188 static const struct ng_parse_struct_field ng_bridge_host_ary_type_fields[]
189         = NG_BRIDGE_HOST_ARY_TYPE_INFO(&ng_bridge_hary_type);
190 static const struct ng_parse_type ng_bridge_host_ary_type = {
191         &ng_parse_struct_type,
192         &ng_bridge_host_ary_type_fields
193 };
194
195 /* Parse type for struct ng_bridge_config */
196 static const struct ng_parse_fixedarray_info ng_bridge_ipfwary_type_info = {
197         &ng_parse_uint8_type,
198         NG_BRIDGE_MAX_LINKS
199 };
200 static const struct ng_parse_type ng_bridge_ipfwary_type = {
201         &ng_parse_fixedarray_type,
202         &ng_bridge_ipfwary_type_info
203 };
204 static const struct ng_parse_struct_field ng_bridge_config_type_fields[]
205         = NG_BRIDGE_CONFIG_TYPE_INFO(&ng_bridge_ipfwary_type);
206 static const struct ng_parse_type ng_bridge_config_type = {
207         &ng_parse_struct_type,
208         &ng_bridge_config_type_fields
209 };
210
211 /* Parse type for struct ng_bridge_link_stat */
212 static const struct ng_parse_struct_field ng_bridge_stats_type_fields[]
213         = NG_BRIDGE_STATS_TYPE_INFO;
214 static const struct ng_parse_type ng_bridge_stats_type = {
215         &ng_parse_struct_type,
216         &ng_bridge_stats_type_fields
217 };
218
219 /* List of commands and how to convert arguments to/from ASCII */
220 static const struct ng_cmdlist ng_bridge_cmdlist[] = {
221         {
222           NGM_BRIDGE_COOKIE,
223           NGM_BRIDGE_SET_CONFIG,
224           "setconfig",
225           &ng_bridge_config_type,
226           NULL
227         },
228         {
229           NGM_BRIDGE_COOKIE,
230           NGM_BRIDGE_GET_CONFIG,
231           "getconfig",
232           NULL,
233           &ng_bridge_config_type
234         },
235         {
236           NGM_BRIDGE_COOKIE,
237           NGM_BRIDGE_RESET,
238           "reset",
239           NULL,
240           NULL
241         },
242         {
243           NGM_BRIDGE_COOKIE,
244           NGM_BRIDGE_GET_STATS,
245           "getstats",
246           &ng_parse_uint32_type,
247           &ng_bridge_stats_type
248         },
249         {
250           NGM_BRIDGE_COOKIE,
251           NGM_BRIDGE_CLR_STATS,
252           "clrstats",
253           &ng_parse_uint32_type,
254           NULL
255         },
256         {
257           NGM_BRIDGE_COOKIE,
258           NGM_BRIDGE_GETCLR_STATS,
259           "getclrstats",
260           &ng_parse_uint32_type,
261           &ng_bridge_stats_type
262         },
263         {
264           NGM_BRIDGE_COOKIE,
265           NGM_BRIDGE_GET_TABLE,
266           "gettable",
267           NULL,
268           &ng_bridge_host_ary_type
269         },
270         { 0 }
271 };
272
273 /* Node type descriptor */
274 static struct ng_type ng_bridge_typestruct = {
275         .version =      NG_ABI_VERSION,
276         .name =         NG_BRIDGE_NODE_TYPE,
277         .constructor =  ng_bridge_constructor,
278         .rcvmsg =       ng_bridge_rcvmsg,
279         .shutdown =     ng_bridge_shutdown,
280         .newhook =      ng_bridge_newhook,
281         .rcvdata =      ng_bridge_rcvdata,
282         .disconnect =   ng_bridge_disconnect,
283         .cmdlist =      ng_bridge_cmdlist,
284 };
285 NETGRAPH_INIT(bridge, &ng_bridge_typestruct);
286
287 /******************************************************************
288                     NETGRAPH NODE METHODS
289 ******************************************************************/
290
291 /*
292  * Node constructor
293  */
294 static int
295 ng_bridge_constructor(node_p node)
296 {
297         priv_p priv;
298
299         /* Allocate and initialize private info */
300         priv = kmalloc(sizeof(*priv), M_NETGRAPH_BRIDGE,
301                        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         priv->tab = kmalloc(MIN_BUCKETS * sizeof(*priv->tab),
308                             M_NETGRAPH_BRIDGE, M_WAITOK | M_NULLOK | M_ZERO);
309         if (priv->tab == NULL) {
310                 kfree(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                 priv->links[linkNum] = kmalloc(sizeof(*priv->links[linkNum]),
363                                                M_NETGRAPH_BRIDGE,
364                                                M_WAITOK | M_NULLOK | M_ZERO);
365                 if (priv->links[linkNum] == NULL)
366                         return (ENOMEM);
367                 priv->links[linkNum]->hook = hook;
368                 NG_HOOK_SET_PRIVATE(hook, (void *)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, item_p item, hook_p lasthook)
382 {
383         const priv_p priv = NG_NODE_PRIVATE(node);
384         struct ng_mesg *resp = NULL;
385         int error = 0;
386         struct ng_mesg *msg;
387
388         NGI_GET_MSG(item, msg);
389         switch (msg->header.typecookie) {
390         case NGM_BRIDGE_COOKIE:
391                 switch (msg->header.cmd) {
392                 case NGM_BRIDGE_GET_CONFIG:
393                     {
394                         struct ng_bridge_config *conf;
395
396                         NG_MKRESPONSE(resp, msg,
397                             sizeof(struct ng_bridge_config), M_WAITOK | M_NULLOK);
398                         if (resp == NULL) {
399                                 error = ENOMEM;
400                                 break;
401                         }
402                         conf = (struct ng_bridge_config *)resp->data;
403                         *conf = priv->conf;     /* no sanity checking needed */
404                         break;
405                     }
406                 case NGM_BRIDGE_SET_CONFIG:
407                     {
408                         struct ng_bridge_config *conf;
409                         int i;
410
411                         if (msg->header.arglen
412                             != sizeof(struct ng_bridge_config)) {
413                                 error = EINVAL;
414                                 break;
415                         }
416                         conf = (struct ng_bridge_config *)msg->data;
417                         priv->conf = *conf;
418                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++)
419                                 priv->conf.ipfw[i] = !!priv->conf.ipfw[i];
420                         break;
421                     }
422                 case NGM_BRIDGE_RESET:
423                     {
424                         int i;
425
426                         /* Flush all entries in the hash table */
427                         ng_bridge_remove_hosts(priv, -1);
428
429                         /* Reset all loop detection counters and stats */
430                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++) {
431                                 if (priv->links[i] == NULL)
432                                         continue;
433                                 priv->links[i]->loopCount = 0;
434                                 bzero(&priv->links[i]->stats,
435                                     sizeof(priv->links[i]->stats));
436                         }
437                         break;
438                     }
439                 case NGM_BRIDGE_GET_STATS:
440                 case NGM_BRIDGE_CLR_STATS:
441                 case NGM_BRIDGE_GETCLR_STATS:
442                     {
443                         struct ng_bridge_link *link;
444                         int linkNum;
445
446                         /* Get link number */
447                         if (msg->header.arglen != sizeof(u_int32_t)) {
448                                 error = EINVAL;
449                                 break;
450                         }
451                         linkNum = *((u_int32_t *)msg->data);
452                         if (linkNum < 0 || linkNum >= NG_BRIDGE_MAX_LINKS) {
453                                 error = EINVAL;
454                                 break;
455                         }
456                         if ((link = priv->links[linkNum]) == NULL) {
457                                 error = ENOTCONN;
458                                 break;
459                         }
460
461                         /* Get/clear stats */
462                         if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
463                                 NG_MKRESPONSE(resp, msg,
464                                     sizeof(link->stats), M_WAITOK | M_NULLOK);
465                                 if (resp == NULL) {
466                                         error = ENOMEM;
467                                         break;
468                                 }
469                                 bcopy(&link->stats,
470                                     resp->data, sizeof(link->stats));
471                         }
472                         if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
473                                 bzero(&link->stats, sizeof(link->stats));
474                         break;
475                     }
476                 case NGM_BRIDGE_GET_TABLE:
477                     {
478                         struct ng_bridge_host_ary *ary;
479                         struct ng_bridge_hent *hent;
480                         int i = 0, bucket;
481
482                         NG_MKRESPONSE(resp, msg, sizeof(*ary)
483                             + (priv->numHosts * sizeof(*ary->hosts)), M_WAITOK | M_NULLOK);
484                         if (resp == NULL) {
485                                 error = ENOMEM;
486                                 break;
487                         }
488                         ary = (struct ng_bridge_host_ary *)resp->data;
489                         ary->numHosts = priv->numHosts;
490                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
491                                 SLIST_FOREACH(hent, &priv->tab[bucket], next)
492                                         ary->hosts[i++] = hent->host;
493                         }
494                         break;
495                     }
496                 default:
497                         error = EINVAL;
498                         break;
499                 }
500                 break;
501         default:
502                 error = EINVAL;
503                 break;
504         }
505
506         /* Done */
507         NG_RESPOND_MSG(error, node, item, resp);
508         NG_FREE_MSG(msg);
509         return (error);
510 }
511
512 /*
513  * Receive data on a hook
514  */
515 static int
516 ng_bridge_rcvdata(hook_p hook, item_p item)
517 {
518         const node_p node = NG_HOOK_NODE(hook);
519         const priv_p priv = NG_NODE_PRIVATE(node);
520         struct ng_bridge_host *host;
521         struct ng_bridge_link *link;
522         struct ether_header *eh;
523         int error = 0, linkNum, linksSeen;
524         int manycast;
525         struct mbuf *m;
526         struct ng_bridge_link *firstLink;
527
528         NGI_GET_M(item, m);
529         /* Get link number */
530         linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
531         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
532             ("%s: linkNum=%u", __func__, linkNum));
533         link = priv->links[linkNum];
534         KASSERT(link != NULL, ("%s: link%d null", __func__, linkNum));
535
536         /* Sanity check packet and pull up header */
537         if (m->m_pkthdr.len < ETHER_HDR_LEN) {
538                 link->stats.recvRunts++;
539                 NG_FREE_ITEM(item);
540                 NG_FREE_M(m);
541                 return (EINVAL);
542         }
543         if (m->m_len < ETHER_HDR_LEN && !(m = m_pullup(m, ETHER_HDR_LEN))) {
544                 link->stats.memoryFailures++;
545                 NG_FREE_ITEM(item);
546                 return (ENOBUFS);
547         }
548         eh = mtod(m, struct ether_header *);
549         if ((eh->ether_shost[0] & 1) != 0) {
550                 link->stats.recvInvalid++;
551                 NG_FREE_ITEM(item);
552                 NG_FREE_M(m);
553                 return (EINVAL);
554         }
555
556         /* Is link disabled due to a loopback condition? */
557         if (link->loopCount != 0) {
558                 link->stats.loopDrops++;
559                 NG_FREE_ITEM(item);
560                 NG_FREE_M(m);
561                 return (ELOOP);         /* XXX is this an appropriate error? */
562         }
563
564         /* Update stats */
565         link->stats.recvPackets++;
566         link->stats.recvOctets += m->m_pkthdr.len;
567         if ((manycast = (eh->ether_dhost[0] & 1)) != 0) {
568                 if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
569                         link->stats.recvBroadcasts++;
570                         manycast = 2;
571                 } else
572                         link->stats.recvMulticasts++;
573         }
574
575         /* Look up packet's source Ethernet address in hashtable */
576         if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
577
578                 /* Update time since last heard from this host */
579                 host->staleness = 0;
580
581                 /* Did host jump to a different link? */
582                 if (host->linkNum != linkNum) {
583
584                         /*
585                          * If the host's old link was recently established
586                          * on the old link and it's already jumped to a new
587                          * link, declare a loopback condition.
588                          */
589                         if (host->age < priv->conf.minStableAge) {
590
591                                 /* Log the problem */
592                                 if (priv->conf.debugLevel >= 2) {
593                                         struct ifnet *ifp = m->m_pkthdr.rcvif;
594                                         char suffix[32];
595
596                                         if (ifp != NULL)
597                                                 snprintf(suffix, sizeof(suffix),
598                                                     " (%s)", ifp->if_xname);
599                                         else
600                                                 *suffix = '\0';
601                                         log(LOG_WARNING, "ng_bridge: %s:"
602                                             " loopback detected on %s%s\n",
603                                             ng_bridge_nodename(node),
604                                             NG_HOOK_NAME(hook), suffix);
605                                 }
606
607                                 /* Mark link as linka non grata */
608                                 link->loopCount = priv->conf.loopTimeout;
609                                 link->stats.loopDetects++;
610
611                                 /* Forget all hosts on this link */
612                                 ng_bridge_remove_hosts(priv, linkNum);
613
614                                 /* Drop packet */
615                                 link->stats.loopDrops++;
616                                 NG_FREE_ITEM(item);
617                                 NG_FREE_M(m);
618                                 return (ELOOP);         /* XXX appropriate? */
619                         }
620
621                         /* Move host over to new link */
622                         host->linkNum = linkNum;
623                         host->age = 0;
624                 }
625         } else {
626                 if (!ng_bridge_put(priv, eh->ether_shost, linkNum)) {
627                         link->stats.memoryFailures++;
628                         NG_FREE_ITEM(item);
629                         NG_FREE_M(m);
630                         return (ENOMEM);
631                 }
632         }
633
634         /* Run packet through ipfw processing, if enabled */
635 #if 0
636         if (priv->conf.ipfw[linkNum] && fw_enable && ip_fw_chk_ptr != NULL) {
637                 /* XXX not implemented yet */
638         }
639 #endif
640
641         /*
642          * If unicast and destination host known, deliver to host's link,
643          * unless it is the same link as the packet came in on.
644          */
645         if (!manycast) {
646
647                 /* Determine packet destination link */
648                 if ((host = ng_bridge_get(priv, eh->ether_dhost)) != NULL) {
649                         struct ng_bridge_link *const destLink
650                             = priv->links[host->linkNum];
651
652                         /* If destination same as incoming link, do nothing */
653                         KASSERT(destLink != NULL,
654                             ("%s: link%d null", __func__, host->linkNum));
655                         if (destLink == link) {
656                                 NG_FREE_ITEM(item);
657                                 NG_FREE_M(m);
658                                 return (0);
659                         }
660
661                         /* Deliver packet out the destination link */
662                         destLink->stats.xmitPackets++;
663                         destLink->stats.xmitOctets += m->m_pkthdr.len;
664                         NG_FWD_NEW_DATA(error, item, destLink->hook, m);
665                         return (error);
666                 }
667
668                 /* Destination host is not known */
669                 link->stats.recvUnknown++;
670         }
671
672         /* Distribute unknown, multicast, broadcast pkts to all other links */
673         firstLink = NULL;
674         for (linkNum = linksSeen = 0; linksSeen <= priv->numLinks; linkNum++) {
675                 struct ng_bridge_link *destLink;
676                 struct mbuf *m2 = NULL;
677
678                 /*
679                  * If we have checked all the links then now
680                  * send the original on its reserved link
681                  */
682                 if (linksSeen == priv->numLinks) {
683                         /* If we never saw a good link, leave. */
684                         if (firstLink == NULL) {
685                                 NG_FREE_ITEM(item);
686                                 NG_FREE_M(m);
687                                 return (0);
688                         }       
689                         destLink = firstLink;
690                 } else {
691                         destLink = priv->links[linkNum];
692                         if (destLink != NULL)
693                                 linksSeen++;
694                         /* Skip incoming link and disconnected links */
695                         if (destLink == NULL || destLink == link) {
696                                 continue;
697                         }
698                         if (firstLink == NULL) {
699                                 /*
700                                  * This is the first usable link we have found.
701                                  * Reserve it for the originals.
702                                  * If we never find another we save a copy.
703                                  */
704                                 firstLink = destLink;
705                                 continue;
706                         }
707
708                         /*
709                          * It's usable link but not the reserved (first) one.
710                          * Copy mbuf info for sending.
711                          */
712                         m2 = m_dup(m, MB_DONTWAIT);     /* XXX m_copypacket() */
713                         if (m2 == NULL) {
714                                 link->stats.memoryFailures++;
715                                 NG_FREE_ITEM(item);
716                                 NG_FREE_M(m);
717                                 return (ENOBUFS);
718                         }
719                 }
720
721                 /* Update stats */
722                 destLink->stats.xmitPackets++;
723                 destLink->stats.xmitOctets += m->m_pkthdr.len;
724                 switch (manycast) {
725                 case 0:                                 /* unicast */
726                         break;
727                 case 1:                                 /* multicast */
728                         destLink->stats.xmitMulticasts++;
729                         break;
730                 case 2:                                 /* broadcast */
731                         destLink->stats.xmitBroadcasts++;
732                         break;
733                 }
734
735                 /* Send packet */
736                 if (destLink == firstLink) { 
737                         /*
738                          * If we've sent all the others, send the original
739                          * on the first link we found.
740                          */
741                         NG_FWD_NEW_DATA(error, item, destLink->hook, m);
742                         break; /* always done last - not really needed. */
743                 } else {
744                         NG_SEND_DATA_ONLY(error, destLink->hook, m2);
745                 }
746         }
747         return (error);
748 }
749
750 /*
751  * Shutdown node
752  */
753 static int
754 ng_bridge_shutdown(node_p node)
755 {
756         const priv_p priv = NG_NODE_PRIVATE(node);
757
758         /*
759          * Shut down everything including the timer.  Even if the
760          * callout has already been dequeued and is about to be
761          * run, ng_bridge_timeout() won't be fired as the node
762          * is already marked NGF_INVALID, so we're safe to free
763          * the node now.
764          */
765         KASSERT(priv->numLinks == 0 && priv->numHosts == 0,
766             ("%s: numLinks=%d numHosts=%d",
767             __func__, priv->numLinks, priv->numHosts));
768         ng_uncallout(&priv->timer, node);
769         NG_NODE_SET_PRIVATE(node, NULL);
770         NG_NODE_UNREF(node);
771         kfree(priv->tab, M_NETGRAPH_BRIDGE);
772         kfree(priv, M_NETGRAPH_BRIDGE);
773         return (0);
774 }
775
776 /*
777  * Hook disconnection.
778  */
779 static int
780 ng_bridge_disconnect(hook_p hook)
781 {
782         const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hook));
783         int linkNum;
784
785         /* Get link number */
786         linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
787         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
788             ("%s: linkNum=%u", __func__, linkNum));
789
790         /* Remove all hosts associated with this link */
791         ng_bridge_remove_hosts(priv, linkNum);
792
793         /* Free associated link information */
794         KASSERT(priv->links[linkNum] != NULL, ("%s: no link", __func__));
795         kfree(priv->links[linkNum], M_NETGRAPH_BRIDGE);
796         priv->links[linkNum] = NULL;
797         priv->numLinks--;
798
799         /* If no more hooks, go away */
800         if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
801         && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))) {
802                 ng_rmnode_self(NG_HOOK_NODE(hook));
803         }
804         return (0);
805 }
806
807 /******************************************************************
808                     HASH TABLE FUNCTIONS
809 ******************************************************************/
810
811 /*
812  * Hash algorithm
813  */
814 #define HASH(addr,mask)         ( (((const u_int16_t *)(addr))[0]       \
815                                  ^ ((const u_int16_t *)(addr))[1]       \
816                                  ^ ((const u_int16_t *)(addr))[2]) & (mask) )
817
818 /*
819  * Find a host entry in the table.
820  */
821 static struct ng_bridge_host *
822 ng_bridge_get(priv_p priv, const u_char *addr)
823 {
824         const int bucket = HASH(addr, priv->hashMask);
825         struct ng_bridge_hent *hent;
826
827         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
828                 if (ETHER_EQUAL(hent->host.addr, addr))
829                         return (&hent->host);
830         }
831         return (NULL);
832 }
833
834 /*
835  * Add a new host entry to the table. This assumes the host doesn't
836  * already exist in the table. Returns 1 on success, 0 if there
837  * was a memory allocation failure.
838  */
839 static int
840 ng_bridge_put(priv_p priv, const u_char *addr, int linkNum)
841 {
842         const int bucket = HASH(addr, priv->hashMask);
843         struct ng_bridge_hent *hent;
844         char ethstr[ETHER_ADDRSTRLEN + 1] __debugvar;
845
846 #ifdef INVARIANTS
847         /* Assert that entry does not already exist in hashtable */
848         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
849                 KASSERT(!ETHER_EQUAL(hent->host.addr, addr),
850                     ("%s: entry %s exists in table", __func__, kether_ntoa(addr, ethstr)));
851         }
852 #endif
853
854         /* Allocate and initialize new hashtable entry */
855         hent = kmalloc(sizeof(*hent), M_NETGRAPH_BRIDGE, M_WAITOK | M_NULLOK);
856         if (hent == NULL)
857                 return (0);
858         bcopy(addr, hent->host.addr, ETHER_ADDR_LEN);
859         hent->host.linkNum = linkNum;
860         hent->host.staleness = 0;
861         hent->host.age = 0;
862
863         /* Add new element to hash bucket */
864         SLIST_INSERT_HEAD(&priv->tab[bucket], hent, next);
865         priv->numHosts++;
866
867         /* Resize table if necessary */
868         ng_bridge_rehash(priv);
869         return (1);
870 }
871
872 /*
873  * Resize the hash table. We try to maintain the number of buckets
874  * such that the load factor is in the range 0.25 to 1.0.
875  *
876  * If we can't get the new memory then we silently fail. This is OK
877  * because things will still work and we'll try again soon anyway.
878  */
879 static void
880 ng_bridge_rehash(priv_p priv)
881 {
882         struct ng_bridge_bucket *newTab;
883         int oldBucket, newBucket;
884         int newNumBuckets;
885         u_int newMask;
886
887         /* Is table too full or too empty? */
888         if (priv->numHosts > priv->numBuckets
889             && (priv->numBuckets << 1) <= MAX_BUCKETS)
890                 newNumBuckets = priv->numBuckets << 1;
891         else if (priv->numHosts < (priv->numBuckets >> 2)
892             && (priv->numBuckets >> 2) >= MIN_BUCKETS)
893                 newNumBuckets = priv->numBuckets >> 2;
894         else
895                 return;
896         newMask = newNumBuckets - 1;
897
898         /* Allocate and initialize new table */
899         newTab = kmalloc(newNumBuckets * sizeof(*newTab), M_NETGRAPH_BRIDGE,
900                          M_NOWAIT | M_ZERO);
901         if (newTab == NULL)
902                 return;
903
904         /* Move all entries from old table to new table */
905         for (oldBucket = 0; oldBucket < priv->numBuckets; oldBucket++) {
906                 struct ng_bridge_bucket *const oldList = &priv->tab[oldBucket];
907
908                 while (!SLIST_EMPTY(oldList)) {
909                         struct ng_bridge_hent *const hent
910                             = SLIST_FIRST(oldList);
911
912                         SLIST_REMOVE_HEAD(oldList, next);
913                         newBucket = HASH(hent->host.addr, newMask);
914                         SLIST_INSERT_HEAD(&newTab[newBucket], hent, next);
915                 }
916         }
917
918         /* Replace old table with new one */
919         if (priv->conf.debugLevel >= 3) {
920                 log(LOG_INFO, "ng_bridge: %s: table size %d -> %d\n",
921                     ng_bridge_nodename(priv->node),
922                     priv->numBuckets, newNumBuckets);
923         }
924         kfree(priv->tab, M_NETGRAPH_BRIDGE);
925         priv->numBuckets = newNumBuckets;
926         priv->hashMask = newMask;
927         priv->tab = newTab;
928         return;
929 }
930
931 /******************************************************************
932                     MISC FUNCTIONS
933 ******************************************************************/
934
935 /*
936  * Remove all hosts associated with a specific link from the hashtable.
937  * If linkNum == -1, then remove all hosts in the table.
938  */
939 static void
940 ng_bridge_remove_hosts(priv_p priv, int linkNum)
941 {
942         int bucket;
943
944         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
945                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
946
947                 while (*hptr != NULL) {
948                         struct ng_bridge_hent *const hent = *hptr;
949
950                         if (linkNum == -1 || hent->host.linkNum == linkNum) {
951                                 *hptr = SLIST_NEXT(hent, next);
952                                 kfree(hent, M_NETGRAPH_BRIDGE);
953                                 priv->numHosts--;
954                         } else
955                                 hptr = &SLIST_NEXT(hent, next);
956                 }
957         }
958 }
959
960 /*
961  * Handle our once-per-second timeout event. We do two things:
962  * we decrement link->loopCount for those links being muted due to
963  * a detected loopback condition, and we remove any hosts from
964  * the hashtable whom we haven't heard from in a long while.
965  */
966 static void
967 ng_bridge_timeout(node_p node, hook_p hook, void *arg1, int arg2)
968 {
969         const priv_p priv = NG_NODE_PRIVATE(node);
970         int bucket;
971         int counter = 0;
972         int linkNum;
973         char ethstr[ETHER_ADDRSTRLEN + 1] __debugvar;
974
975         /* Update host time counters and remove stale entries */
976         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
977                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
978
979                 while (*hptr != NULL) {
980                         struct ng_bridge_hent *const hent = *hptr;
981
982                         /* Make sure host's link really exists */
983                         KASSERT(priv->links[hent->host.linkNum] != NULL,
984                             ("%s: host %s on nonexistent link %d",
985                             __func__, kether_ntoa(hent->host.addr, ethstr),
986                             hent->host.linkNum));
987
988                         /* Remove hosts we haven't heard from in a while */
989                         if (++hent->host.staleness >= priv->conf.maxStaleness) {
990                                 *hptr = SLIST_NEXT(hent, next);
991                                 kfree(hent, M_NETGRAPH_BRIDGE);
992                                 priv->numHosts--;
993                         } else {
994                                 if (hent->host.age < 0xffff)
995                                         hent->host.age++;
996                                 hptr = &SLIST_NEXT(hent, next);
997                                 counter++;
998                         }
999                 }
1000         }
1001         KASSERT(priv->numHosts == counter,
1002             ("%s: hosts: %d != %d", __func__, priv->numHosts, counter));
1003
1004         /* Decrease table size if necessary */
1005         ng_bridge_rehash(priv);
1006
1007         /* Decrease loop counter on muted looped back links */
1008         for (counter = linkNum = 0; linkNum < NG_BRIDGE_MAX_LINKS; linkNum++) {
1009                 struct ng_bridge_link *const link = priv->links[linkNum];
1010
1011                 if (link != NULL) {
1012                         if (link->loopCount != 0) {
1013                                 link->loopCount--;
1014                                 if (link->loopCount == 0
1015                                     && priv->conf.debugLevel >= 2) {
1016                                         log(LOG_INFO, "ng_bridge: %s:"
1017                                             " restoring looped back link%d\n",
1018                                             ng_bridge_nodename(node), linkNum);
1019                                 }
1020                         }
1021                         counter++;
1022                 }
1023         }
1024         KASSERT(priv->numLinks == counter,
1025             ("%s: links: %d != %d", __func__, priv->numLinks, counter));
1026
1027         /* Register a new timeout, keeping the existing node reference */
1028         ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
1029 }
1030
1031 /*
1032  * Return node's "name", even if it doesn't have one.
1033  */
1034 static const char *
1035 ng_bridge_nodename(node_p node)
1036 {
1037         static char name[NG_NODESIZ];
1038
1039         if (NG_NODE_NAME(node) != NULL)
1040                 snprintf(name, sizeof(name), "%s", NG_NODE_NAME(node));
1041         else
1042                 snprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1043         return name;
1044 }
1045