kernel/netgraph7: Replace usage of MALLOC/FREE with kmalloc/kfree here too.
[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         priv = kmalloc(sizeof(*priv), M_NETGRAPH_BRIDGE,
302                        M_WAITOK | M_NULLOK | M_ZERO);
303         if (priv == NULL)
304                 return (ENOMEM);
305         ng_callout_init(&priv->timer);
306
307         /* Allocate and initialize hash table, etc. */
308         priv->tab = kmalloc(MIN_BUCKETS * sizeof(*priv->tab),
309                             M_NETGRAPH_BRIDGE, M_WAITOK | M_NULLOK | M_ZERO);
310         if (priv->tab == NULL) {
311                 kfree(priv, M_NETGRAPH_BRIDGE);
312                 return (ENOMEM);
313         }
314         priv->numBuckets = MIN_BUCKETS;
315         priv->hashMask = MIN_BUCKETS - 1;
316         priv->conf.debugLevel = 1;
317         priv->conf.loopTimeout = DEFAULT_LOOP_TIMEOUT;
318         priv->conf.maxStaleness = DEFAULT_MAX_STALENESS;
319         priv->conf.minStableAge = DEFAULT_MIN_STABLE_AGE;
320
321         /*
322          * This node has all kinds of stuff that could be screwed by SMP.
323          * Until it gets it's own internal protection, we go through in 
324          * single file. This could hurt a machine bridging beteen two 
325          * GB ethernets so it should be fixed. 
326          * When it's fixed the process SHOULD NOT SLEEP, spinlocks please!
327          * (and atomic ops )
328          */
329         NG_NODE_FORCE_WRITER(node);
330         NG_NODE_SET_PRIVATE(node, priv);
331         priv->node = node;
332
333         /* Start timer; timer is always running while node is alive */
334         ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
335
336         /* Done */
337         return (0);
338 }
339
340 /*
341  * Method for attaching a new hook
342  */
343 static  int
344 ng_bridge_newhook(node_p node, hook_p hook, const char *name)
345 {
346         const priv_p priv = NG_NODE_PRIVATE(node);
347
348         /* Check for a link hook */
349         if (strncmp(name, NG_BRIDGE_HOOK_LINK_PREFIX,
350             strlen(NG_BRIDGE_HOOK_LINK_PREFIX)) == 0) {
351                 const char *cp;
352                 char *eptr;
353                 u_long linkNum;
354
355                 cp = name + strlen(NG_BRIDGE_HOOK_LINK_PREFIX);
356                 if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0'))
357                         return (EINVAL);
358                 linkNum = strtoul(cp, &eptr, 10);
359                 if (*eptr != '\0' || linkNum >= NG_BRIDGE_MAX_LINKS)
360                         return (EINVAL);
361                 if (priv->links[linkNum] != NULL)
362                         return (EISCONN);
363                 priv->links[linkNum] = kmalloc(sizeof(*priv->links[linkNum]),
364                                                M_NETGRAPH_BRIDGE,
365                                                M_WAITOK | M_NULLOK | M_ZERO);
366                 if (priv->links[linkNum] == NULL)
367                         return (ENOMEM);
368                 priv->links[linkNum]->hook = hook;
369                 NG_HOOK_SET_PRIVATE(hook, (void *)linkNum);
370                 priv->numLinks++;
371                 return (0);
372         }
373
374         /* Unknown hook name */
375         return (EINVAL);
376 }
377
378 /*
379  * Receive a control message
380  */
381 static int
382 ng_bridge_rcvmsg(node_p node, item_p item, hook_p lasthook)
383 {
384         const priv_p priv = NG_NODE_PRIVATE(node);
385         struct ng_mesg *resp = NULL;
386         int error = 0;
387         struct ng_mesg *msg;
388
389         NGI_GET_MSG(item, msg);
390         switch (msg->header.typecookie) {
391         case NGM_BRIDGE_COOKIE:
392                 switch (msg->header.cmd) {
393                 case NGM_BRIDGE_GET_CONFIG:
394                     {
395                         struct ng_bridge_config *conf;
396
397                         NG_MKRESPONSE(resp, msg,
398                             sizeof(struct ng_bridge_config), M_WAITOK | M_NULLOK);
399                         if (resp == NULL) {
400                                 error = ENOMEM;
401                                 break;
402                         }
403                         conf = (struct ng_bridge_config *)resp->data;
404                         *conf = priv->conf;     /* no sanity checking needed */
405                         break;
406                     }
407                 case NGM_BRIDGE_SET_CONFIG:
408                     {
409                         struct ng_bridge_config *conf;
410                         int i;
411
412                         if (msg->header.arglen
413                             != sizeof(struct ng_bridge_config)) {
414                                 error = EINVAL;
415                                 break;
416                         }
417                         conf = (struct ng_bridge_config *)msg->data;
418                         priv->conf = *conf;
419                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++)
420                                 priv->conf.ipfw[i] = !!priv->conf.ipfw[i];
421                         break;
422                     }
423                 case NGM_BRIDGE_RESET:
424                     {
425                         int i;
426
427                         /* Flush all entries in the hash table */
428                         ng_bridge_remove_hosts(priv, -1);
429
430                         /* Reset all loop detection counters and stats */
431                         for (i = 0; i < NG_BRIDGE_MAX_LINKS; i++) {
432                                 if (priv->links[i] == NULL)
433                                         continue;
434                                 priv->links[i]->loopCount = 0;
435                                 bzero(&priv->links[i]->stats,
436                                     sizeof(priv->links[i]->stats));
437                         }
438                         break;
439                     }
440                 case NGM_BRIDGE_GET_STATS:
441                 case NGM_BRIDGE_CLR_STATS:
442                 case NGM_BRIDGE_GETCLR_STATS:
443                     {
444                         struct ng_bridge_link *link;
445                         int linkNum;
446
447                         /* Get link number */
448                         if (msg->header.arglen != sizeof(u_int32_t)) {
449                                 error = EINVAL;
450                                 break;
451                         }
452                         linkNum = *((u_int32_t *)msg->data);
453                         if (linkNum < 0 || linkNum >= NG_BRIDGE_MAX_LINKS) {
454                                 error = EINVAL;
455                                 break;
456                         }
457                         if ((link = priv->links[linkNum]) == NULL) {
458                                 error = ENOTCONN;
459                                 break;
460                         }
461
462                         /* Get/clear stats */
463                         if (msg->header.cmd != NGM_BRIDGE_CLR_STATS) {
464                                 NG_MKRESPONSE(resp, msg,
465                                     sizeof(link->stats), M_WAITOK | M_NULLOK);
466                                 if (resp == NULL) {
467                                         error = ENOMEM;
468                                         break;
469                                 }
470                                 bcopy(&link->stats,
471                                     resp->data, sizeof(link->stats));
472                         }
473                         if (msg->header.cmd != NGM_BRIDGE_GET_STATS)
474                                 bzero(&link->stats, sizeof(link->stats));
475                         break;
476                     }
477                 case NGM_BRIDGE_GET_TABLE:
478                     {
479                         struct ng_bridge_host_ary *ary;
480                         struct ng_bridge_hent *hent;
481                         int i = 0, bucket;
482
483                         NG_MKRESPONSE(resp, msg, sizeof(*ary)
484                             + (priv->numHosts * sizeof(*ary->hosts)), M_WAITOK | M_NULLOK);
485                         if (resp == NULL) {
486                                 error = ENOMEM;
487                                 break;
488                         }
489                         ary = (struct ng_bridge_host_ary *)resp->data;
490                         ary->numHosts = priv->numHosts;
491                         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
492                                 SLIST_FOREACH(hent, &priv->tab[bucket], next)
493                                         ary->hosts[i++] = hent->host;
494                         }
495                         break;
496                     }
497                 default:
498                         error = EINVAL;
499                         break;
500                 }
501                 break;
502         default:
503                 error = EINVAL;
504                 break;
505         }
506
507         /* Done */
508         NG_RESPOND_MSG(error, node, item, resp);
509         NG_FREE_MSG(msg);
510         return (error);
511 }
512
513 /*
514  * Receive data on a hook
515  */
516 static int
517 ng_bridge_rcvdata(hook_p hook, item_p item)
518 {
519         const node_p node = NG_HOOK_NODE(hook);
520         const priv_p priv = NG_NODE_PRIVATE(node);
521         struct ng_bridge_host *host;
522         struct ng_bridge_link *link;
523         struct ether_header *eh;
524         int error = 0, linkNum, linksSeen;
525         int manycast;
526         struct mbuf *m;
527         struct ng_bridge_link *firstLink;
528
529         NGI_GET_M(item, m);
530         /* Get link number */
531         linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
532         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
533             ("%s: linkNum=%u", __func__, linkNum));
534         link = priv->links[linkNum];
535         KASSERT(link != NULL, ("%s: link%d null", __func__, linkNum));
536
537         /* Sanity check packet and pull up header */
538         if (m->m_pkthdr.len < ETHER_HDR_LEN) {
539                 link->stats.recvRunts++;
540                 NG_FREE_ITEM(item);
541                 NG_FREE_M(m);
542                 return (EINVAL);
543         }
544         if (m->m_len < ETHER_HDR_LEN && !(m = m_pullup(m, ETHER_HDR_LEN))) {
545                 link->stats.memoryFailures++;
546                 NG_FREE_ITEM(item);
547                 return (ENOBUFS);
548         }
549         eh = mtod(m, struct ether_header *);
550         if ((eh->ether_shost[0] & 1) != 0) {
551                 link->stats.recvInvalid++;
552                 NG_FREE_ITEM(item);
553                 NG_FREE_M(m);
554                 return (EINVAL);
555         }
556
557         /* Is link disabled due to a loopback condition? */
558         if (link->loopCount != 0) {
559                 link->stats.loopDrops++;
560                 NG_FREE_ITEM(item);
561                 NG_FREE_M(m);
562                 return (ELOOP);         /* XXX is this an appropriate error? */
563         }
564
565         /* Update stats */
566         link->stats.recvPackets++;
567         link->stats.recvOctets += m->m_pkthdr.len;
568         if ((manycast = (eh->ether_dhost[0] & 1)) != 0) {
569                 if (ETHER_EQUAL(eh->ether_dhost, ng_bridge_bcast_addr)) {
570                         link->stats.recvBroadcasts++;
571                         manycast = 2;
572                 } else
573                         link->stats.recvMulticasts++;
574         }
575
576         /* Look up packet's source Ethernet address in hashtable */
577         if ((host = ng_bridge_get(priv, eh->ether_shost)) != NULL) {
578
579                 /* Update time since last heard from this host */
580                 host->staleness = 0;
581
582                 /* Did host jump to a different link? */
583                 if (host->linkNum != linkNum) {
584
585                         /*
586                          * If the host's old link was recently established
587                          * on the old link and it's already jumped to a new
588                          * link, declare a loopback condition.
589                          */
590                         if (host->age < priv->conf.minStableAge) {
591
592                                 /* Log the problem */
593                                 if (priv->conf.debugLevel >= 2) {
594                                         struct ifnet *ifp = m->m_pkthdr.rcvif;
595                                         char suffix[32];
596
597                                         if (ifp != NULL)
598                                                 snprintf(suffix, sizeof(suffix),
599                                                     " (%s)", ifp->if_xname);
600                                         else
601                                                 *suffix = '\0';
602                                         log(LOG_WARNING, "ng_bridge: %s:"
603                                             " loopback detected on %s%s\n",
604                                             ng_bridge_nodename(node),
605                                             NG_HOOK_NAME(hook), suffix);
606                                 }
607
608                                 /* Mark link as linka non grata */
609                                 link->loopCount = priv->conf.loopTimeout;
610                                 link->stats.loopDetects++;
611
612                                 /* Forget all hosts on this link */
613                                 ng_bridge_remove_hosts(priv, linkNum);
614
615                                 /* Drop packet */
616                                 link->stats.loopDrops++;
617                                 NG_FREE_ITEM(item);
618                                 NG_FREE_M(m);
619                                 return (ELOOP);         /* XXX appropriate? */
620                         }
621
622                         /* Move host over to new link */
623                         host->linkNum = linkNum;
624                         host->age = 0;
625                 }
626         } else {
627                 if (!ng_bridge_put(priv, eh->ether_shost, linkNum)) {
628                         link->stats.memoryFailures++;
629                         NG_FREE_ITEM(item);
630                         NG_FREE_M(m);
631                         return (ENOMEM);
632                 }
633         }
634
635         /* Run packet through ipfw processing, if enabled */
636 #if 0
637         if (priv->conf.ipfw[linkNum] && fw_enable && ip_fw_chk_ptr != NULL) {
638                 /* XXX not implemented yet */
639         }
640 #endif
641
642         /*
643          * If unicast and destination host known, deliver to host's link,
644          * unless it is the same link as the packet came in on.
645          */
646         if (!manycast) {
647
648                 /* Determine packet destination link */
649                 if ((host = ng_bridge_get(priv, eh->ether_dhost)) != NULL) {
650                         struct ng_bridge_link *const destLink
651                             = priv->links[host->linkNum];
652
653                         /* If destination same as incoming link, do nothing */
654                         KASSERT(destLink != NULL,
655                             ("%s: link%d null", __func__, host->linkNum));
656                         if (destLink == link) {
657                                 NG_FREE_ITEM(item);
658                                 NG_FREE_M(m);
659                                 return (0);
660                         }
661
662                         /* Deliver packet out the destination link */
663                         destLink->stats.xmitPackets++;
664                         destLink->stats.xmitOctets += m->m_pkthdr.len;
665                         NG_FWD_NEW_DATA(error, item, destLink->hook, m);
666                         return (error);
667                 }
668
669                 /* Destination host is not known */
670                 link->stats.recvUnknown++;
671         }
672
673         /* Distribute unknown, multicast, broadcast pkts to all other links */
674         firstLink = NULL;
675         for (linkNum = linksSeen = 0; linksSeen <= priv->numLinks; linkNum++) {
676                 struct ng_bridge_link *destLink;
677                 struct mbuf *m2 = NULL;
678
679                 /*
680                  * If we have checked all the links then now
681                  * send the original on its reserved link
682                  */
683                 if (linksSeen == priv->numLinks) {
684                         /* If we never saw a good link, leave. */
685                         if (firstLink == NULL) {
686                                 NG_FREE_ITEM(item);
687                                 NG_FREE_M(m);
688                                 return (0);
689                         }       
690                         destLink = firstLink;
691                 } else {
692                         destLink = priv->links[linkNum];
693                         if (destLink != NULL)
694                                 linksSeen++;
695                         /* Skip incoming link and disconnected links */
696                         if (destLink == NULL || destLink == link) {
697                                 continue;
698                         }
699                         if (firstLink == NULL) {
700                                 /*
701                                  * This is the first usable link we have found.
702                                  * Reserve it for the originals.
703                                  * If we never find another we save a copy.
704                                  */
705                                 firstLink = destLink;
706                                 continue;
707                         }
708
709                         /*
710                          * It's usable link but not the reserved (first) one.
711                          * Copy mbuf info for sending.
712                          */
713                         m2 = m_dup(m, MB_DONTWAIT);     /* XXX m_copypacket() */
714                         if (m2 == NULL) {
715                                 link->stats.memoryFailures++;
716                                 NG_FREE_ITEM(item);
717                                 NG_FREE_M(m);
718                                 return (ENOBUFS);
719                         }
720                 }
721
722                 /* Update stats */
723                 destLink->stats.xmitPackets++;
724                 destLink->stats.xmitOctets += m->m_pkthdr.len;
725                 switch (manycast) {
726                 case 0:                                 /* unicast */
727                         break;
728                 case 1:                                 /* multicast */
729                         destLink->stats.xmitMulticasts++;
730                         break;
731                 case 2:                                 /* broadcast */
732                         destLink->stats.xmitBroadcasts++;
733                         break;
734                 }
735
736                 /* Send packet */
737                 if (destLink == firstLink) { 
738                         /*
739                          * If we've sent all the others, send the original
740                          * on the first link we found.
741                          */
742                         NG_FWD_NEW_DATA(error, item, destLink->hook, m);
743                         break; /* always done last - not really needed. */
744                 } else {
745                         NG_SEND_DATA_ONLY(error, destLink->hook, m2);
746                 }
747         }
748         return (error);
749 }
750
751 /*
752  * Shutdown node
753  */
754 static int
755 ng_bridge_shutdown(node_p node)
756 {
757         const priv_p priv = NG_NODE_PRIVATE(node);
758
759         /*
760          * Shut down everything including the timer.  Even if the
761          * callout has already been dequeued and is about to be
762          * run, ng_bridge_timeout() won't be fired as the node
763          * is already marked NGF_INVALID, so we're safe to free
764          * the node now.
765          */
766         KASSERT(priv->numLinks == 0 && priv->numHosts == 0,
767             ("%s: numLinks=%d numHosts=%d",
768             __func__, priv->numLinks, priv->numHosts));
769         ng_uncallout(&priv->timer, node);
770         NG_NODE_SET_PRIVATE(node, NULL);
771         NG_NODE_UNREF(node);
772         kfree(priv->tab, M_NETGRAPH_BRIDGE);
773         kfree(priv, M_NETGRAPH_BRIDGE);
774         return (0);
775 }
776
777 /*
778  * Hook disconnection.
779  */
780 static int
781 ng_bridge_disconnect(hook_p hook)
782 {
783         const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hook));
784         int linkNum;
785
786         /* Get link number */
787         linkNum = (intptr_t)NG_HOOK_PRIVATE(hook);
788         KASSERT(linkNum >= 0 && linkNum < NG_BRIDGE_MAX_LINKS,
789             ("%s: linkNum=%u", __func__, linkNum));
790
791         /* Remove all hosts associated with this link */
792         ng_bridge_remove_hosts(priv, linkNum);
793
794         /* Free associated link information */
795         KASSERT(priv->links[linkNum] != NULL, ("%s: no link", __func__));
796         kfree(priv->links[linkNum], M_NETGRAPH_BRIDGE);
797         priv->links[linkNum] = NULL;
798         priv->numLinks--;
799
800         /* If no more hooks, go away */
801         if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
802         && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))) {
803                 ng_rmnode_self(NG_HOOK_NODE(hook));
804         }
805         return (0);
806 }
807
808 /******************************************************************
809                     HASH TABLE FUNCTIONS
810 ******************************************************************/
811
812 /*
813  * Hash algorithm
814  */
815 #define HASH(addr,mask)         ( (((const u_int16_t *)(addr))[0]       \
816                                  ^ ((const u_int16_t *)(addr))[1]       \
817                                  ^ ((const u_int16_t *)(addr))[2]) & (mask) )
818
819 /*
820  * Find a host entry in the table.
821  */
822 static struct ng_bridge_host *
823 ng_bridge_get(priv_p priv, const u_char *addr)
824 {
825         const int bucket = HASH(addr, priv->hashMask);
826         struct ng_bridge_hent *hent;
827
828         SLIST_FOREACH(hent, &priv->tab[bucket], next) {
829                 if (ETHER_EQUAL(hent->host.addr, addr))
830                         return (&hent->host);
831         }
832         return (NULL);
833 }
834
835 /*
836  * Add a new host entry to the table. This assumes the host doesn't
837  * already exist in the table. Returns 1 on success, 0 if there
838  * was a memory allocation failure.
839  */
840 static int
841 ng_bridge_put(priv_p priv, const u_char *addr, int linkNum)
842 {
843         const int bucket = HASH(addr, priv->hashMask);
844         struct ng_bridge_hent *hent;
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 %6D exists in table", __func__, addr, ":"));
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
974         /* Update host time counters and remove stale entries */
975         for (bucket = 0; bucket < priv->numBuckets; bucket++) {
976                 struct ng_bridge_hent **hptr = &SLIST_FIRST(&priv->tab[bucket]);
977
978                 while (*hptr != NULL) {
979                         struct ng_bridge_hent *const hent = *hptr;
980
981                         /* Make sure host's link really exists */
982                         KASSERT(priv->links[hent->host.linkNum] != NULL,
983                             ("%s: host %6D on nonexistent link %d\n",
984                             __func__, hent->host.addr, ":",
985                             hent->host.linkNum));
986
987                         /* Remove hosts we haven't heard from in a while */
988                         if (++hent->host.staleness >= priv->conf.maxStaleness) {
989                                 *hptr = SLIST_NEXT(hent, next);
990                                 kfree(hent, M_NETGRAPH_BRIDGE);
991                                 priv->numHosts--;
992                         } else {
993                                 if (hent->host.age < 0xffff)
994                                         hent->host.age++;
995                                 hptr = &SLIST_NEXT(hent, next);
996                                 counter++;
997                         }
998                 }
999         }
1000         KASSERT(priv->numHosts == counter,
1001             ("%s: hosts: %d != %d", __func__, priv->numHosts, counter));
1002
1003         /* Decrease table size if necessary */
1004         ng_bridge_rehash(priv);
1005
1006         /* Decrease loop counter on muted looped back links */
1007         for (counter = linkNum = 0; linkNum < NG_BRIDGE_MAX_LINKS; linkNum++) {
1008                 struct ng_bridge_link *const link = priv->links[linkNum];
1009
1010                 if (link != NULL) {
1011                         if (link->loopCount != 0) {
1012                                 link->loopCount--;
1013                                 if (link->loopCount == 0
1014                                     && priv->conf.debugLevel >= 2) {
1015                                         log(LOG_INFO, "ng_bridge: %s:"
1016                                             " restoring looped back link%d\n",
1017                                             ng_bridge_nodename(node), linkNum);
1018                                 }
1019                         }
1020                         counter++;
1021                 }
1022         }
1023         KASSERT(priv->numLinks == counter,
1024             ("%s: links: %d != %d", __func__, priv->numLinks, counter));
1025
1026         /* Register a new timeout, keeping the existing node reference */
1027         ng_callout(&priv->timer, node, NULL, hz, ng_bridge_timeout, NULL, 0);
1028 }
1029
1030 /*
1031  * Return node's "name", even if it doesn't have one.
1032  */
1033 static const char *
1034 ng_bridge_nodename(node_p node)
1035 {
1036         static char name[NG_NODESIZ];
1037
1038         if (NG_NODE_NAME(node) != NULL)
1039                 snprintf(name, sizeof(name), "%s", NG_NODE_NAME(node));
1040         else
1041                 snprintf(name, sizeof(name), "[%x]", ng_node2ID(node));
1042         return name;
1043 }
1044