Make all network interrupt service routines MPSAFE part 1/3.
[dragonfly.git] / sys / net / bridge / bridge.c
1 /*
2  * Copyright (c) 1998-2002 Luigi Rizzo
3  *
4  * Work partly supported by: Cisco Systems, Inc. - NSITE lab, RTP, NC
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  *
15  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND
16  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
19  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25  * SUCH DAMAGE.
26  *
27  * $FreeBSD: src/sys/net/bridge.c,v 1.16.2.25 2003/01/23 21:06:44 sam Exp $
28  * $DragonFly: src/sys/net/bridge/Attic/bridge.c,v 1.19 2005/11/28 17:13:45 dillon Exp $
29  */
30
31 /*
32  * This code implements bridging in FreeBSD. It only acts on ethernet
33  * interfaces, including VLANs (others are still usable for routing).
34  * A FreeBSD host can implement multiple logical bridges, called
35  * "clusters". Each cluster is made of a set of interfaces, and
36  * identified by a "cluster-id" which is a number in the range 1..2^16-1.
37  *
38  * Bridging is enabled by the sysctl variable
39  *      net.link.ether.bridge
40  * the grouping of interfaces into clusters is done with
41  *      net.link.ether.bridge_cfg
42  * containing a list of interfaces each optionally followed by
43  * a colon and the cluster it belongs to (1 is the default).
44  * Separators can be * spaces, commas or tabs, e.g.
45  *      net.link.ether.bridge_cfg="fxp0:2 fxp1:2 dc0 dc1:1"
46  * Optionally bridged packets can be passed through the firewall,
47  * this is controlled by the variable
48  *      net.link.ether.bridge_ipfw
49  *
50  * For each cluster there is a descriptor (cluster_softc) storing
51  * the following data structures:
52  * - a hash table with the MAC address and destination interface for each
53  *   known node. The table is indexed using a hash of the source address.
54  * - an array with the MAC addresses of the interfaces used in the cluster.
55  *
56  * Input packets are tapped near the beginning of ether_input(), and
57  * analysed by bridge_in(). Depending on the result, the packet
58  * can be forwarded to one or more output interfaces using bdg_forward(),
59  * and/or sent to the upper layer (e.g. in case of multicast).
60  *
61  * Output packets are intercepted near the end of ether_output().
62  * The correct destination is selected by bridge_dst_lookup(),
63  * and then forwarding is done by bdg_forward().
64  *
65  * The arp code is also modified to let a machine answer to requests
66  * irrespective of the port the request came from.
67  *
68  * In case of loops in the bridging topology, the bridge detects this
69  * event and temporarily mutes output bridging on one of the ports.
70  * Periodically, interfaces are unmuted by bdg_timeout().
71  * Muting is only implemented as a safety measure, and also as
72  * a mechanism to support a user-space implementation of the spanning
73  * tree algorithm.
74  *
75  * To build a bridging kernel, use the following option
76  *    option BRIDGE
77  * and then at runtime set the sysctl variable to enable bridging.
78  *
79  * Only one interface per cluster is supposed to have addresses set (but
80  * there are no substantial problems if you set addresses for none or
81  * for more than one interface).
82  * Bridging will act before routing, but nothing prevents a machine
83  * from doing both (modulo bugs in the implementation...).
84  *
85  * THINGS TO REMEMBER
86  *  - bridging is incompatible with multicast routing on the same
87  *    machine. There is not an easy fix to this.
88  *  - be very careful when bridging VLANs
89  *  - loop detection is still not very robust.
90  */
91
92 #include <sys/param.h>
93 #include <sys/mbuf.h>
94 #include <sys/malloc.h>
95 #include <sys/systm.h>
96 #include <sys/socket.h> /* for net/if.h */
97 #include <sys/ctype.h>  /* string functions */
98 #include <sys/kernel.h>
99 #include <sys/sysctl.h>
100 #include <sys/thread2.h>
101
102 #include <net/if.h>
103 #include <net/if_types.h>
104 #include <net/if_llc.h>
105 #include <net/if_var.h>
106 #include <net/ifq_var.h>
107 #include <net/pfil.h>
108
109 #include <netinet/in.h> /* for struct arpcom */
110 #include <netinet/in_systm.h>
111 #include <netinet/in_var.h>
112 #include <netinet/ip.h>
113 #include <netinet/ip_var.h>
114 #include <netinet/if_ether.h> /* for struct arpcom */
115
116 #include <net/route.h>
117 #include <net/ipfw/ip_fw.h>
118 #include <net/dummynet/ip_dummynet.h>
119 #include "bridge.h"
120
121 /*--------------------*/
122
123 /*
124  * For each cluster, source MAC addresses are stored into a hash
125  * table which locates the port they reside on.
126  */
127 #define HASH_SIZE 8192  /* Table size, must be a power of 2 */
128
129 typedef struct hash_table {             /* each entry.          */
130     struct ifnet *      name;
131     u_char              etheraddr[6];
132     u_int16_t           used;           /* also, padding        */
133 } bdg_hash_table ;
134
135 /*
136  * The hash function applied to MAC addresses. Out of the 6 bytes,
137  * the last ones tend to vary more. Since we are on a little endian machine,
138  * we have to do some gimmick...
139  */
140 #define HASH_FN(addr)   (       \
141     ntohs( ((u_int16_t *)addr)[1] ^ ((u_int16_t *)addr)[2] ) & (HASH_SIZE -1))
142
143 /*
144  * This is the data structure where local addresses are stored.
145  */
146 struct bdg_addr {
147     u_char      etheraddr[6] ;
148     u_int16_t   _padding ;
149 };
150
151 /*
152  * The configuration of each cluster includes the cluster id, a pointer to
153  * the hash table, and an array of local MAC addresses (of size "ports").
154  */
155 struct cluster_softc {
156     u_int16_t   cluster_id;
157     u_int16_t   ports;
158     bdg_hash_table *ht;
159     struct bdg_addr     *my_macs;       /* local MAC addresses */
160 };
161
162
163 extern struct protosw inetsw[];                 /* from netinet/ip_input.c */
164
165 static int n_clusters;                          /* number of clusters */
166 static struct cluster_softc *clusters;
167
168 #define BDG_MUTED(ifp) (ifp2sc[ifp->if_index].flags & IFF_MUTE)
169 #define BDG_MUTE(ifp) ifp2sc[ifp->if_index].flags |= IFF_MUTE
170 #define BDG_CLUSTER(ifp) (ifp2sc[ifp->if_index].cluster)
171
172 #define BDG_SAMECLUSTER(ifp,src) \
173         (src == NULL || BDG_CLUSTER(ifp) == BDG_CLUSTER(src) )
174
175 #ifdef __i386__
176 #define BDG_MATCH(a,b) ( \
177     ((u_int16_t *)(a))[2] == ((u_int16_t *)(b))[2] && \
178     *((u_int32_t *)(a)) == *((u_int32_t *)(b)) )
179 #define IS_ETHER_BROADCAST(a) ( \
180         *((u_int32_t *)(a)) == 0xffffffff && \
181         ((u_int16_t *)(a))[2] == 0xffff )
182 #else
183 /* for machines that do not support unaligned access */
184 #define BDG_MATCH(a,b)          (!bcmp(a, b, ETHER_ADDR_LEN) )
185 #define IS_ETHER_BROADCAST(a)   (!bcmp(a, "\377\377\377\377\377\377", 6))
186 #endif
187
188
189 /*
190  * For timing-related debugging, you can use the following macros.
191  * remember, rdtsc() only works on Pentium-class machines
192
193     quad_t ticks;
194     DDB(ticks = rdtsc();)
195     ... interesting code ...
196     DDB(bdg_fw_ticks += (u_long)(rdtsc() - ticks) ; bdg_fw_count++ ;)
197
198  *
199  */
200
201 #define DDB(x) x
202 #define DEB(x)
203
204 static int bdginit(void);
205 static void parse_bdg_cfg(void);
206
207 static int bdg_pfil;            /* PFIL hooks enabled in bridge */
208 static int bdg_ipfw;
209
210 #if 0 /* debugging only */
211 static char *bdg_dst_names[] = {
212         "BDG_NULL    ",
213         "BDG_BCAST   ",
214         "BDG_MCAST   ",
215         "BDG_LOCAL   ",
216         "BDG_DROP    ",
217         "BDG_UNKNOWN ",
218         "BDG_IN      ",
219         "BDG_OUT     ",
220         "BDG_FORWARD " };
221 #endif
222 /*
223  * System initialization
224  */
225
226 static struct bdg_stats bdg_stats ;
227 static struct callout bdg_timeout_h ;
228
229 /*
230  * Add an interface to a cluster, possibly creating a new entry in
231  * the cluster table. This requires reallocation of the table and
232  * updating pointers in ifp2sc.
233  */
234 static struct cluster_softc *
235 add_cluster(u_int16_t cluster_id, struct arpcom *ac)
236 {
237     struct cluster_softc *c = NULL;
238     int i;
239
240     for (i = 0; i < n_clusters ; i++)
241         if (clusters[i].cluster_id == cluster_id)
242             goto found;
243
244     /* Not found, need to reallocate */
245     c = malloc((1+n_clusters) * sizeof (*c), M_IFADDR, M_WAITOK | M_ZERO);
246     c[n_clusters].ht = malloc(HASH_SIZE * sizeof(struct hash_table),
247                                 M_IFADDR, M_WAITOK | M_ZERO);
248     c[n_clusters].my_macs = malloc(BDG_MAX_PORTS * sizeof(struct bdg_addr),
249                                 M_IFADDR, M_WAITOK | M_ZERO);
250
251     c[n_clusters].cluster_id = cluster_id;
252     c[n_clusters].ports = 0;
253     /*
254      * now copy old descriptors here
255      */
256     if (n_clusters > 0) {
257         for (i=0; i < n_clusters; i++)
258             c[i] = clusters[i];
259         /*
260          * and finally update pointers in ifp2sc
261          */
262         for (i = 0 ; i < if_index && i < BDG_MAX_PORTS; i++)
263             if (ifp2sc[i].cluster != NULL)
264                 ifp2sc[i].cluster = c + (ifp2sc[i].cluster - clusters);
265         free(clusters, M_IFADDR);
266     }
267     clusters = c;
268     i = n_clusters;             /* index of cluster entry */
269     n_clusters++;
270 found:
271     c = clusters + i;           /* the right cluster ... */
272     bcopy(ac->ac_enaddr, &(c->my_macs[c->ports]), 6);
273     c->ports++;
274     return c;
275 }
276
277
278 /*
279  * Turn off bridging, by clearing promisc mode on the interface,
280  * marking the interface as unused, and clearing the name in the
281  * stats entry.
282  * Also dispose the hash tables associated with the clusters.
283  */
284 static void
285 bridge_off(void)
286 {
287     struct ifnet *ifp ;
288     int i;
289
290     DEB(printf("bridge_off: n_clusters %d\n", n_clusters);)
291     TAILQ_FOREACH(ifp, &ifnet, if_link) {
292         struct bdg_softc *b;
293
294         if (ifp->if_index >= BDG_MAX_PORTS)
295             continue;   /* make sure we do not go beyond the end */
296         b = &(ifp2sc[ifp->if_index]);
297
298         if ( b->flags & IFF_BDG_PROMISC ) {
299             crit_enter();
300             ifpromisc(ifp, 0);
301             crit_exit();
302             b->flags &= ~(IFF_BDG_PROMISC|IFF_MUTE) ;
303             DEB(printf(">> now %s promisc OFF if_flags 0x%x bdg_flags 0x%x\n",
304                     ifp->if_xname,
305                     ifp->if_flags, b->flags);)
306         }
307         b->flags &= ~(IFF_USED) ;
308         b->cluster = NULL;
309         bdg_stats.s[ifp->if_index].name[0] = '\0';
310     }
311     /* flush_tables */
312
313     crit_enter();
314     for (i=0; i < n_clusters; i++) {
315         free(clusters[i].ht, M_IFADDR);
316         free(clusters[i].my_macs, M_IFADDR);
317     }
318     if (clusters != NULL)
319         free(clusters, M_IFADDR);
320     clusters = NULL;
321     n_clusters =0;
322     crit_exit();
323 }
324
325 /*
326  * set promisc mode on the interfaces we use.
327  */
328 static void
329 bridge_on(void)
330 {
331     struct ifnet *ifp ;
332
333     TAILQ_FOREACH(ifp, &ifnet, if_link) {
334         struct bdg_softc *b = &ifp2sc[ifp->if_index];
335
336         if ( !(b->flags & IFF_USED) )
337             continue ;
338         if ( !( ifp->if_flags & IFF_UP) ) {
339             crit_enter();
340             if_up(ifp);
341             crit_exit();
342         }
343         if ( !(b->flags & IFF_BDG_PROMISC) ) {
344             int ret ;
345             crit_enter();
346             ret = ifpromisc(ifp, 1);
347             crit_exit();
348             b->flags |= IFF_BDG_PROMISC ;
349             DEB(printf(">> now %s promisc ON if_flags 0x%x bdg_flags 0x%x\n",
350                     ifp->if_xname,
351                     ifp->if_flags, b->flags);)
352         }
353         if (b->flags & IFF_MUTE) {
354             DEB(printf(">> unmuting %s\n", ifp->if_xname);)
355             b->flags &= ~IFF_MUTE;
356         }
357     }
358 }
359
360 /**
361  * reconfigure bridge.
362  * This is also done every time we attach or detach an interface.
363  * Main use is to make sure that we do not bridge on some old
364  * (ejected) device. So, it would be really useful to have a
365  * pointer to the modified device as an argument. Without it, we
366  * have to scan all interfaces.
367  */
368 static void
369 reconfigure_bridge(void)
370 {
371     bridge_off();
372     if (do_bridge) {
373         if (if_index >= BDG_MAX_PORTS) {
374             printf("-- sorry too many interfaces (%d, max is %d),"
375                 " disabling bridging\n", if_index, BDG_MAX_PORTS);
376             do_bridge=0;
377             return;
378         }
379         parse_bdg_cfg();
380         bridge_on();
381     }
382 }
383
384 static char bridge_cfg[1024]; /* in BSS so initialized to all NULs */
385
386 /*
387  * parse the config string, set IFF_USED, name and cluster_id
388  * for all interfaces found.
389  * The config string is a list of "if[:cluster]" with
390  * a number of possible separators (see "sep"). In particular the
391  * use of the space lets you set bridge_cfg with the output from
392  * "ifconfig -l"
393  */
394 static void
395 parse_bdg_cfg()
396 {
397     char *p, *beg ;
398     int l, cluster;
399     static char *sep = ", \t";
400
401     for (p = bridge_cfg; *p ; p++) {
402         struct ifnet *ifp;
403         int found = 0;
404         char c;
405
406         if (index(sep, *p))     /* skip separators */
407             continue ;
408         /* names are lowercase and digits */
409         for ( beg = p ; islower(*p) || isdigit(*p) ; p++ )
410             ;
411         l = p - beg ;           /* length of name string */
412         if (l == 0)             /* invalid name */
413             break ;
414         if ( *p != ':' )        /* no ':', assume default cluster 1 */
415             cluster = 1 ;
416         else                    /* fetch cluster */
417             cluster = strtoul( p+1, &p, 10);
418         c = *p;
419         *p = '\0';
420         /*
421          * now search in interface list for a matching name
422          */
423         TAILQ_FOREACH(ifp, &ifnet, if_link) {
424             char buf[IFNAMSIZ];
425
426             snprintf(buf, sizeof(buf), "%s", ifp->if_xname);
427             if (!strncmp(beg, buf, max(l, strlen(buf)))) {
428                 struct bdg_softc *b = &ifp2sc[ifp->if_index];
429                 if (ifp->if_type != IFT_ETHER && ifp->if_type != IFT_L2VLAN) {
430                     printf("%s is not an ethernet, continue\n", buf);
431                     continue;
432                 }
433                 if (b->flags & IFF_USED) {
434                     printf("%s already used, skipping\n", buf);
435                     break;
436                 }
437                 b->cluster = add_cluster(htons(cluster), (struct arpcom *)ifp);
438                 b->flags |= IFF_USED ;
439                 sprintf(bdg_stats.s[ifp->if_index].name,
440                         "%s:%d", ifp->if_xname, cluster);
441
442                 DEB(printf("--++  found %s next c %d\n",
443                     bdg_stats.s[ifp->if_index].name, c);)
444                 found = 1;
445                 break ;
446             }
447         }
448         if (!found)
449             printf("interface %s Not found in bridge\n", beg);
450         *p = c;
451         if (c == '\0')
452             break; /* no more */
453     }
454 }
455
456
457 /*
458  * handler for net.link.ether.bridge
459  */
460 static int
461 sysctl_bdg(SYSCTL_HANDLER_ARGS)
462 {
463     int error, oldval = do_bridge ;
464
465     error = sysctl_handle_int(oidp, oidp->oid_arg1, oidp->oid_arg2, req);
466     DEB( printf("called sysctl for bridge name %s arg2 %d val %d->%d\n",
467         oidp->oid_name, oidp->oid_arg2,
468         oldval, do_bridge); )
469
470     if (oldval != do_bridge)
471         reconfigure_bridge();
472     return error ;
473 }
474
475 /*
476  * handler for net.link.ether.bridge_cfg
477  */
478 static int
479 sysctl_bdg_cfg(SYSCTL_HANDLER_ARGS)
480 {
481     int error = 0 ;
482     char old_cfg[1024] ;
483
484     strcpy(old_cfg, bridge_cfg) ;
485
486     error = sysctl_handle_string(oidp, bridge_cfg, oidp->oid_arg2, req);
487     DEB(
488         printf("called sysctl for bridge name %s arg2 %d err %d val %s->%s\n",
489                 oidp->oid_name, oidp->oid_arg2,
490                 error,
491                 old_cfg, bridge_cfg);
492         )
493     if (strcmp(old_cfg, bridge_cfg))
494         reconfigure_bridge();
495     return error ;
496 }
497
498 static int
499 sysctl_refresh(SYSCTL_HANDLER_ARGS)
500 {
501     if (req->newptr)
502         reconfigure_bridge();
503
504     return 0;
505 }
506
507
508 SYSCTL_DECL(_net_link_ether);
509 SYSCTL_PROC(_net_link_ether, OID_AUTO, bridge_cfg, CTLTYPE_STRING|CTLFLAG_RW,
510             &bridge_cfg, sizeof(bridge_cfg), &sysctl_bdg_cfg, "A",
511             "Bridge configuration");
512
513 SYSCTL_PROC(_net_link_ether, OID_AUTO, bridge, CTLTYPE_INT|CTLFLAG_RW,
514             &do_bridge, 0, &sysctl_bdg, "I", "Bridging");
515
516 SYSCTL_INT(_net_link_ether, OID_AUTO, bridge_ipfw, CTLFLAG_RW,
517             &bdg_ipfw,0,"Pass bridged pkts through IPFW");
518
519 SYSCTL_INT(_net_link_ether, OID_AUTO, bridge_pfil, CTLFLAG_RW,
520             &bdg_pfil, 0,"Pass bridged pkts through PFIL hooks");
521
522 /*
523  * The follow macro declares a variable, and maps it to
524  * a SYSCTL_INT entry with the same name.
525  */
526 #define SY(parent, var, comment)                        \
527         static int var ;                                \
528         SYSCTL_INT(parent, OID_AUTO, var, CTLFLAG_RW, &(var), 0, comment);
529
530 int bdg_ipfw_drops;
531 SYSCTL_INT(_net_link_ether, OID_AUTO, bridge_ipfw_drop,
532         CTLFLAG_RW, &bdg_ipfw_drops,0,"");
533
534 int bdg_ipfw_colls;
535 SYSCTL_INT(_net_link_ether, OID_AUTO, bridge_ipfw_collisions,
536         CTLFLAG_RW, &bdg_ipfw_colls,0,"");
537
538 SYSCTL_PROC(_net_link_ether, OID_AUTO, bridge_refresh, CTLTYPE_INT|CTLFLAG_WR,
539             NULL, 0, &sysctl_refresh, "I", "iface refresh");
540
541 #if 1 /* diagnostic vars */
542
543 SY(_net_link_ether, verbose, "Be verbose");
544 SY(_net_link_ether, bdg_split_pkts, "Packets split in bdg_forward");
545
546 SY(_net_link_ether, bdg_thru, "Packets through bridge");
547
548 SY(_net_link_ether, bdg_copied, "Packets copied in bdg_forward");
549
550 SY(_net_link_ether, bdg_copy, "Force copy in bdg_forward");
551 SY(_net_link_ether, bdg_predict, "Correctly predicted header location");
552
553 SY(_net_link_ether, bdg_fw_avg, "Cycle counter avg");
554 SY(_net_link_ether, bdg_fw_ticks, "Cycle counter item");
555 SY(_net_link_ether, bdg_fw_count, "Cycle counter count");
556 #endif
557
558 SYSCTL_STRUCT(_net_link_ether, PF_BDG, bdgstats,
559         CTLFLAG_RD, &bdg_stats , bdg_stats, "bridge statistics");
560
561 static int bdg_loops ;
562
563 /*
564  * called periodically to flush entries etc.
565  */
566 static void
567 bdg_timeout(void *dummy)
568 {
569     static int slowtimer; /* in BSS so initialized to 0 */
570
571     if (do_bridge) {
572         static int age_index = 0 ; /* index of table position to age */
573         int l = age_index + HASH_SIZE/4 ;
574         int i;
575         /*
576          * age entries in the forwarding table.
577          */
578         if (l > HASH_SIZE)
579             l = HASH_SIZE ;
580
581         for (i=0; i<n_clusters; i++) {
582             bdg_hash_table *bdg_table = clusters[i].ht;
583             for (; age_index < l ; age_index++)
584                 if (bdg_table[age_index].used)
585                     bdg_table[age_index].used = 0 ;
586                 else if (bdg_table[age_index].name) {
587                     /* printf("xx flushing stale entry %d\n", age_index); */
588                     bdg_table[age_index].name = NULL ;
589                 }
590         }
591         if (age_index >= HASH_SIZE)
592             age_index = 0 ;
593
594         if (--slowtimer <= 0 ) {
595             slowtimer = 5 ;
596
597             bridge_on() ; /* we just need unmute, really */
598             bdg_loops = 0 ;
599         }
600     }
601     callout_reset(&bdg_timeout_h, 2*hz, bdg_timeout, NULL);
602 }
603
604 /*
605  * Find the right pkt destination:
606  *      BDG_BCAST       is a broadcast
607  *      BDG_MCAST       is a multicast
608  *      BDG_LOCAL       is for a local address
609  *      BDG_DROP        must be dropped
610  *      other           ifp of the dest. interface (incl.self)
611  *
612  * We assume this is only called for interfaces for which bridging
613  * is enabled, i.e. BDG_USED(ifp) is true.
614  */
615 static __inline
616 struct ifnet *
617 bridge_dst_lookup(struct ether_header *eh, struct cluster_softc *c)
618 {
619     struct ifnet *dst ;
620     int index ;
621     struct bdg_addr *p ;
622     bdg_hash_table *bt;         /* pointer to entry in hash table */
623
624     if (IS_ETHER_BROADCAST(eh->ether_dhost))
625         return BDG_BCAST ;
626     if (eh->ether_dhost[0] & 1)
627         return BDG_MCAST ;
628     /*
629      * Lookup local addresses in case one matches.
630      */
631     for (index = c->ports, p = c->my_macs; index ; index--, p++ )
632         if (BDG_MATCH(p->etheraddr, eh->ether_dhost) )
633             return BDG_LOCAL ;
634     /*
635      * Look for a possible destination in table
636      */
637     index= HASH_FN( eh->ether_dhost );
638     bt = &(c->ht[index]);
639     dst = bt->name;
640     if ( dst && BDG_MATCH( bt->etheraddr, eh->ether_dhost) )
641         return dst ;
642     else
643         return BDG_UNKNOWN ;
644 }
645
646 /**
647  * bridge_in() is invoked to perform bridging decision on input packets.
648  *
649  * On Input:
650  *   eh         Ethernet header of the incoming packet.
651  *   ifp        interface the packet is coming from.
652  *
653  * On Return: destination of packet, one of
654  *   BDG_BCAST  broadcast
655  *   BDG_MCAST  multicast
656  *   BDG_LOCAL  is only for a local address (do not forward)
657  *   BDG_DROP   drop the packet
658  *   ifp        ifp of the destination interface.
659  *
660  * Forwarding is not done directly to give a chance to some drivers
661  * to fetch more of the packet, or simply drop it completely.
662  */
663
664 static struct ifnet *
665 bridge_in(struct ifnet *ifp, struct ether_header *eh)
666 {
667     int index;
668     struct ifnet *dst , *old ;
669     bdg_hash_table *bt;                 /* location in hash table */
670     int dropit = BDG_MUTED(ifp) ;
671
672     /*
673      * hash the source address
674      */
675     index= HASH_FN(eh->ether_shost);
676     bt = &(ifp2sc[ifp->if_index].cluster->ht[index]);
677     bt->used = 1 ;
678     old = bt->name ;
679     if ( old ) { /* the entry is valid. */
680         if (!BDG_MATCH( eh->ether_shost, bt->etheraddr) ) {
681             bdg_ipfw_colls++ ;
682             bt->name = NULL ;
683         } else if (old != ifp) {
684             /*
685              * Found a loop. Either a machine has moved, or there
686              * is a misconfiguration/reconfiguration of the network.
687              * First, do not forward this packet!
688              * Record the relocation anyways; then, if loops persist,
689              * suspect a reconfiguration and disable forwarding
690              * from the old interface.
691              */
692             bt->name = ifp ; /* relocate address */
693             printf("-- loop (%d) %6D to %s from %s (%s)\n",
694                         bdg_loops, eh->ether_shost, ".",
695                         ifp->if_xname, old->if_xname,
696                         BDG_MUTED(old) ? "muted":"active");
697             dropit = 1 ;
698             if ( !BDG_MUTED(old) ) {
699                 if (++bdg_loops > 10)
700                     BDG_MUTE(old) ;
701             }
702         }
703     }
704
705     /*
706      * now write the source address into the table
707      */
708     if (bt->name == NULL) {
709         DEB(printf("new addr %6D at %d for %s\n",
710             eh->ether_shost, ".", index, ifp->if_xname);)
711         bcopy(eh->ether_shost, bt->etheraddr, 6);
712         bt->name = ifp ;
713     }
714     dst = bridge_dst_lookup(eh, ifp2sc[ifp->if_index].cluster);
715     /*
716      * bridge_dst_lookup can return the following values:
717      *   BDG_BCAST, BDG_MCAST, BDG_LOCAL, BDG_UNKNOWN, BDG_DROP, ifp.
718      * For muted interfaces, or when we detect a loop, the first 3 are
719      * changed in BDG_LOCAL (we still listen to incoming traffic),
720      * and others to BDG_DROP (no use for the local host).
721      * Also, for incoming packets, ifp is changed to BDG_DROP if ifp == src.
722      * These changes are not necessary for outgoing packets from ether_output().
723      */
724     BDG_STAT(ifp, BDG_IN);
725     switch ((uintptr_t)dst) {
726     case (uintptr_t)BDG_BCAST:
727     case (uintptr_t)BDG_MCAST:
728     case (uintptr_t)BDG_LOCAL:
729     case (uintptr_t)BDG_UNKNOWN:
730     case (uintptr_t)BDG_DROP:
731         BDG_STAT(ifp, dst);
732         break ;
733     default :
734         if (dst == ifp || dropit)
735             BDG_STAT(ifp, BDG_DROP);
736         else
737             BDG_STAT(ifp, BDG_FORWARD);
738         break ;
739     }
740
741     if ( dropit ) {
742         if (dst == BDG_BCAST || dst == BDG_MCAST || dst == BDG_LOCAL)
743             dst = BDG_LOCAL ;
744         else
745             dst = BDG_DROP ;
746     } else {
747         if (dst == ifp)
748             dst = BDG_DROP;
749     }
750     DEB(printf("bridge_in %6D ->%6D ty 0x%04x dst %s\n",
751         eh->ether_shost, ".",
752         eh->ether_dhost, ".",
753         ntohs(eh->ether_type),
754         (dst <= BDG_FORWARD) ? bdg_dst_names[(int)dst]"0" :
755                 dst->if_xname); )
756
757     return dst ;
758 }
759
760 /*
761  * Forward a packet to dst -- which can be a single interface or
762  * an entire cluster. The src port and muted interfaces are excluded.
763  *
764  * If src == NULL, the pkt comes from ether_output, and dst is the real
765  * interface the packet is originally sent to. In this case, we must forward
766  * it to the whole cluster.
767  * We never call bdg_forward from ether_output on interfaces which are
768  * not part of a cluster.
769  *
770  * If possible (i.e. we can determine that the caller does not need
771  * a copy), the packet is consumed here, and bdg_forward returns NULL.
772  * Otherwise, a pointer to a copy of the packet is returned.
773  *
774  * XXX be careful with eh, it can be a pointer into *m
775  */
776 static struct mbuf *
777 bdg_forward(struct mbuf *m0, struct ether_header *const eh, struct ifnet *dst)
778 {
779     struct ifnet *src;
780     struct ifnet *ifp, *last;
781     int shared = bdg_copy ; /* someone else is using the mbuf */
782     int error, once = 0;      /* loop only once */
783     struct ifnet *real_dst = dst ; /* real dst from ether_output */
784     struct ip_fw_args args;
785     struct m_tag *mtag;
786
787     /*
788      * XXX eh is usually a pointer within the mbuf (some ethernet drivers
789      * do that), so we better copy it before doing anything with the mbuf,
790      * or we might corrupt the header.
791      */
792     struct ether_header save_eh = *eh ;
793
794     DEB(quad_t ticks; ticks = rdtsc();)
795
796     args.rule = NULL;           /* did we match a firewall rule ? */
797     /* Fetch state from dummynet tag, ignore others */
798     for (;m0->m_type == MT_TAG; m0 = m0->m_next)
799         if (m0->_m_tag_id == PACKET_TAG_DUMMYNET) {
800             args.rule = ((struct dn_pkt *)m0)->rule;
801             shared = 0;         /* For sure this is our own mbuf. */
802         }
803     if (args.rule == NULL)
804         bdg_thru++; /* first time through bdg_forward, count packet */
805
806     src = m0->m_pkthdr.rcvif;
807     if (src == NULL)                    /* packet from ether_output */
808         dst = bridge_dst_lookup(eh, ifp2sc[real_dst->if_index].cluster);
809
810     if (dst == BDG_DROP) { /* this should not happen */
811         printf("xx bdg_forward for BDG_DROP\n");
812         m_freem(m0);
813         return NULL;
814     }
815     if (dst == BDG_LOCAL) { /* this should not happen as well */
816         printf("xx ouch, bdg_forward for local pkt\n");
817         return m0;
818     }
819     if (dst == BDG_BCAST || dst == BDG_MCAST || dst == BDG_UNKNOWN) {
820         ifp = TAILQ_FIRST(&ifnet) ; /* scan all ports */
821         once = 0 ;
822         if (dst != BDG_UNKNOWN) /* need a copy for the local stack */
823             shared = 1 ;
824     } else {
825         ifp = dst ;
826         once = 1 ;
827     }
828     if ( (uintptr_t)(ifp) <= (u_int)BDG_FORWARD )
829         panic("bdg_forward: bad dst");
830
831     /*
832      * Do filtering in a very similar way to what is done in ip_output.
833      * Only if firewall is loaded, enabled, and the packet is not
834      * from ether_output() (src==NULL, or we would filter it twice).
835      * Additional restrictions may apply e.g. non-IP, short packets,
836      * and pkts already gone through a pipe.
837      */
838     if (src != NULL && (
839         (bdg_pfil && pfil_has_hooks(&inet_pfil_hook)) ||
840         (IPFW_LOADED && bdg_ipfw != 0))) {
841
842         int i;
843
844         if (args.rule != NULL && fw_one_pass)
845             goto forward; /* packet already partially processed */
846         /*
847          * i need some amt of data to be contiguous, and in case others need
848          * the packet (shared==1) also better be in the first mbuf.
849          */
850         i = min(m0->m_pkthdr.len, max_protohdr) ;
851         if ( shared || m0->m_len < i) {
852             m0 = m_pullup(m0, i) ;
853             if (m0 == NULL) {
854                 printf("-- bdg: pullup failed.\n") ;
855                 return NULL ;
856             }
857         }
858
859         /*
860          * PFIL hooks processing
861          */
862         if (bdg_pfil && pfil_has_hooks(&inet_pfil_hook) &&
863             m0->m_pkthdr.len >= sizeof(struct ip) &&
864             ntohs(save_eh.ether_type) == ETHERTYPE_IP) {
865             /*
866              * before calling the firewall, swap fields the same as IP does.
867              * here we assume the pkt is an IP one and the header is contiguous
868              */
869             struct ip *ip = mtod(m0, struct ip *);
870             int error;
871
872             ip->ip_len = ntohs(ip->ip_len);
873             ip->ip_off = ntohs(ip->ip_off);
874
875             /*
876              * XXX I think this needs to be reworked to enable stateful
877              * filtering. Think about this. For now, declare the packet as incoming.
878              */
879             error = pfil_run_hooks(&inet_pfil_hook, &m0, src, PFIL_IN);
880             if (error != 0 || m0 == NULL)
881                 return m0;
882
883             /*
884              * If we get here, the firewall has passed the pkt, but the mbuf
885              * pointer might have changed. Restore ip and the fields ntohs()'d.
886              */
887             ip = mtod(m0, struct ip *);
888             ip->ip_len = htons(ip->ip_len);
889             ip->ip_off = htons(ip->ip_off);
890         }
891
892         /*
893          * Prepare arguments and call the firewall.
894          */
895         if (!IPFW_LOADED || bdg_ipfw == 0)
896             goto forward;       /* not using ipfw, accept the packet */
897
898         /*
899          * XXX The following code is very similar to the one in
900          * if_ethersubr.c:ether_ipfw_chk()
901          */
902
903         args.m = m0;            /* the packet we are looking at         */
904         args.oif = NULL;        /* this is an input packet              */
905
906         /* no divert support */
907         if ((mtag = m_tag_find(m0, PACKET_TAG_IPFW_DIVERT, NULL)) != NULL)
908                 m_tag_delete(m0, mtag);
909
910         args.next_hop = NULL;   /* we do not support forward yet        */
911         args.eh = &save_eh;     /* MAC header for bridged/MAC packets   */
912         i = ip_fw_chk_ptr(&args);
913         m0 = args.m;            /* in case the firewall used the mbuf   */
914
915         if ( (i & IP_FW_PORT_DENY_FLAG) || m0 == NULL) /* drop */
916             return m0 ;
917
918         if (i == 0) /* a PASS rule.  */
919             goto forward ;
920         if (DUMMYNET_LOADED && (i & IP_FW_PORT_DYNT_FLAG)) {
921             /*
922              * Pass the pkt to dummynet, which consumes it.
923              * If shared, make a copy and keep the original.
924              */
925             struct mbuf *m ;
926
927             if (shared) {
928                 m = m_copypacket(m0, MB_DONTWAIT);
929                 if (m == NULL)  /* copy failed, give up */
930                     return m0;
931             } else {
932                 m = m0 ; /* pass the original to dummynet */
933                 m0 = NULL ; /* and nothing back to the caller */
934             }
935             /*
936              * Prepend the header, optimize for the common case of
937              * eh pointing into the mbuf.
938              */
939             if ( (void *)(eh + 1) == (void *)m->m_data) {
940                 m->m_data -= ETHER_HDR_LEN ;
941                 m->m_len += ETHER_HDR_LEN ;
942                 m->m_pkthdr.len += ETHER_HDR_LEN ;
943                 bdg_predict++;
944             } else {
945                 M_PREPEND(m, ETHER_HDR_LEN, MB_DONTWAIT);
946                 if (m == NULL) /* nope... */
947                     return m0 ;
948                 bcopy(&save_eh, mtod(m, struct ether_header *), ETHER_HDR_LEN);
949             }
950
951             args.oif = real_dst;
952             ip_dn_io_ptr(m, (i & 0xffff),DN_TO_BDG_FWD, &args);
953             return m0 ;
954         }
955         /*
956          * XXX at some point, add support for divert/forward actions.
957          * If none of the above matches, we have to drop the packet.
958          */
959         bdg_ipfw_drops++ ;
960         return m0 ;
961     }
962 forward:
963     /*
964      * Again, bring up the headers in case of shared bufs to avoid
965      * corruptions in the future.
966      */
967     if ( shared ) {
968         int i = min(m0->m_pkthdr.len, max_protohdr) ;
969
970         m0 = m_pullup(m0, i) ;
971         if (m0 == NULL)
972             return NULL ;
973     }
974     /*
975      * now real_dst is used to determine the cluster where to forward.
976      * For packets coming from ether_input, this is the one of the 'src'
977      * interface, whereas for locally generated packets (src==NULL) it
978      * is the cluster of the original destination interface, which
979      * was already saved into real_dst.
980      */
981     if (src != NULL)
982         real_dst = src ;
983
984     last = NULL;
985     for (;;) {
986         if (last) { /* need to forward packet leftover from previous loop */
987             struct mbuf *m ;
988             struct altq_pktattr pktattr;
989
990             if (shared == 0 && once ) { /* no need to copy */
991                 m = m0 ;
992                 m0 = NULL ; /* original is gone */
993             } else {
994                 m = m_copypacket(m0, MB_DONTWAIT);
995                 if (m == NULL) {
996                     printf("bdg_forward: sorry, m_copypacket failed!\n");
997                     return m0 ; /* the original is still there... */
998                 }
999             }
1000             if (ifq_is_enabled(&last->if_snd)) {
1001                     uint16_t ether_type;
1002                     int af;
1003
1004                     /*
1005                      * If the queueing discipline needs packet classification,
1006                      * do it before prepending link headers.
1007                      */
1008                     ether_type = ntohs(eh->ether_type);
1009                     if (ether_type == ETHERTYPE_IP)
1010                             af = AF_INET;
1011 #ifdef INET6
1012                     else if (ether_type == ETHERTYPE_IPV6)
1013                             af = AF_INET6;
1014 #endif
1015                     else
1016                             af = AF_UNSPEC;
1017                     ifq_classify(&last->if_snd, m, af, &pktattr);
1018             }
1019
1020             /*
1021              * Add header (optimized for the common case of eh pointing
1022              * already into the mbuf) and execute last part of ether_output:
1023              * queue pkt and start output if interface not yet active.
1024              */
1025             if ( (void *)(eh + 1) == (void *)m->m_data) {
1026                 m->m_data -= ETHER_HDR_LEN ;
1027                 m->m_len += ETHER_HDR_LEN ;
1028                 m->m_pkthdr.len += ETHER_HDR_LEN ;
1029                 bdg_predict++;
1030             } else {
1031                 M_PREPEND(m, ETHER_HDR_LEN, MB_DONTWAIT);
1032                 if (!m && verbose)
1033                     printf("M_PREPEND failed\n");
1034                 if (m == NULL)
1035                     return m0;
1036                 bcopy(&save_eh, mtod(m, struct ether_header *), ETHER_HDR_LEN);
1037             }
1038             lwkt_serialize_enter(last->if_serializer);
1039             error = ifq_handoff(last, m, &pktattr);
1040             lwkt_serialize_exit(last->if_serializer);
1041             if (error != 0) {
1042 #if 0
1043                 BDG_MUTE(last); /* should I also mute ? */
1044 #endif
1045             }
1046             BDG_STAT(last, BDG_OUT);
1047             last = NULL ;
1048             if (once)
1049                 break ;
1050         }
1051         if (ifp == NULL)
1052             break ;
1053         /*
1054          * If the interface is used for bridging, not muted, not full,
1055          * up and running, is not the source interface, and belongs to
1056          * the same cluster as the 'real_dst', then send here.
1057          */
1058         if ( BDG_USED(ifp) && !BDG_MUTED(ifp) &&
1059 #ifndef ALTQ
1060              !IF_QFULL(&ifp->if_snd) &&
1061 #endif
1062              (ifp->if_flags & (IFF_UP|IFF_RUNNING)) == (IFF_UP|IFF_RUNNING) &&
1063              ifp != src && BDG_SAMECLUSTER(ifp, real_dst) )
1064             last = ifp ;
1065         ifp = TAILQ_NEXT(ifp, if_link) ;
1066         if (ifp == NULL)
1067             once = 1 ;
1068     }
1069     DEB(bdg_fw_ticks += (u_long)(rdtsc() - ticks) ; bdg_fw_count++ ;
1070         if (bdg_fw_count != 0) bdg_fw_avg = bdg_fw_ticks/bdg_fw_count; )
1071     return m0 ;
1072 }
1073
1074 /*
1075  * initialization of bridge code.
1076  */
1077 static int
1078 bdginit(void)
1079 {
1080     printf("BRIDGE 020214 loaded\n");
1081
1082     ifp2sc = malloc(BDG_MAX_PORTS * sizeof(struct bdg_softc),
1083                 M_IFADDR, M_WAITOK | M_ZERO );
1084     if (ifp2sc == NULL)
1085         return ENOMEM ;
1086
1087     callout_init(&bdg_timeout_h);
1088
1089     bridge_in_ptr = bridge_in;
1090     bdg_forward_ptr = bdg_forward;
1091     bdgtakeifaces_ptr = reconfigure_bridge;
1092
1093     n_clusters = 0;
1094     clusters = NULL;
1095     do_bridge=0;
1096
1097     bzero(&bdg_stats, sizeof(bdg_stats) );
1098     bdgtakeifaces_ptr();
1099     bdg_timeout(0);
1100     return 0 ;
1101 }
1102
1103 /*
1104  * initialization code, both for static and dynamic loading.
1105  */
1106 static int
1107 bridge_modevent(module_t mod, int type, void *unused)
1108 {
1109         int err = 0 ;
1110
1111         switch (type) {
1112         case MOD_LOAD:
1113                 if (BDG_LOADED) {
1114                         err = EEXIST;
1115                         break ;
1116                 }
1117                 crit_enter();
1118                 err = bdginit();
1119                 crit_exit();
1120                 break;
1121         case MOD_UNLOAD:
1122 #if !defined(KLD_MODULE)
1123                 printf("bridge statically compiled, cannot unload\n");
1124                 err = EINVAL ;
1125 #else
1126                 crit_enter();
1127                 do_bridge = 0;
1128                 bridge_in_ptr = NULL;
1129                 bdg_forward_ptr = NULL;
1130                 bdgtakeifaces_ptr = NULL;
1131                 callout_stop(&bdg_timeout_h);
1132                 bridge_off();
1133                 if (clusters)
1134                     free(clusters, M_IFADDR);
1135                 free(ifp2sc, M_IFADDR);
1136                 ifp2sc = NULL ;
1137                 crit_exit();
1138 #endif
1139                 break;
1140         default:
1141                 err = EINVAL ;
1142                 break;
1143         }
1144         return err;
1145 }
1146
1147 static moduledata_t bridge_mod = {
1148         "bridge",
1149         bridge_modevent,
1150         0
1151 };
1152
1153 DECLARE_MODULE(bridge, bridge_mod, SI_SUB_PSEUDO, SI_ORDER_ANY);
1154 MODULE_VERSION(bridge, 1);