3 * Linux ethernet bridge
6 * Lennert Buytenhek <buytenh@gnu.org>
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version
11 * 2 of the License, or (at your option) any later version.
14 #include <linux/kernel.h>
15 #include <linux/init.h>
16 #include <linux/rculist.h>
17 #include <linux/spinlock.h>
18 #include <linux/times.h>
19 #include <linux/netdevice.h>
20 #include <linux/etherdevice.h>
21 #include <linux/jhash.h>
22 #include <linux/random.h>
23 #include <linux/slab.h>
24 #include <linux/atomic.h>
25 #include <asm/unaligned.h>
26 #include "br_private.h"
28 static struct kmem_cache
*br_fdb_cache __read_mostly
;
29 static int fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
30 const unsigned char *addr
);
31 static void fdb_notify(const struct net_bridge_fdb_entry
*, int);
33 static u32 fdb_salt __read_mostly
;
35 int __init
br_fdb_init(void)
37 br_fdb_cache
= kmem_cache_create("bridge_fdb_cache",
38 sizeof(struct net_bridge_fdb_entry
),
40 SLAB_HWCACHE_ALIGN
, NULL
);
44 get_random_bytes(&fdb_salt
, sizeof(fdb_salt
));
48 void br_fdb_fini(void)
50 kmem_cache_destroy(br_fdb_cache
);
54 /* if topology_changing then use forward_delay (default 15 sec)
55 * otherwise keep longer (default 5 minutes)
57 static inline unsigned long hold_time(const struct net_bridge
*br
)
59 return br
->topology_change
? br
->forward_delay
: br
->ageing_time
;
62 static inline int has_expired(const struct net_bridge
*br
,
63 const struct net_bridge_fdb_entry
*fdb
)
65 return !fdb
->is_static
&&
66 time_before_eq(fdb
->updated
+ hold_time(br
), jiffies
);
69 static inline int br_mac_hash(const unsigned char *mac
)
71 /* use 1 byte of OUI cnd 3 bytes of NIC */
72 u32 key
= get_unaligned((u32
*)(mac
+ 2));
73 return jhash_1word(key
, fdb_salt
) & (BR_HASH_SIZE
- 1);
76 static void fdb_rcu_free(struct rcu_head
*head
)
78 struct net_bridge_fdb_entry
*ent
79 = container_of(head
, struct net_bridge_fdb_entry
, rcu
);
80 kmem_cache_free(br_fdb_cache
, ent
);
83 static inline void fdb_delete(struct net_bridge_fdb_entry
*f
)
85 fdb_notify(f
, RTM_DELNEIGH
);
86 hlist_del_rcu(&f
->hlist
);
87 call_rcu(&f
->rcu
, fdb_rcu_free
);
90 void br_fdb_changeaddr(struct net_bridge_port
*p
, const unsigned char *newaddr
)
92 struct net_bridge
*br
= p
->br
;
95 spin_lock_bh(&br
->hash_lock
);
97 /* Search all chains since old address/hash is unknown */
98 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
100 hlist_for_each(h
, &br
->hash
[i
]) {
101 struct net_bridge_fdb_entry
*f
;
103 f
= hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
104 if (f
->dst
== p
&& f
->is_local
) {
105 /* maybe another port has same hw addr? */
106 struct net_bridge_port
*op
;
107 list_for_each_entry(op
, &br
->port_list
, list
) {
109 !compare_ether_addr(op
->dev
->dev_addr
,
123 /* insert new address, may fail if invalid address or dup. */
124 fdb_insert(br
, p
, newaddr
);
126 spin_unlock_bh(&br
->hash_lock
);
129 void br_fdb_cleanup(unsigned long _data
)
131 struct net_bridge
*br
= (struct net_bridge
*)_data
;
132 unsigned long delay
= hold_time(br
);
133 unsigned long next_timer
= jiffies
+ br
->ageing_time
;
136 spin_lock_bh(&br
->hash_lock
);
137 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
138 struct net_bridge_fdb_entry
*f
;
139 struct hlist_node
*h
, *n
;
141 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
142 unsigned long this_timer
;
145 this_timer
= f
->updated
+ delay
;
146 if (time_before_eq(this_timer
, jiffies
))
148 else if (time_before(this_timer
, next_timer
))
149 next_timer
= this_timer
;
152 spin_unlock_bh(&br
->hash_lock
);
154 mod_timer(&br
->gc_timer
, round_jiffies_up(next_timer
));
157 /* Completely flush all dynamic entries in forwarding database.*/
158 void br_fdb_flush(struct net_bridge
*br
)
162 spin_lock_bh(&br
->hash_lock
);
163 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
164 struct net_bridge_fdb_entry
*f
;
165 struct hlist_node
*h
, *n
;
166 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
171 spin_unlock_bh(&br
->hash_lock
);
174 /* Flush all entries referring to a specific port.
175 * if do_all is set also flush static entries
177 void br_fdb_delete_by_port(struct net_bridge
*br
,
178 const struct net_bridge_port
*p
,
183 spin_lock_bh(&br
->hash_lock
);
184 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
185 struct hlist_node
*h
, *g
;
187 hlist_for_each_safe(h
, g
, &br
->hash
[i
]) {
188 struct net_bridge_fdb_entry
*f
189 = hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
193 if (f
->is_static
&& !do_all
)
196 * if multiple ports all have the same device address
197 * then when one port is deleted, assign
198 * the local entry to other port
201 struct net_bridge_port
*op
;
202 list_for_each_entry(op
, &br
->port_list
, list
) {
204 !compare_ether_addr(op
->dev
->dev_addr
,
216 spin_unlock_bh(&br
->hash_lock
);
219 /* No locking or refcounting, assumes caller has rcu_read_lock */
220 struct net_bridge_fdb_entry
*__br_fdb_get(struct net_bridge
*br
,
221 const unsigned char *addr
)
223 struct hlist_node
*h
;
224 struct net_bridge_fdb_entry
*fdb
;
226 hlist_for_each_entry_rcu(fdb
, h
, &br
->hash
[br_mac_hash(addr
)], hlist
) {
227 if (!compare_ether_addr(fdb
->addr
.addr
, addr
)) {
228 if (unlikely(has_expired(br
, fdb
)))
237 #if defined(CONFIG_ATM_LANE) || defined(CONFIG_ATM_LANE_MODULE)
238 /* Interface used by ATM LANE hook to test
239 * if an addr is on some other bridge port */
240 int br_fdb_test_addr(struct net_device
*dev
, unsigned char *addr
)
242 struct net_bridge_fdb_entry
*fdb
;
243 struct net_bridge_port
*port
;
247 port
= br_port_get_rcu(dev
);
251 fdb
= __br_fdb_get(port
->br
, addr
);
252 ret
= fdb
&& fdb
->dst
->dev
!= dev
&&
253 fdb
->dst
->state
== BR_STATE_FORWARDING
;
259 #endif /* CONFIG_ATM_LANE */
262 * Fill buffer with forwarding table records in
265 int br_fdb_fillbuf(struct net_bridge
*br
, void *buf
,
266 unsigned long maxnum
, unsigned long skip
)
268 struct __fdb_entry
*fe
= buf
;
270 struct hlist_node
*h
;
271 struct net_bridge_fdb_entry
*f
;
273 memset(buf
, 0, maxnum
*sizeof(struct __fdb_entry
));
276 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
277 hlist_for_each_entry_rcu(f
, h
, &br
->hash
[i
], hlist
) {
281 if (has_expired(br
, f
))
289 /* convert from internal format to API */
290 memcpy(fe
->mac_addr
, f
->addr
.addr
, ETH_ALEN
);
292 /* due to ABI compat need to split into hi/lo */
293 fe
->port_no
= f
->dst
->port_no
;
294 fe
->port_hi
= f
->dst
->port_no
>> 8;
296 fe
->is_local
= f
->is_local
;
298 fe
->ageing_timer_value
= jiffies_to_clock_t(jiffies
- f
->updated
);
310 static struct net_bridge_fdb_entry
*fdb_find(struct hlist_head
*head
,
311 const unsigned char *addr
)
313 struct hlist_node
*h
;
314 struct net_bridge_fdb_entry
*fdb
;
316 hlist_for_each_entry(fdb
, h
, head
, hlist
) {
317 if (!compare_ether_addr(fdb
->addr
.addr
, addr
))
323 static struct net_bridge_fdb_entry
*fdb_find_rcu(struct hlist_head
*head
,
324 const unsigned char *addr
)
326 struct hlist_node
*h
;
327 struct net_bridge_fdb_entry
*fdb
;
329 hlist_for_each_entry_rcu(fdb
, h
, head
, hlist
) {
330 if (!compare_ether_addr(fdb
->addr
.addr
, addr
))
336 static struct net_bridge_fdb_entry
*fdb_create(struct hlist_head
*head
,
337 struct net_bridge_port
*source
,
338 const unsigned char *addr
)
340 struct net_bridge_fdb_entry
*fdb
;
342 fdb
= kmem_cache_alloc(br_fdb_cache
, GFP_ATOMIC
);
344 memcpy(fdb
->addr
.addr
, addr
, ETH_ALEN
);
348 fdb
->updated
= fdb
->used
= jiffies
;
349 hlist_add_head_rcu(&fdb
->hlist
, head
);
350 fdb_notify(fdb
, RTM_NEWNEIGH
);
355 static int fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
356 const unsigned char *addr
)
358 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
359 struct net_bridge_fdb_entry
*fdb
;
361 if (!is_valid_ether_addr(addr
))
364 fdb
= fdb_find(head
, addr
);
366 /* it is okay to have multiple ports with same
367 * address, just use the first one.
371 br_warn(br
, "adding interface %s with same address "
372 "as a received packet\n",
377 fdb
= fdb_create(head
, source
, addr
);
381 fdb
->is_local
= fdb
->is_static
= 1;
385 /* Add entry for local address of interface */
386 int br_fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
387 const unsigned char *addr
)
391 spin_lock_bh(&br
->hash_lock
);
392 ret
= fdb_insert(br
, source
, addr
);
393 spin_unlock_bh(&br
->hash_lock
);
397 void br_fdb_update(struct net_bridge
*br
, struct net_bridge_port
*source
,
398 const unsigned char *addr
)
400 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
401 struct net_bridge_fdb_entry
*fdb
;
403 /* some users want to always flood. */
404 if (hold_time(br
) == 0)
407 /* ignore packets unless we are using this port */
408 if (!(source
->state
== BR_STATE_LEARNING
||
409 source
->state
== BR_STATE_FORWARDING
))
412 fdb
= fdb_find_rcu(head
, addr
);
414 /* attempt to update an entry for a local interface */
415 if (unlikely(fdb
->is_local
)) {
417 br_warn(br
, "received packet on %s with "
418 "own address as source address\n",
421 /* fastpath: update of existing entry */
423 fdb
->updated
= jiffies
;
426 spin_lock(&br
->hash_lock
);
427 if (likely(!fdb_find(head
, addr
)))
428 fdb_create(head
, source
, addr
);
430 /* else we lose race and someone else inserts
431 * it first, don't bother updating
433 spin_unlock(&br
->hash_lock
);
437 static int fdb_to_nud(const struct net_bridge_fdb_entry
*fdb
)
440 return NUD_PERMANENT
;
441 else if (fdb
->is_static
)
443 else if (has_expired(fdb
->dst
->br
, fdb
))
446 return NUD_REACHABLE
;
449 static int fdb_fill_info(struct sk_buff
*skb
,
450 const struct net_bridge_fdb_entry
*fdb
,
451 u32 pid
, u32 seq
, int type
, unsigned int flags
)
453 unsigned long now
= jiffies
;
454 struct nda_cacheinfo ci
;
455 struct nlmsghdr
*nlh
;
458 nlh
= nlmsg_put(skb
, pid
, seq
, type
, sizeof(*ndm
), flags
);
463 ndm
= nlmsg_data(nlh
);
464 ndm
->ndm_family
= AF_BRIDGE
;
469 ndm
->ndm_ifindex
= fdb
->dst
->dev
->ifindex
;
470 ndm
->ndm_state
= fdb_to_nud(fdb
);
472 NLA_PUT(skb
, NDA_LLADDR
, ETH_ALEN
, &fdb
->addr
);
474 ci
.ndm_used
= jiffies_to_clock_t(now
- fdb
->used
);
475 ci
.ndm_confirmed
= 0;
476 ci
.ndm_updated
= jiffies_to_clock_t(now
- fdb
->updated
);
478 NLA_PUT(skb
, NDA_CACHEINFO
, sizeof(ci
), &ci
);
480 return nlmsg_end(skb
, nlh
);
483 nlmsg_cancel(skb
, nlh
);
487 static inline size_t fdb_nlmsg_size(void)
489 return NLMSG_ALIGN(sizeof(struct ndmsg
))
490 + nla_total_size(ETH_ALEN
) /* NDA_LLADDR */
491 + nla_total_size(sizeof(struct nda_cacheinfo
));
494 static void fdb_notify(const struct net_bridge_fdb_entry
*fdb
, int type
)
496 struct net
*net
= dev_net(fdb
->dst
->dev
);
500 skb
= nlmsg_new(fdb_nlmsg_size(), GFP_ATOMIC
);
504 err
= fdb_fill_info(skb
, fdb
, 0, 0, type
, 0);
506 /* -EMSGSIZE implies BUG in fdb_nlmsg_size() */
507 WARN_ON(err
== -EMSGSIZE
);
511 rtnl_notify(skb
, net
, 0, RTNLGRP_NEIGH
, NULL
, GFP_ATOMIC
);
515 rtnl_set_sk_err(net
, RTNLGRP_NEIGH
, err
);
518 /* Dump information about entries, in response to GETNEIGH */
519 int br_fdb_dump(struct sk_buff
*skb
, struct netlink_callback
*cb
)
521 struct net
*net
= sock_net(skb
->sk
);
522 struct net_device
*dev
;
526 for_each_netdev_rcu(net
, dev
) {
527 struct net_bridge
*br
= netdev_priv(dev
);
530 if (!(dev
->priv_flags
& IFF_EBRIDGE
))
533 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
534 struct hlist_node
*h
;
535 struct net_bridge_fdb_entry
*f
;
537 hlist_for_each_entry_rcu(f
, h
, &br
->hash
[i
], hlist
) {
538 if (idx
< cb
->args
[0])
541 if (fdb_fill_info(skb
, f
,
542 NETLINK_CB(cb
->skb
).pid
,
559 /* Create new static fdb entry */
560 static int fdb_add_entry(struct net_bridge_port
*source
, const __u8
*addr
,
563 struct net_bridge
*br
= source
->br
;
564 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
565 struct net_bridge_fdb_entry
*fdb
;
567 fdb
= fdb_find(head
, addr
);
571 fdb
= fdb_create(head
, source
, addr
);
575 if (state
& NUD_PERMANENT
)
576 fdb
->is_local
= fdb
->is_static
= 1;
577 else if (state
& NUD_NOARP
)
582 /* Add new permanent fdb entry with RTM_NEWNEIGH */
583 int br_fdb_add(struct sk_buff
*skb
, struct nlmsghdr
*nlh
, void *arg
)
585 struct net
*net
= sock_net(skb
->sk
);
587 struct nlattr
*tb
[NDA_MAX
+1];
588 struct net_device
*dev
;
589 struct net_bridge_port
*p
;
594 err
= nlmsg_parse(nlh
, sizeof(*ndm
), tb
, NDA_MAX
, NULL
);
598 ndm
= nlmsg_data(nlh
);
599 if (ndm
->ndm_ifindex
== 0) {
600 pr_info("bridge: RTM_NEWNEIGH with invalid ifindex\n");
604 dev
= __dev_get_by_index(net
, ndm
->ndm_ifindex
);
606 pr_info("bridge: RTM_NEWNEIGH with unknown ifindex\n");
610 if (!tb
[NDA_LLADDR
] || nla_len(tb
[NDA_LLADDR
]) != ETH_ALEN
) {
611 pr_info("bridge: RTM_NEWNEIGH with invalid address\n");
615 addr
= nla_data(tb
[NDA_LLADDR
]);
616 if (!is_valid_ether_addr(addr
)) {
617 pr_info("bridge: RTM_NEWNEIGH with invalid ether address\n");
621 p
= br_port_get_rtnl(dev
);
623 pr_info("bridge: RTM_NEWNEIGH %s not a bridge port\n",
628 spin_lock_bh(&p
->br
->hash_lock
);
629 err
= fdb_add_entry(p
, addr
, ndm
->ndm_state
);
630 spin_unlock_bh(&p
->br
->hash_lock
);
635 static int fdb_delete_by_addr(struct net_bridge_port
*p
, const u8
*addr
)
637 struct net_bridge
*br
= p
->br
;
638 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
639 struct net_bridge_fdb_entry
*fdb
;
641 fdb
= fdb_find(head
, addr
);
649 /* Remove neighbor entry with RTM_DELNEIGH */
650 int br_fdb_delete(struct sk_buff
*skb
, struct nlmsghdr
*nlh
, void *arg
)
652 struct net
*net
= sock_net(skb
->sk
);
654 struct net_bridge_port
*p
;
655 struct nlattr
*llattr
;
657 struct net_device
*dev
;
661 if (nlmsg_len(nlh
) < sizeof(*ndm
))
664 ndm
= nlmsg_data(nlh
);
665 if (ndm
->ndm_ifindex
== 0) {
666 pr_info("bridge: RTM_DELNEIGH with invalid ifindex\n");
670 dev
= __dev_get_by_index(net
, ndm
->ndm_ifindex
);
672 pr_info("bridge: RTM_DELNEIGH with unknown ifindex\n");
676 llattr
= nlmsg_find_attr(nlh
, sizeof(*ndm
), NDA_LLADDR
);
677 if (llattr
== NULL
|| nla_len(llattr
) != ETH_ALEN
) {
678 pr_info("bridge: RTM_DELNEIGH with invalid address\n");
682 addr
= nla_data(llattr
);
684 p
= br_port_get_rtnl(dev
);
686 pr_info("bridge: RTM_DELNEIGH %s not a bridge port\n",
691 spin_lock_bh(&p
->br
->hash_lock
);
692 err
= fdb_delete_by_addr(p
, addr
);
693 spin_unlock_bh(&p
->br
->hash_lock
);