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/spinlock.h>
17 #include <linux/times.h>
18 #include <linux/netdevice.h>
19 #include <linux/etherdevice.h>
20 #include <linux/jhash.h>
21 #include <linux/random.h>
22 #include <asm/atomic.h>
23 #include <asm/unaligned.h>
24 #include "br_private.h"
26 static struct kmem_cache
*br_fdb_cache __read_mostly
;
27 static int fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
28 const unsigned char *addr
);
30 static u32 fdb_salt __read_mostly
;
32 int __init
br_fdb_init(void)
34 br_fdb_cache
= kmem_cache_create("bridge_fdb_cache",
35 sizeof(struct net_bridge_fdb_entry
),
37 SLAB_HWCACHE_ALIGN
, NULL
);
41 get_random_bytes(&fdb_salt
, sizeof(fdb_salt
));
45 void br_fdb_fini(void)
47 kmem_cache_destroy(br_fdb_cache
);
51 /* if topology_changing then use forward_delay (default 15 sec)
52 * otherwise keep longer (default 5 minutes)
54 static inline unsigned long hold_time(const struct net_bridge
*br
)
56 return br
->topology_change
? br
->forward_delay
: br
->ageing_time
;
59 static inline int has_expired(const struct net_bridge
*br
,
60 const struct net_bridge_fdb_entry
*fdb
)
62 return !fdb
->is_static
63 && time_before_eq(fdb
->ageing_timer
+ hold_time(br
), jiffies
);
66 static inline int br_mac_hash(const unsigned char *mac
)
68 /* use 1 byte of OUI cnd 3 bytes of NIC */
69 u32 key
= get_unaligned((u32
*)(mac
+ 2));
70 return jhash_1word(key
, fdb_salt
) & (BR_HASH_SIZE
- 1);
73 static inline void fdb_delete(struct net_bridge_fdb_entry
*f
)
75 hlist_del_rcu(&f
->hlist
);
79 void br_fdb_changeaddr(struct net_bridge_port
*p
, const unsigned char *newaddr
)
81 struct net_bridge
*br
= p
->br
;
84 spin_lock_bh(&br
->hash_lock
);
86 /* Search all chains since old address/hash is unknown */
87 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
89 hlist_for_each(h
, &br
->hash
[i
]) {
90 struct net_bridge_fdb_entry
*f
;
92 f
= hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
93 if (f
->dst
== p
&& f
->is_local
) {
94 /* maybe another port has same hw addr? */
95 struct net_bridge_port
*op
;
96 list_for_each_entry(op
, &br
->port_list
, list
) {
98 !compare_ether_addr(op
->dev
->dev_addr
,
112 /* insert new address, may fail if invalid address or dup. */
113 fdb_insert(br
, p
, newaddr
);
115 spin_unlock_bh(&br
->hash_lock
);
118 void br_fdb_cleanup(unsigned long _data
)
120 struct net_bridge
*br
= (struct net_bridge
*)_data
;
121 unsigned long delay
= hold_time(br
);
122 unsigned long next_timer
= jiffies
+ br
->forward_delay
;
125 spin_lock_bh(&br
->hash_lock
);
126 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
127 struct net_bridge_fdb_entry
*f
;
128 struct hlist_node
*h
, *n
;
130 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
131 unsigned long this_timer
;
134 this_timer
= f
->ageing_timer
+ delay
;
135 if (time_before_eq(this_timer
, jiffies
))
137 else if (time_before(this_timer
, next_timer
))
138 next_timer
= this_timer
;
141 spin_unlock_bh(&br
->hash_lock
);
143 /* Add HZ/4 to ensure we round the jiffies upwards to be after the next
144 * timer, otherwise we might round down and will have no-op run. */
145 mod_timer(&br
->gc_timer
, round_jiffies(next_timer
+ HZ
/4));
148 /* Completely flush all dynamic entries in forwarding database.*/
149 void br_fdb_flush(struct net_bridge
*br
)
153 spin_lock_bh(&br
->hash_lock
);
154 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
155 struct net_bridge_fdb_entry
*f
;
156 struct hlist_node
*h
, *n
;
157 hlist_for_each_entry_safe(f
, h
, n
, &br
->hash
[i
], hlist
) {
162 spin_unlock_bh(&br
->hash_lock
);
165 /* Flush all entries refering to a specific port.
166 * if do_all is set also flush static entries
168 void br_fdb_delete_by_port(struct net_bridge
*br
,
169 const struct net_bridge_port
*p
,
174 spin_lock_bh(&br
->hash_lock
);
175 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
176 struct hlist_node
*h
, *g
;
178 hlist_for_each_safe(h
, g
, &br
->hash
[i
]) {
179 struct net_bridge_fdb_entry
*f
180 = hlist_entry(h
, struct net_bridge_fdb_entry
, hlist
);
184 if (f
->is_static
&& !do_all
)
187 * if multiple ports all have the same device address
188 * then when one port is deleted, assign
189 * the local entry to other port
192 struct net_bridge_port
*op
;
193 list_for_each_entry(op
, &br
->port_list
, list
) {
195 !compare_ether_addr(op
->dev
->dev_addr
,
207 spin_unlock_bh(&br
->hash_lock
);
210 /* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */
211 struct net_bridge_fdb_entry
*__br_fdb_get(struct net_bridge
*br
,
212 const unsigned char *addr
)
214 struct hlist_node
*h
;
215 struct net_bridge_fdb_entry
*fdb
;
217 hlist_for_each_entry_rcu(fdb
, h
, &br
->hash
[br_mac_hash(addr
)], hlist
) {
218 if (!compare_ether_addr(fdb
->addr
.addr
, addr
)) {
219 if (unlikely(has_expired(br
, fdb
)))
228 /* Interface used by ATM hook that keeps a ref count */
229 struct net_bridge_fdb_entry
*br_fdb_get(struct net_bridge
*br
,
232 struct net_bridge_fdb_entry
*fdb
;
235 fdb
= __br_fdb_get(br
, addr
);
236 if (fdb
&& !atomic_inc_not_zero(&fdb
->use_count
))
242 static void fdb_rcu_free(struct rcu_head
*head
)
244 struct net_bridge_fdb_entry
*ent
245 = container_of(head
, struct net_bridge_fdb_entry
, rcu
);
246 kmem_cache_free(br_fdb_cache
, ent
);
249 /* Set entry up for deletion with RCU */
250 void br_fdb_put(struct net_bridge_fdb_entry
*ent
)
252 if (atomic_dec_and_test(&ent
->use_count
))
253 call_rcu(&ent
->rcu
, fdb_rcu_free
);
257 * Fill buffer with forwarding table records in
260 int br_fdb_fillbuf(struct net_bridge
*br
, void *buf
,
261 unsigned long maxnum
, unsigned long skip
)
263 struct __fdb_entry
*fe
= buf
;
265 struct hlist_node
*h
;
266 struct net_bridge_fdb_entry
*f
;
268 memset(buf
, 0, maxnum
*sizeof(struct __fdb_entry
));
271 for (i
= 0; i
< BR_HASH_SIZE
; i
++) {
272 hlist_for_each_entry_rcu(f
, h
, &br
->hash
[i
], hlist
) {
276 if (has_expired(br
, f
))
284 /* convert from internal format to API */
285 memcpy(fe
->mac_addr
, f
->addr
.addr
, ETH_ALEN
);
287 /* due to ABI compat need to split into hi/lo */
288 fe
->port_no
= f
->dst
->port_no
;
289 fe
->port_hi
= f
->dst
->port_no
>> 8;
291 fe
->is_local
= f
->is_local
;
293 fe
->ageing_timer_value
= jiffies_to_clock_t(jiffies
- f
->ageing_timer
);
305 static inline struct net_bridge_fdb_entry
*fdb_find(struct hlist_head
*head
,
306 const unsigned char *addr
)
308 struct hlist_node
*h
;
309 struct net_bridge_fdb_entry
*fdb
;
311 hlist_for_each_entry_rcu(fdb
, h
, head
, hlist
) {
312 if (!compare_ether_addr(fdb
->addr
.addr
, addr
))
318 static struct net_bridge_fdb_entry
*fdb_create(struct hlist_head
*head
,
319 struct net_bridge_port
*source
,
320 const unsigned char *addr
,
323 struct net_bridge_fdb_entry
*fdb
;
325 fdb
= kmem_cache_alloc(br_fdb_cache
, GFP_ATOMIC
);
327 memcpy(fdb
->addr
.addr
, addr
, ETH_ALEN
);
328 atomic_set(&fdb
->use_count
, 1);
329 hlist_add_head_rcu(&fdb
->hlist
, head
);
332 fdb
->is_local
= is_local
;
333 fdb
->is_static
= is_local
;
334 fdb
->ageing_timer
= jiffies
;
339 static int fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
340 const unsigned char *addr
)
342 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
343 struct net_bridge_fdb_entry
*fdb
;
345 if (!is_valid_ether_addr(addr
))
348 fdb
= fdb_find(head
, addr
);
350 /* it is okay to have multiple ports with same
351 * address, just use the first one.
356 printk(KERN_WARNING
"%s adding interface with same address "
357 "as a received packet\n",
362 if (!fdb_create(head
, source
, addr
, 1))
368 int br_fdb_insert(struct net_bridge
*br
, struct net_bridge_port
*source
,
369 const unsigned char *addr
)
373 spin_lock_bh(&br
->hash_lock
);
374 ret
= fdb_insert(br
, source
, addr
);
375 spin_unlock_bh(&br
->hash_lock
);
379 void br_fdb_update(struct net_bridge
*br
, struct net_bridge_port
*source
,
380 const unsigned char *addr
)
382 struct hlist_head
*head
= &br
->hash
[br_mac_hash(addr
)];
383 struct net_bridge_fdb_entry
*fdb
;
385 /* some users want to always flood. */
386 if (hold_time(br
) == 0)
389 /* ignore packets unless we are using this port */
390 if (!(source
->state
== BR_STATE_LEARNING
||
391 source
->state
== BR_STATE_FORWARDING
))
394 fdb
= fdb_find(head
, addr
);
396 /* attempt to update an entry for a local interface */
397 if (unlikely(fdb
->is_local
)) {
399 printk(KERN_WARNING
"%s: received packet with "
400 " own address as source address\n",
403 /* fastpath: update of existing entry */
405 fdb
->ageing_timer
= jiffies
;
408 spin_lock(&br
->hash_lock
);
409 if (!fdb_find(head
, addr
))
410 fdb_create(head
, source
, addr
, 0);
411 /* else we lose race and someone else inserts
412 * it first, don't bother updating
414 spin_unlock(&br
->hash_lock
);