5 * Copyright (c) 2000 Whistle Communications, Inc.
8 * Subject to the following obligations and disclaimer of warranty, use and
9 * redistribution of this software, in source or object code forms, with or
10 * without modifications are expressly permitted by Whistle Communications;
11 * provided, however, that:
12 * 1. Any and all reproductions of the source or object code must include the
13 * copyright notice above and the following disclaimer of warranties; and
14 * 2. No rights are granted, in any manner or form, to use Whistle
15 * Communications, Inc. trademarks, including the mark "WHISTLE
16 * COMMUNICATIONS" on advertising, endorsements, or otherwise except as
17 * such appears in the above copyright notice or in the software.
19 * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
20 * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
21 * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
22 * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
23 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
24 * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
25 * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
26 * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
27 * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
28 * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
29 * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
30 * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
31 * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
34 * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
37 * Author: Archie Cobbs <archie@freebsd.org>
39 * $FreeBSD: src/sys/netgraph/ng_bridge.c,v 1.1.2.5 2002/07/02 23:44:02 archie Exp $
43 * ng_bridge(4) netgraph node type
45 * The node performs standard intelligent Ethernet bridging over
46 * each of its connected hooks, or links. A simple loop detection
47 * algorithm is included which disables a link for priv->conf.loopTimeout
48 * seconds when a host is seen to have jumped from one link to
49 * another within priv->conf.minStableAge seconds.
51 * We keep a hashtable that maps Ethernet addresses to host info,
52 * which is contained in struct ng_bridge_host's. These structures
53 * tell us on which link the host may be found. A host's entry will
54 * expire after priv->conf.maxStaleness seconds.
56 * This node is optimzed for stable networks, where machines jump
57 * from one port to the other only rarely.
60 #include <sys/param.h>
61 #include <sys/systm.h>
62 #include <sys/kernel.h>
63 #include <sys/malloc.h>
65 #include <sys/errno.h>
66 #include <sys/syslog.h>
67 #include <sys/socket.h>
68 #include <sys/ctype.h>
69 #include <sys/thread2.h>
72 #include <net/ethernet.h>
74 #include <netinet/in.h>
75 #include <net/ipfw/ip_fw.h>
77 #include <netgraph/ng_message.h>
78 #include <netgraph/netgraph.h>
79 #include <netgraph/ng_parse.h>
80 #include "ng_bridge.h"
81 #include <netgraph/ether/ng_ether.h>
83 /* Per-link private data */
84 struct ng_bridge_link
{
85 hook_p hook
; /* netgraph hook */
86 u_int16_t loopCount
; /* loop ignore timer */
87 struct ng_bridge_link_stats stats
; /* link stats */
90 /* Per-node private data */
91 struct ng_bridge_private
{
92 struct ng_bridge_bucket
*tab
; /* hash table bucket array */
93 struct ng_bridge_link
*links
[NG_BRIDGE_MAX_LINKS
];
94 struct ng_bridge_config conf
; /* node configuration */
95 node_p node
; /* netgraph node */
96 u_int numHosts
; /* num entries in table */
97 u_int numBuckets
; /* num buckets in table */
98 u_int hashMask
; /* numBuckets - 1 */
99 int numLinks
; /* num connected links */
100 struct callout timer
; /* one second periodic timer */
102 typedef struct ng_bridge_private
*priv_p
;
104 /* Information about a host, stored in a hash table entry */
105 struct ng_bridge_hent
{
106 struct ng_bridge_host host
; /* actual host info */
107 SLIST_ENTRY(ng_bridge_hent
) next
; /* next entry in bucket */
110 /* Hash table bucket declaration */
111 SLIST_HEAD(ng_bridge_bucket
, ng_bridge_hent
);
113 /* Netgraph node methods */
114 static ng_constructor_t ng_bridge_constructor
;
115 static ng_rcvmsg_t ng_bridge_rcvmsg
;
116 static ng_shutdown_t ng_bridge_rmnode
;
117 static ng_newhook_t ng_bridge_newhook
;
118 static ng_rcvdata_t ng_bridge_rcvdata
;
119 static ng_disconnect_t ng_bridge_disconnect
;
121 /* Other internal functions */
122 static struct ng_bridge_host
*ng_bridge_get(priv_p priv
, const u_char
*addr
);
123 static int ng_bridge_put(priv_p priv
, const u_char
*addr
, int linkNum
);
124 static void ng_bridge_rehash(priv_p priv
);
125 static void ng_bridge_remove_hosts(priv_p priv
, int linkNum
);
126 static void ng_bridge_timeout(void *arg
);
127 static const char *ng_bridge_nodename(node_p node
);
129 /* Ethernet broadcast */
130 static const u_char ng_bridge_bcast_addr
[ETHER_ADDR_LEN
] =
131 { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
133 /* Store each hook's link number in the private field */
134 #define LINK_NUM(hook) (*(u_int16_t *)(&(hook)->private))
136 /* Compare Ethernet addresses using 32 and 16 bit words instead of bytewise */
137 #define ETHER_EQUAL(a,b) (((const u_int32_t *)(a))[0] \
138 == ((const u_int32_t *)(b))[0] \
139 && ((const u_int16_t *)(a))[2] \
140 == ((const u_int16_t *)(b))[2])
142 /* Minimum and maximum number of hash buckets. Must be a power of two. */
143 #define MIN_BUCKETS (1 << 5) /* 32 */
144 #define MAX_BUCKETS (1 << 14) /* 16384 */
146 /* Configuration default values */
147 #define DEFAULT_LOOP_TIMEOUT 60
148 #define DEFAULT_MAX_STALENESS (15 * 60) /* same as ARP timeout */
149 #define DEFAULT_MIN_STABLE_AGE 1
151 /******************************************************************
153 ******************************************************************/
156 * How to determine the length of the table returned by NGM_BRIDGE_GET_TABLE
159 ng_bridge_getTableLength(const struct ng_parse_type
*type
,
160 const u_char
*start
, const u_char
*buf
)
162 const struct ng_bridge_host_ary
*const hary
163 = (const struct ng_bridge_host_ary
*)(buf
- sizeof(u_int32_t
));
165 return hary
->numHosts
;
168 /* Parse type for struct ng_bridge_host_ary */
169 static const struct ng_parse_struct_field ng_bridge_host_type_fields
[]
170 = NG_BRIDGE_HOST_TYPE_INFO(&ng_ether_enaddr_type
);
171 static const struct ng_parse_type ng_bridge_host_type
= {
172 &ng_parse_struct_type
,
173 &ng_bridge_host_type_fields
175 static const struct ng_parse_array_info ng_bridge_hary_type_info
= {
176 &ng_bridge_host_type
,
177 ng_bridge_getTableLength
179 static const struct ng_parse_type ng_bridge_hary_type
= {
180 &ng_parse_array_type
,
181 &ng_bridge_hary_type_info
183 static const struct ng_parse_struct_field ng_bridge_host_ary_type_fields
[]
184 = NG_BRIDGE_HOST_ARY_TYPE_INFO(&ng_bridge_hary_type
);
185 static const struct ng_parse_type ng_bridge_host_ary_type
= {
186 &ng_parse_struct_type
,
187 &ng_bridge_host_ary_type_fields
190 /* Parse type for struct ng_bridge_config */
191 static const struct ng_parse_fixedarray_info ng_bridge_ipfwary_type_info
= {
192 &ng_parse_uint8_type
,
195 static const struct ng_parse_type ng_bridge_ipfwary_type
= {
196 &ng_parse_fixedarray_type
,
197 &ng_bridge_ipfwary_type_info
199 static const struct ng_parse_struct_field ng_bridge_config_type_fields
[]
200 = NG_BRIDGE_CONFIG_TYPE_INFO(&ng_bridge_ipfwary_type
);
201 static const struct ng_parse_type ng_bridge_config_type
= {
202 &ng_parse_struct_type
,
203 &ng_bridge_config_type_fields
206 /* Parse type for struct ng_bridge_link_stat */
207 static const struct ng_parse_struct_field ng_bridge_stats_type_fields
[]
208 = NG_BRIDGE_STATS_TYPE_INFO
;
209 static const struct ng_parse_type ng_bridge_stats_type
= {
210 &ng_parse_struct_type
,
211 &ng_bridge_stats_type_fields
214 /* List of commands and how to convert arguments to/from ASCII */
215 static const struct ng_cmdlist ng_bridge_cmdlist
[] = {
218 NGM_BRIDGE_SET_CONFIG
,
220 &ng_bridge_config_type
,
225 NGM_BRIDGE_GET_CONFIG
,
228 &ng_bridge_config_type
239 NGM_BRIDGE_GET_STATS
,
241 &ng_parse_uint32_type
,
242 &ng_bridge_stats_type
246 NGM_BRIDGE_CLR_STATS
,
248 &ng_parse_uint32_type
,
253 NGM_BRIDGE_GETCLR_STATS
,
255 &ng_parse_uint32_type
,
256 &ng_bridge_stats_type
260 NGM_BRIDGE_GET_TABLE
,
263 &ng_bridge_host_ary_type
268 /* Node type descriptor */
269 static struct ng_type ng_bridge_typestruct
= {
273 ng_bridge_constructor
,
281 ng_bridge_disconnect
,
284 NETGRAPH_INIT(bridge
, &ng_bridge_typestruct
);
286 /* Depend on ng_ether so we can use the Ethernet parse type */
287 MODULE_DEPEND(ng_bridge
, ng_ether
, NG_ABI_VERSION
, NG_ABI_VERSION
, NG_ABI_VERSION
);
289 /******************************************************************
290 NETGRAPH NODE METHODS
291 ******************************************************************/
297 ng_bridge_constructor(node_p
*nodep
)
302 /* Allocate and initialize private info */
303 priv
= kmalloc(sizeof(*priv
), M_NETGRAPH
, M_NOWAIT
| M_ZERO
);
306 callout_init(&priv
->timer
);
308 /* Allocate and initialize hash table, etc. */
309 priv
->tab
= kmalloc(MIN_BUCKETS
* sizeof(*priv
->tab
), M_NETGRAPH
,
311 if (priv
->tab
== NULL
) {
312 kfree(priv
, M_NETGRAPH
);
315 priv
->numBuckets
= MIN_BUCKETS
;
316 priv
->hashMask
= MIN_BUCKETS
- 1;
317 priv
->conf
.debugLevel
= 1;
318 priv
->conf
.loopTimeout
= DEFAULT_LOOP_TIMEOUT
;
319 priv
->conf
.maxStaleness
= DEFAULT_MAX_STALENESS
;
320 priv
->conf
.minStableAge
= DEFAULT_MIN_STABLE_AGE
;
322 /* Call superclass constructor */
323 if ((error
= ng_make_node_common(&ng_bridge_typestruct
, nodep
))) {
324 kfree(priv
, M_NETGRAPH
);
327 (*nodep
)->private = priv
;
330 /* Start timer; timer is always running while node is alive */
331 callout_reset(&priv
->timer
, hz
, ng_bridge_timeout
, priv
->node
);
338 * Method for attaching a new hook
341 ng_bridge_newhook(node_p node
, hook_p hook
, const char *name
)
343 const priv_p priv
= node
->private;
345 /* Check for a link hook */
346 if (strncmp(name
, NG_BRIDGE_HOOK_LINK_PREFIX
,
347 strlen(NG_BRIDGE_HOOK_LINK_PREFIX
)) == 0) {
352 cp
= name
+ strlen(NG_BRIDGE_HOOK_LINK_PREFIX
);
353 if (!isdigit(*cp
) || (cp
[0] == '0' && cp
[1] != '\0'))
355 linkNum
= strtoul(cp
, &eptr
, 10);
356 if (*eptr
!= '\0' || linkNum
>= NG_BRIDGE_MAX_LINKS
)
358 if (priv
->links
[linkNum
] != NULL
)
360 priv
->links
[linkNum
] = kmalloc(sizeof(*priv
->links
[linkNum
]),
361 M_NETGRAPH
, M_NOWAIT
);
362 if (priv
->links
[linkNum
] == NULL
)
364 bzero(priv
->links
[linkNum
], sizeof(*priv
->links
[linkNum
]));
365 priv
->links
[linkNum
]->hook
= hook
;
366 LINK_NUM(hook
) = linkNum
;
371 /* Unknown hook name */
376 * Receive a control message
379 ng_bridge_rcvmsg(node_p node
, struct ng_mesg
*msg
,
380 const char *retaddr
, struct ng_mesg
**rptr
)
382 const priv_p priv
= node
->private;
383 struct ng_mesg
*resp
= NULL
;
386 switch (msg
->header
.typecookie
) {
387 case NGM_BRIDGE_COOKIE
:
388 switch (msg
->header
.cmd
) {
389 case NGM_BRIDGE_GET_CONFIG
:
391 struct ng_bridge_config
*conf
;
393 NG_MKRESPONSE(resp
, msg
,
394 sizeof(struct ng_bridge_config
), M_NOWAIT
);
399 conf
= (struct ng_bridge_config
*)resp
->data
;
400 *conf
= priv
->conf
; /* no sanity checking needed */
403 case NGM_BRIDGE_SET_CONFIG
:
405 struct ng_bridge_config
*conf
;
408 if (msg
->header
.arglen
409 != sizeof(struct ng_bridge_config
)) {
413 conf
= (struct ng_bridge_config
*)msg
->data
;
415 for (i
= 0; i
< NG_BRIDGE_MAX_LINKS
; i
++)
416 priv
->conf
.ipfw
[i
] = !!priv
->conf
.ipfw
[i
];
419 case NGM_BRIDGE_RESET
:
423 /* Flush all entries in the hash table */
424 ng_bridge_remove_hosts(priv
, -1);
426 /* Reset all loop detection counters and stats */
427 for (i
= 0; i
< NG_BRIDGE_MAX_LINKS
; i
++) {
428 if (priv
->links
[i
] == NULL
)
430 priv
->links
[i
]->loopCount
= 0;
431 bzero(&priv
->links
[i
]->stats
,
432 sizeof(priv
->links
[i
]->stats
));
436 case NGM_BRIDGE_GET_STATS
:
437 case NGM_BRIDGE_CLR_STATS
:
438 case NGM_BRIDGE_GETCLR_STATS
:
440 struct ng_bridge_link
*link
;
443 /* Get link number */
444 if (msg
->header
.arglen
!= sizeof(u_int32_t
)) {
448 linkNum
= *((u_int32_t
*)msg
->data
);
449 if (linkNum
< 0 || linkNum
>= NG_BRIDGE_MAX_LINKS
) {
453 if ((link
= priv
->links
[linkNum
]) == NULL
) {
458 /* Get/clear stats */
459 if (msg
->header
.cmd
!= NGM_BRIDGE_CLR_STATS
) {
460 NG_MKRESPONSE(resp
, msg
,
461 sizeof(link
->stats
), M_NOWAIT
);
467 resp
->data
, sizeof(link
->stats
));
469 if (msg
->header
.cmd
!= NGM_BRIDGE_GET_STATS
)
470 bzero(&link
->stats
, sizeof(link
->stats
));
473 case NGM_BRIDGE_GET_TABLE
:
475 struct ng_bridge_host_ary
*ary
;
476 struct ng_bridge_hent
*hent
;
479 NG_MKRESPONSE(resp
, msg
, sizeof(*ary
)
480 + (priv
->numHosts
* sizeof(*ary
->hosts
)), M_NOWAIT
);
485 ary
= (struct ng_bridge_host_ary
*)resp
->data
;
486 ary
->numHosts
= priv
->numHosts
;
487 for (bucket
= 0; bucket
< priv
->numBuckets
; bucket
++) {
488 SLIST_FOREACH(hent
, &priv
->tab
[bucket
], next
)
489 ary
->hosts
[i
++] = hent
->host
;
506 else if (resp
!= NULL
)
507 kfree(resp
, M_NETGRAPH
);
508 kfree(msg
, M_NETGRAPH
);
513 * Receive data on a hook
516 ng_bridge_rcvdata(hook_p hook
, struct mbuf
*m
, meta_p meta
)
518 const node_p node
= hook
->node
;
519 const priv_p priv
= node
->private;
520 struct ng_bridge_host
*host
;
521 struct ng_bridge_link
*link
;
522 struct ether_header
*eh
;
523 int error
= 0, linkNum
;
526 /* Get link number */
527 linkNum
= LINK_NUM(hook
);
528 KASSERT(linkNum
>= 0 && linkNum
< NG_BRIDGE_MAX_LINKS
,
529 ("%s: linkNum=%u", __func__
, linkNum
));
530 link
= priv
->links
[linkNum
];
531 KASSERT(link
!= NULL
, ("%s: link%d null", __func__
, linkNum
));
533 /* Sanity check packet and pull up header */
534 if (m
->m_pkthdr
.len
< ETHER_HDR_LEN
) {
535 link
->stats
.recvRunts
++;
536 NG_FREE_DATA(m
, meta
);
539 if (m
->m_len
< ETHER_HDR_LEN
&& !(m
= m_pullup(m
, ETHER_HDR_LEN
))) {
540 link
->stats
.memoryFailures
++;
544 eh
= mtod(m
, struct ether_header
*);
545 if ((eh
->ether_shost
[0] & 1) != 0) {
546 link
->stats
.recvInvalid
++;
547 NG_FREE_DATA(m
, meta
);
551 /* Is link disabled due to a loopback condition? */
552 if (link
->loopCount
!= 0) {
553 link
->stats
.loopDrops
++;
554 NG_FREE_DATA(m
, meta
);
555 return (ELOOP
); /* XXX is this an appropriate error? */
559 link
->stats
.recvPackets
++;
560 link
->stats
.recvOctets
+= m
->m_pkthdr
.len
;
561 if ((manycast
= (eh
->ether_dhost
[0] & 1)) != 0) {
562 if (ETHER_EQUAL(eh
->ether_dhost
, ng_bridge_bcast_addr
)) {
563 link
->stats
.recvBroadcasts
++;
566 link
->stats
.recvMulticasts
++;
569 /* Look up packet's source Ethernet address in hashtable */
570 if ((host
= ng_bridge_get(priv
, eh
->ether_shost
)) != NULL
) {
572 /* Update time since last heard from this host */
575 /* Did host jump to a different link? */
576 if (host
->linkNum
!= linkNum
) {
579 * If the host's old link was recently established
580 * on the old link and it's already jumped to a new
581 * link, declare a loopback condition.
583 if (host
->age
< priv
->conf
.minStableAge
) {
585 /* Log the problem */
586 if (priv
->conf
.debugLevel
>= 2) {
587 struct ifnet
*ifp
= m
->m_pkthdr
.rcvif
;
591 ksnprintf(suffix
, sizeof(suffix
),
592 " (%s)", ifp
->if_xname
);
595 log(LOG_WARNING
, "ng_bridge: %s:"
596 " loopback detected on %s%s\n",
597 ng_bridge_nodename(node
),
601 /* Mark link as linka non grata */
602 link
->loopCount
= priv
->conf
.loopTimeout
;
603 link
->stats
.loopDetects
++;
605 /* Forget all hosts on this link */
606 ng_bridge_remove_hosts(priv
, linkNum
);
609 link
->stats
.loopDrops
++;
610 NG_FREE_DATA(m
, meta
);
611 return (ELOOP
); /* XXX appropriate? */
614 /* Move host over to new link */
615 host
->linkNum
= linkNum
;
619 if (!ng_bridge_put(priv
, eh
->ether_shost
, linkNum
)) {
620 link
->stats
.memoryFailures
++;
621 NG_FREE_DATA(m
, meta
);
626 /* Run packet through ipfw processing, if enabled */
627 if (priv
->conf
.ipfw
[linkNum
] && fw_enable
&& ip_fw_chk_ptr
!= NULL
) {
628 /* XXX not implemented yet */
632 * If unicast and destination host known, deliver to host's link,
633 * unless it is the same link as the packet came in on.
637 /* Determine packet destination link */
638 if ((host
= ng_bridge_get(priv
, eh
->ether_dhost
)) != NULL
) {
639 struct ng_bridge_link
*const destLink
640 = priv
->links
[host
->linkNum
];
642 /* If destination same as incoming link, do nothing */
643 KASSERT(destLink
!= NULL
,
644 ("%s: link%d null", __func__
, host
->linkNum
));
645 if (destLink
== link
) {
646 NG_FREE_DATA(m
, meta
);
650 /* Deliver packet out the destination link */
651 destLink
->stats
.xmitPackets
++;
652 destLink
->stats
.xmitOctets
+= m
->m_pkthdr
.len
;
653 NG_SEND_DATA(error
, destLink
->hook
, m
, meta
);
657 /* Destination host is not known */
658 link
->stats
.recvUnknown
++;
661 /* Distribute unknown, multicast, broadcast pkts to all other links */
662 for (linkNum
= i
= 0; i
< priv
->numLinks
- 1; linkNum
++) {
663 struct ng_bridge_link
*const destLink
= priv
->links
[linkNum
];
667 /* Skip incoming link and disconnected links */
668 if (destLink
== NULL
|| destLink
== link
)
671 /* Copy mbuf and meta info */
672 if (++i
== priv
->numLinks
- 1) { /* last link */
676 m2
= m_dup(m
, M_NOWAIT
); /* XXX m_copypacket() */
678 link
->stats
.memoryFailures
++;
679 NG_FREE_DATA(m
, meta
);
683 && (meta2
= ng_copy_meta(meta
)) == NULL
) {
684 link
->stats
.memoryFailures
++;
686 NG_FREE_DATA(m
, meta
);
692 destLink
->stats
.xmitPackets
++;
693 destLink
->stats
.xmitOctets
+= m
->m_pkthdr
.len
;
695 case 0: /* unicast */
697 case 1: /* multicast */
698 destLink
->stats
.xmitMulticasts
++;
700 case 2: /* broadcast */
701 destLink
->stats
.xmitBroadcasts
++;
706 NG_SEND_DATA(error
, destLink
->hook
, m2
, meta2
);
715 ng_bridge_rmnode(node_p node
)
717 const priv_p priv
= node
->private;
720 * Shut down everything except the timer. There's no way to
721 * avoid another possible timeout event (it may have already
722 * been dequeued), so we can't free the node yet.
725 ng_cutlinks(node
); /* frees all link and host info */
726 KASSERT(priv
->numLinks
== 0 && priv
->numHosts
== 0,
727 ("%s: numLinks=%d numHosts=%d",
728 __func__
, priv
->numLinks
, priv
->numHosts
));
729 kfree(priv
->tab
, M_NETGRAPH
);
731 /* NG_INVALID flag is now set so node will be freed at next timeout */
736 * Hook disconnection.
739 ng_bridge_disconnect(hook_p hook
)
741 const priv_p priv
= hook
->node
->private;
744 /* Get link number */
745 linkNum
= LINK_NUM(hook
);
746 KASSERT(linkNum
>= 0 && linkNum
< NG_BRIDGE_MAX_LINKS
,
747 ("%s: linkNum=%u", __func__
, linkNum
));
749 /* Remove all hosts associated with this link */
750 ng_bridge_remove_hosts(priv
, linkNum
);
752 /* Free associated link information */
753 KASSERT(priv
->links
[linkNum
] != NULL
, ("%s: no link", __func__
));
754 kfree(priv
->links
[linkNum
], M_NETGRAPH
);
755 priv
->links
[linkNum
] = NULL
;
758 /* If no more hooks, go away */
759 if (hook
->node
->numhooks
== 0)
760 ng_rmnode(hook
->node
);
764 /******************************************************************
766 ******************************************************************/
771 * Only hashing bytes 3-6 of the Ethernet address is sufficient and fast.
773 #define HASH(addr,mask) ( (((const u_int16_t *)(addr))[0] \
774 ^ ((const u_int16_t *)(addr))[1] \
775 ^ ((const u_int16_t *)(addr))[2]) & (mask) )
778 * Find a host entry in the table.
780 static struct ng_bridge_host
*
781 ng_bridge_get(priv_p priv
, const u_char
*addr
)
783 const int bucket
= HASH(addr
, priv
->hashMask
);
784 struct ng_bridge_hent
*hent
;
786 SLIST_FOREACH(hent
, &priv
->tab
[bucket
], next
) {
787 if (ETHER_EQUAL(hent
->host
.addr
, addr
))
788 return (&hent
->host
);
794 * Add a new host entry to the table. This assumes the host doesn't
795 * already exist in the table. Returns 1 on success, 0 if there
796 * was a memory allocation failure.
799 ng_bridge_put(priv_p priv
, const u_char
*addr
, int linkNum
)
801 const int bucket
= HASH(addr
, priv
->hashMask
);
802 struct ng_bridge_hent
*hent
;
805 char ethstr
[ETHER_ADDRSTRLEN
+ 1];
807 /* Assert that entry does not already exist in hashtable */
808 SLIST_FOREACH(hent
, &priv
->tab
[bucket
], next
) {
809 KASSERT(!ETHER_EQUAL(hent
->host
.addr
, addr
),
810 ("%s: entry %s exists in table", __func__
, kether_ntoa(addr
, ethstr
)));
814 /* Allocate and initialize new hashtable entry */
815 hent
= kmalloc(sizeof(*hent
), M_NETGRAPH
, M_NOWAIT
);
818 bcopy(addr
, hent
->host
.addr
, ETHER_ADDR_LEN
);
819 hent
->host
.linkNum
= linkNum
;
820 hent
->host
.staleness
= 0;
823 /* Add new element to hash bucket */
824 SLIST_INSERT_HEAD(&priv
->tab
[bucket
], hent
, next
);
827 /* Resize table if necessary */
828 ng_bridge_rehash(priv
);
833 * Resize the hash table. We try to maintain the number of buckets
834 * such that the load factor is in the range 0.25 to 1.0.
836 * If we can't get the new memory then we silently fail. This is OK
837 * because things will still work and we'll try again soon anyway.
840 ng_bridge_rehash(priv_p priv
)
842 struct ng_bridge_bucket
*newTab
;
843 int oldBucket
, newBucket
;
847 /* Is table too full or too empty? */
848 if (priv
->numHosts
> priv
->numBuckets
849 && (priv
->numBuckets
<< 1) <= MAX_BUCKETS
)
850 newNumBuckets
= priv
->numBuckets
<< 1;
851 else if (priv
->numHosts
< (priv
->numBuckets
>> 2)
852 && (priv
->numBuckets
>> 2) >= MIN_BUCKETS
)
853 newNumBuckets
= priv
->numBuckets
>> 2;
856 newMask
= newNumBuckets
- 1;
858 /* Allocate and initialize new table */
859 newTab
= kmalloc(newNumBuckets
* sizeof(*newTab
), M_NETGRAPH
,
864 /* Move all entries from old table to new table */
865 for (oldBucket
= 0; oldBucket
< priv
->numBuckets
; oldBucket
++) {
866 struct ng_bridge_bucket
*const oldList
= &priv
->tab
[oldBucket
];
868 while (!SLIST_EMPTY(oldList
)) {
869 struct ng_bridge_hent
*const hent
870 = SLIST_FIRST(oldList
);
872 SLIST_REMOVE_HEAD(oldList
, next
);
873 newBucket
= HASH(hent
->host
.addr
, newMask
);
874 SLIST_INSERT_HEAD(&newTab
[newBucket
], hent
, next
);
878 /* Replace old table with new one */
879 if (priv
->conf
.debugLevel
>= 3) {
880 log(LOG_INFO
, "ng_bridge: %s: table size %d -> %d\n",
881 ng_bridge_nodename(priv
->node
),
882 priv
->numBuckets
, newNumBuckets
);
884 kfree(priv
->tab
, M_NETGRAPH
);
885 priv
->numBuckets
= newNumBuckets
;
886 priv
->hashMask
= newMask
;
891 /******************************************************************
893 ******************************************************************/
896 * Remove all hosts associated with a specific link from the hashtable.
897 * If linkNum == -1, then remove all hosts in the table.
900 ng_bridge_remove_hosts(priv_p priv
, int linkNum
)
904 for (bucket
= 0; bucket
< priv
->numBuckets
; bucket
++) {
905 struct ng_bridge_hent
**hptr
= &SLIST_FIRST(&priv
->tab
[bucket
]);
907 while (*hptr
!= NULL
) {
908 struct ng_bridge_hent
*const hent
= *hptr
;
910 if (linkNum
== -1 || hent
->host
.linkNum
== linkNum
) {
911 *hptr
= SLIST_NEXT(hent
, next
);
912 kfree(hent
, M_NETGRAPH
);
915 hptr
= &SLIST_NEXT(hent
, next
);
921 * Handle our once-per-second timeout event. We do two things:
922 * we decrement link->loopCount for those links being muted due to
923 * a detected loopback condition, and we remove any hosts from
924 * the hashtable whom we haven't heard from in a long while.
926 * If the node has the NG_INVALID flag set, our job is to kill it.
929 ng_bridge_timeout(void *arg
)
931 const node_p node
= arg
;
932 const priv_p priv
= node
->private;
936 char ethstr
[ETHER_ADDRSTRLEN
+ 1] __debugvar
;
938 /* If node was shut down, this is the final lingering timeout */
940 if ((node
->flags
& NG_INVALID
) != 0) {
941 kfree(priv
, M_NETGRAPH
);
942 node
->private = NULL
;
948 /* Register a new timeout, keeping the existing node reference */
949 callout_reset(&priv
->timer
, hz
, ng_bridge_timeout
, node
);
951 /* Update host time counters and remove stale entries */
952 for (bucket
= 0; bucket
< priv
->numBuckets
; bucket
++) {
953 struct ng_bridge_hent
**hptr
= &SLIST_FIRST(&priv
->tab
[bucket
]);
955 while (*hptr
!= NULL
) {
956 struct ng_bridge_hent
*const hent
= *hptr
;
958 /* Make sure host's link really exists */
959 KASSERT(priv
->links
[hent
->host
.linkNum
] != NULL
,
960 ("%s: host %s on nonexistent link %d",
961 __func__
, kether_ntoa(hent
->host
.addr
, ethstr
),
962 hent
->host
.linkNum
));
964 /* Remove hosts we haven't heard from in a while */
965 if (++hent
->host
.staleness
>= priv
->conf
.maxStaleness
) {
966 *hptr
= SLIST_NEXT(hent
, next
);
967 kfree(hent
, M_NETGRAPH
);
970 if (hent
->host
.age
< 0xffff)
972 hptr
= &SLIST_NEXT(hent
, next
);
977 KASSERT(priv
->numHosts
== counter
,
978 ("%s: hosts: %d != %d", __func__
, priv
->numHosts
, counter
));
980 /* Decrease table size if necessary */
981 ng_bridge_rehash(priv
);
983 /* Decrease loop counter on muted looped back links */
984 for (counter
= linkNum
= 0; linkNum
< NG_BRIDGE_MAX_LINKS
; linkNum
++) {
985 struct ng_bridge_link
*const link
= priv
->links
[linkNum
];
988 if (link
->loopCount
!= 0) {
990 if (link
->loopCount
== 0
991 && priv
->conf
.debugLevel
>= 2) {
992 log(LOG_INFO
, "ng_bridge: %s:"
993 " restoring looped back link%d\n",
994 ng_bridge_nodename(node
), linkNum
);
1000 KASSERT(priv
->numLinks
== counter
,
1001 ("%s: links: %d != %d", __func__
, priv
->numLinks
, counter
));
1008 * Return node's "name", even if it doesn't have one.
1011 ng_bridge_nodename(node_p node
)
1013 static char name
[NG_NODESIZ
];
1015 if (node
->name
!= NULL
)
1016 ksnprintf(name
, sizeof(name
), "%s", node
->name
);
1018 ksnprintf(name
, sizeof(name
), "[%x]", ng_node2ID(node
));