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 <asm/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
);
32 static u32 fdb_salt __read_mostly
;
34 int __init
br_fdb_init(void)
36 br_fdb_cache
= kmem_cache_create("bridge_fdb_cache",
37 sizeof(struct net_bridge_fdb_entry
),
39 SLAB_HWCACHE_ALIGN
, NULL
);
43 get_random_bytes(&fdb_salt
, sizeof(fdb_salt
));
47 void br_fdb_fini(void)
49 kmem_cache_destroy(br_fdb_cache
);
53 /* if topology_changing then use forward_delay (default 15 sec)
54 * otherwise keep longer (default 5 minutes)
56 static inline unsigned long hold_time(const struct net_bridge
*br
)
58 return br
->topology_change
? br
->forward_delay
: br
->ageing_time
;
61 static inline int has_expired(const struct net_bridge
*br
,
62 const struct net_bridge_fdb_entry
*fdb
)
64 return !fdb
->is_static
&&
65 time_before_eq(fdb
->updated
+ hold_time(br
), jiffies
);
68 static inline int br_mac_hash(const unsigned char *mac
)
70 /* use 1 byte of OUI cnd 3 bytes of NIC */
71 u32 key
= get_unaligned((u32
*)(mac
+ 2));
72 return jhash_1word(key
, fdb_salt
) & (BR_HASH_SIZE
- 1);
75 static void fdb_rcu_free(struct rcu_head
*head
)
77 struct net_bridge_fdb_entry
*ent
78 = container_of(head
, struct net_bridge_fdb_entry
, rcu
);
79 kmem_cache_free(br_fdb_cache
, ent
);
82 static inline void fdb_delete(struct net_bridge_fdb_entry
*f
)
84 hlist_del_rcu(&f
->hlist
);
85 call_rcu(&f
->rcu
, fdb_rcu_free
);
88 void br_fdb_changeaddr(struct net_bridge_port
*p
, const unsigned char *newaddr
)
90 struct net_bridge
*br
= p
->br
;
93 spin_lock_bh(&br
->hash_lock
);
95 /* Search all chains since old address/hash is unknown */
96 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
98 hlist_for_each(h
, &br
->hash
[i
]) {
99 struct net_bridge_fdb_entry
*f
;
101 f
= hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
102 if (f
->dst
== p
&& f
->is_local
) {
103 /* maybe another port has same hw addr? */
104 struct net_bridge_port
*op
;
105 list_for_each_entry(op
, &br
->port_list
, list
) {
107 !compare_ether_addr(op
->dev
->dev_addr
,
121 /* insert new address, may fail if invalid address or dup. */
122 fdb_insert(br
, p
, newaddr
);
124 spin_unlock_bh(&br
->hash_lock
);
127 void br_fdb_cleanup(unsigned long _data
)
129 struct net_bridge
*br
= (struct net_bridge
*)_data
;
130 unsigned long delay
= hold_time(br
);
131 unsigned long next_timer
= jiffies
+ br
->ageing_time
;
134 spin_lock_bh(&br
->hash_lock
);
135 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
136 struct net_bridge_fdb_entry
*f
;
137 struct hlist_node
*h
, *n
;
139 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
140 unsigned long this_timer
;
143 this_timer
= f
->updated
+ delay
;
144 if (time_before_eq(this_timer
, jiffies
))
146 else if (time_before(this_timer
, next_timer
))
147 next_timer
= this_timer
;
150 spin_unlock_bh(&br
->hash_lock
);
152 mod_timer(&br
->gc_timer
, round_jiffies_up(next_timer
));
155 /* Completely flush all dynamic entries in forwarding database.*/
156 void br_fdb_flush(struct net_bridge
*br
)
160 spin_lock_bh(&br
->hash_lock
);
161 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
162 struct net_bridge_fdb_entry
*f
;
163 struct hlist_node
*h
, *n
;
164 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
169 spin_unlock_bh(&br
->hash_lock
);
172 /* Flush all entries refering to a specific port.
173 * if do_all is set also flush static entries
175 void br_fdb_delete_by_port(struct net_bridge
*br
,
176 const struct net_bridge_port
*p
,
181 spin_lock_bh(&br
->hash_lock
);
182 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
183 struct hlist_node
*h
, *g
;
185 hlist_for_each_safe(h
, g
, &br
->hash
[i
]) {
186 struct net_bridge_fdb_entry
*f
187 = hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
191 if (f
->is_static
&& !do_all
)
194 * if multiple ports all have the same device address
195 * then when one port is deleted, assign
196 * the local entry to other port
199 struct net_bridge_port
*op
;
200 list_for_each_entry(op
, &br
->port_list
, list
) {
202 !compare_ether_addr(op
->dev
->dev_addr
,
214 spin_unlock_bh(&br
->hash_lock
);
217 /* No locking or refcounting, assumes caller has rcu_read_lock */
218 struct net_bridge_fdb_entry
*__br_fdb_get(struct net_bridge
*br
,
219 const unsigned char *addr
)
221 struct hlist_node
*h
;
222 struct net_bridge_fdb_entry
*fdb
;
224 hlist_for_each_entry_rcu(fdb
, h
, &br
->hash
[br_mac_hash(addr
)], hlist
) {
225 if (!compare_ether_addr(fdb
->addr
.addr
, addr
)) {
226 if (unlikely(has_expired(br
, fdb
)))
235 #if defined(CONFIG_ATM_LANE) || defined(CONFIG_ATM_LANE_MODULE)
236 /* Interface used by ATM LANE hook to test
237 * if an addr is on some other bridge port */
238 int br_fdb_test_addr(struct net_device
*dev
, unsigned char *addr
)
240 struct net_bridge_fdb_entry
*fdb
;
241 struct net_bridge_port
*port
;
245 port
= br_port_get_rcu(dev
);
249 fdb
= __br_fdb_get(port
->br
, addr
);
250 ret
= fdb
&& fdb
->dst
->dev
!= dev
&&
251 fdb
->dst
->state
== BR_STATE_FORWARDING
;
257 #endif /* CONFIG_ATM_LANE */
260 * Fill buffer with forwarding table records in
263 int br_fdb_fillbuf(struct net_bridge
*br
, void *buf
,
264 unsigned long maxnum
, unsigned long skip
)
266 struct __fdb_entry
*fe
= buf
;
268 struct hlist_node
*h
;
269 struct net_bridge_fdb_entry
*f
;
271 memset(buf
, 0, maxnum
*sizeof(struct __fdb_entry
));
274 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
275 hlist_for_each_entry_rcu(f
, h
, &br
->hash
[i
], hlist
) {
279 if (has_expired(br
, f
))
287 /* convert from internal format to API */
288 memcpy(fe
->mac_addr
, f
->addr
.addr
, ETH_ALEN
);
290 /* due to ABI compat need to split into hi/lo */
291 fe
->port_no
= f
->dst
->port_no
;
292 fe
->port_hi
= f
->dst
->port_no
>> 8;
294 fe
->is_local
= f
->is_local
;
296 fe
->ageing_timer_value
= jiffies_to_clock_t(jiffies
- f
->updated
);
308 static struct net_bridge_fdb_entry
*fdb_find(struct hlist_head
*head
,
309 const unsigned char *addr
)
311 struct hlist_node
*h
;
312 struct net_bridge_fdb_entry
*fdb
;
314 hlist_for_each_entry(fdb
, h
, head
, hlist
) {
315 if (!compare_ether_addr(fdb
->addr
.addr
, addr
))
321 static struct net_bridge_fdb_entry
*fdb_find_rcu(struct hlist_head
*head
,
322 const unsigned char *addr
)
324 struct hlist_node
*h
;
325 struct net_bridge_fdb_entry
*fdb
;
327 hlist_for_each_entry_rcu(fdb
, h
, head
, hlist
) {
328 if (!compare_ether_addr(fdb
->addr
.addr
, addr
))
334 static struct net_bridge_fdb_entry
*fdb_create(struct hlist_head
*head
,
335 struct net_bridge_port
*source
,
336 const unsigned char *addr
)
338 struct net_bridge_fdb_entry
*fdb
;
340 fdb
= kmem_cache_alloc(br_fdb_cache
, GFP_ATOMIC
);
342 memcpy(fdb
->addr
.addr
, addr
, ETH_ALEN
);
346 fdb
->updated
= fdb
->used
= jiffies
;
347 hlist_add_head_rcu(&fdb
->hlist
, head
);
352 static int fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
353 const unsigned char *addr
)
355 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
356 struct net_bridge_fdb_entry
*fdb
;
358 if (!is_valid_ether_addr(addr
))
361 fdb
= fdb_find(head
, addr
);
363 /* it is okay to have multiple ports with same
364 * address, just use the first one.
368 br_warn(br
, "adding interface %s with same address "
369 "as a received packet\n",
374 fdb
= fdb_create(head
, source
, addr
);
378 fdb
->is_local
= fdb
->is_static
= 1;
382 /* Add entry for local address of interface */
383 int br_fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
384 const unsigned char *addr
)
388 spin_lock_bh(&br
->hash_lock
);
389 ret
= fdb_insert(br
, source
, addr
);
390 spin_unlock_bh(&br
->hash_lock
);
394 void br_fdb_update(struct net_bridge
*br
, struct net_bridge_port
*source
,
395 const unsigned char *addr
)
397 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
398 struct net_bridge_fdb_entry
*fdb
;
400 /* some users want to always flood. */
401 if (hold_time(br
) == 0)
404 /* ignore packets unless we are using this port */
405 if (!(source
->state
== BR_STATE_LEARNING
||
406 source
->state
== BR_STATE_FORWARDING
))
409 fdb
= fdb_find_rcu(head
, addr
);
411 /* attempt to update an entry for a local interface */
412 if (unlikely(fdb
->is_local
)) {
414 br_warn(br
, "received packet on %s with "
415 "own address as source address\n",
418 /* fastpath: update of existing entry */
420 fdb
->updated
= jiffies
;
423 spin_lock(&br
->hash_lock
);
424 if (likely(!fdb_find(head
, addr
)))
425 fdb_create(head
, source
, addr
);
427 /* else we lose race and someone else inserts
428 * it first, don't bother updating
430 spin_unlock(&br
->hash_lock
);