blob: dd5a5d5fb280537f59cd7a0f5c29db18aae32659 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Forwarding database
3 * Linux ethernet bridge
4 *
5 * Authors:
6 * Lennert Buytenhek <buytenh@gnu.org>
7 *
8 * $Id: br_fdb.c,v 1.6 2002/01/17 00:57:07 davem Exp $
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version
13 * 2 of the License, or (at your option) any later version.
14 */
15
16#include <linux/kernel.h>
17#include <linux/init.h>
18#include <linux/spinlock.h>
19#include <linux/times.h>
20#include <linux/netdevice.h>
21#include <linux/etherdevice.h>
22#include <linux/jhash.h>
Stephen Hemminger3f890922007-03-21 13:42:33 -070023#include <linux/random.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include <asm/atomic.h>
Stephen Hemminger3f890922007-03-21 13:42:33 -070025#include <asm/unaligned.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include "br_private.h"
27
Christoph Lametere18b8902006-12-06 20:33:20 -080028static struct kmem_cache *br_fdb_cache __read_mostly;
Linus Torvalds1da177e2005-04-16 15:20:36 -070029static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
30 const unsigned char *addr);
31
Stephen Hemminger3f890922007-03-21 13:42:33 -070032static u32 fdb_salt __read_mostly;
33
Linus Torvalds1da177e2005-04-16 15:20:36 -070034void __init br_fdb_init(void)
35{
36 br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
37 sizeof(struct net_bridge_fdb_entry),
38 0,
39 SLAB_HWCACHE_ALIGN, NULL, NULL);
Stephen Hemminger3f890922007-03-21 13:42:33 -070040 get_random_bytes(&fdb_salt, sizeof(fdb_salt));
Linus Torvalds1da177e2005-04-16 15:20:36 -070041}
42
43void __exit br_fdb_fini(void)
44{
45 kmem_cache_destroy(br_fdb_cache);
46}
47
48
49/* if topology_changing then use forward_delay (default 15 sec)
50 * otherwise keep longer (default 5 minutes)
51 */
Stephen Hemminger3f890922007-03-21 13:42:33 -070052static inline unsigned long hold_time(const struct net_bridge *br)
Linus Torvalds1da177e2005-04-16 15:20:36 -070053{
54 return br->topology_change ? br->forward_delay : br->ageing_time;
55}
56
Stephen Hemminger3f890922007-03-21 13:42:33 -070057static inline int has_expired(const struct net_bridge *br,
Linus Torvalds1da177e2005-04-16 15:20:36 -070058 const struct net_bridge_fdb_entry *fdb)
59{
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090060 return !fdb->is_static
Linus Torvalds1da177e2005-04-16 15:20:36 -070061 && time_before_eq(fdb->ageing_timer + hold_time(br), jiffies);
62}
63
Stephen Hemminger3f890922007-03-21 13:42:33 -070064static inline int br_mac_hash(const unsigned char *mac)
Linus Torvalds1da177e2005-04-16 15:20:36 -070065{
Stephen Hemminger3f890922007-03-21 13:42:33 -070066 /* use 1 byte of OUI cnd 3 bytes of NIC */
67 u32 key = get_unaligned((u32 *)(mac + 2));
68 return jhash_1word(key, fdb_salt) & (BR_HASH_SIZE - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -070069}
70
Stephen Hemminger3f890922007-03-21 13:42:33 -070071static inline void fdb_delete(struct net_bridge_fdb_entry *f)
Linus Torvalds1da177e2005-04-16 15:20:36 -070072{
73 hlist_del_rcu(&f->hlist);
74 br_fdb_put(f);
75}
76
77void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr)
78{
79 struct net_bridge *br = p->br;
80 int i;
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090081
Linus Torvalds1da177e2005-04-16 15:20:36 -070082 spin_lock_bh(&br->hash_lock);
83
84 /* Search all chains since old address/hash is unknown */
85 for (i = 0; i < BR_HASH_SIZE; i++) {
86 struct hlist_node *h;
87 hlist_for_each(h, &br->hash[i]) {
88 struct net_bridge_fdb_entry *f;
89
90 f = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
91 if (f->dst == p && f->is_local) {
92 /* maybe another port has same hw addr? */
93 struct net_bridge_port *op;
94 list_for_each_entry(op, &br->port_list, list) {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +090095 if (op != p &&
Stephen Hemminger6ede2462005-10-25 15:04:59 -070096 !compare_ether_addr(op->dev->dev_addr,
97 f->addr.addr)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 f->dst = op;
99 goto insert;
100 }
101 }
102
103 /* delete old one */
104 fdb_delete(f);
105 goto insert;
106 }
107 }
108 }
109 insert:
110 /* insert new address, may fail if invalid address or dup. */
111 fdb_insert(br, p, newaddr);
112
113 spin_unlock_bh(&br->hash_lock);
114}
115
116void br_fdb_cleanup(unsigned long _data)
117{
118 struct net_bridge *br = (struct net_bridge *)_data;
119 unsigned long delay = hold_time(br);
120 int i;
121
122 spin_lock_bh(&br->hash_lock);
123 for (i = 0; i < BR_HASH_SIZE; i++) {
124 struct net_bridge_fdb_entry *f;
125 struct hlist_node *h, *n;
126
127 hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900128 if (!f->is_static &&
129 time_before_eq(f->ageing_timer + delay, jiffies))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700130 fdb_delete(f);
131 }
132 }
133 spin_unlock_bh(&br->hash_lock);
134
135 mod_timer(&br->gc_timer, jiffies + HZ/10);
136}
137
Stephen Hemminger1a620692006-10-12 14:45:38 -0700138
139void br_fdb_delete_by_port(struct net_bridge *br,
140 const struct net_bridge_port *p,
141 int do_all)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700142{
143 int i;
144
145 spin_lock_bh(&br->hash_lock);
146 for (i = 0; i < BR_HASH_SIZE; i++) {
147 struct hlist_node *h, *g;
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900148
Linus Torvalds1da177e2005-04-16 15:20:36 -0700149 hlist_for_each_safe(h, g, &br->hash[i]) {
150 struct net_bridge_fdb_entry *f
151 = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900152 if (f->dst != p)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700153 continue;
154
Stephen Hemminger1a620692006-10-12 14:45:38 -0700155 if (f->is_static && !do_all)
156 continue;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157 /*
158 * if multiple ports all have the same device address
159 * then when one port is deleted, assign
160 * the local entry to other port
161 */
162 if (f->is_local) {
163 struct net_bridge_port *op;
164 list_for_each_entry(op, &br->port_list, list) {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900165 if (op != p &&
Stephen Hemminger6ede2462005-10-25 15:04:59 -0700166 !compare_ether_addr(op->dev->dev_addr,
167 f->addr.addr)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168 f->dst = op;
169 goto skip_delete;
170 }
171 }
172 }
173
174 fdb_delete(f);
175 skip_delete: ;
176 }
177 }
178 spin_unlock_bh(&br->hash_lock);
179}
180
181/* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */
182struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
183 const unsigned char *addr)
184{
185 struct hlist_node *h;
186 struct net_bridge_fdb_entry *fdb;
187
188 hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
Stephen Hemminger6ede2462005-10-25 15:04:59 -0700189 if (!compare_ether_addr(fdb->addr.addr, addr)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700190 if (unlikely(has_expired(br, fdb)))
191 break;
192 return fdb;
193 }
194 }
195
196 return NULL;
197}
198
199/* Interface used by ATM hook that keeps a ref count */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900200struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 unsigned char *addr)
202{
203 struct net_bridge_fdb_entry *fdb;
204
205 rcu_read_lock();
206 fdb = __br_fdb_get(br, addr);
Patrick McHardyb19cbe22007-03-22 12:25:20 -0700207 if (fdb && !atomic_inc_not_zero(&fdb->use_count))
208 fdb = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209 rcu_read_unlock();
210 return fdb;
211}
212
213static void fdb_rcu_free(struct rcu_head *head)
214{
215 struct net_bridge_fdb_entry *ent
216 = container_of(head, struct net_bridge_fdb_entry, rcu);
217 kmem_cache_free(br_fdb_cache, ent);
218}
219
220/* Set entry up for deletion with RCU */
221void br_fdb_put(struct net_bridge_fdb_entry *ent)
222{
223 if (atomic_dec_and_test(&ent->use_count))
224 call_rcu(&ent->rcu, fdb_rcu_free);
225}
226
227/*
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900228 * Fill buffer with forwarding table records in
Linus Torvalds1da177e2005-04-16 15:20:36 -0700229 * the API format.
230 */
231int br_fdb_fillbuf(struct net_bridge *br, void *buf,
232 unsigned long maxnum, unsigned long skip)
233{
234 struct __fdb_entry *fe = buf;
235 int i, num = 0;
236 struct hlist_node *h;
237 struct net_bridge_fdb_entry *f;
238
239 memset(buf, 0, maxnum*sizeof(struct __fdb_entry));
240
241 rcu_read_lock();
242 for (i = 0; i < BR_HASH_SIZE; i++) {
243 hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) {
244 if (num >= maxnum)
245 goto out;
246
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900247 if (has_expired(br, f))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248 continue;
249
250 if (skip) {
251 --skip;
252 continue;
253 }
254
255 /* convert from internal format to API */
256 memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN);
257 fe->port_no = f->dst->port_no;
258 fe->is_local = f->is_local;
259 if (!f->is_static)
260 fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer);
261 ++fe;
262 ++num;
263 }
264 }
265
266 out:
267 rcu_read_unlock();
268
269 return num;
270}
271
272static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
273 const unsigned char *addr)
274{
275 struct hlist_node *h;
276 struct net_bridge_fdb_entry *fdb;
277
278 hlist_for_each_entry_rcu(fdb, h, head, hlist) {
Stephen Hemminger6ede2462005-10-25 15:04:59 -0700279 if (!compare_ether_addr(fdb->addr.addr, addr))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700280 return fdb;
281 }
282 return NULL;
283}
284
285static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
286 struct net_bridge_port *source,
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900287 const unsigned char *addr,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700288 int is_local)
289{
290 struct net_bridge_fdb_entry *fdb;
291
292 fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
293 if (fdb) {
294 memcpy(fdb->addr.addr, addr, ETH_ALEN);
295 atomic_set(&fdb->use_count, 1);
296 hlist_add_head_rcu(&fdb->hlist, head);
297
298 fdb->dst = source;
299 fdb->is_local = is_local;
300 fdb->is_static = is_local;
301 fdb->ageing_timer = jiffies;
302 }
303 return fdb;
304}
305
306static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
307 const unsigned char *addr)
308{
309 struct hlist_head *head = &br->hash[br_mac_hash(addr)];
310 struct net_bridge_fdb_entry *fdb;
311
312 if (!is_valid_ether_addr(addr))
313 return -EINVAL;
314
315 fdb = fdb_find(head, addr);
316 if (fdb) {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900317 /* it is okay to have multiple ports with same
Linus Torvalds1da177e2005-04-16 15:20:36 -0700318 * address, just use the first one.
319 */
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900320 if (fdb->is_local)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700321 return 0;
322
323 printk(KERN_WARNING "%s adding interface with same address "
324 "as a received packet\n",
325 source->dev->name);
326 fdb_delete(fdb);
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900327 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328
329 if (!fdb_create(head, source, addr, 1))
330 return -ENOMEM;
331
332 return 0;
333}
334
335int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
336 const unsigned char *addr)
337{
338 int ret;
339
340 spin_lock_bh(&br->hash_lock);
341 ret = fdb_insert(br, source, addr);
342 spin_unlock_bh(&br->hash_lock);
343 return ret;
344}
345
346void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source,
347 const unsigned char *addr)
348{
349 struct hlist_head *head = &br->hash[br_mac_hash(addr)];
350 struct net_bridge_fdb_entry *fdb;
351
352 /* some users want to always flood. */
353 if (hold_time(br) == 0)
354 return;
355
Linus Torvalds1da177e2005-04-16 15:20:36 -0700356 fdb = fdb_find(head, addr);
357 if (likely(fdb)) {
358 /* attempt to update an entry for a local interface */
359 if (unlikely(fdb->is_local)) {
YOSHIFUJI Hideaki9d6f2292007-02-09 23:24:35 +0900360 if (net_ratelimit())
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361 printk(KERN_WARNING "%s: received packet with "
362 " own address as source address\n",
363 source->dev->name);
364 } else {
365 /* fastpath: update of existing entry */
366 fdb->dst = source;
367 fdb->ageing_timer = jiffies;
368 }
369 } else {
Stephen Hemmingerf8ae7372006-03-20 22:58:36 -0800370 spin_lock(&br->hash_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700371 if (!fdb_find(head, addr))
372 fdb_create(head, source, addr, 0);
373 /* else we lose race and someone else inserts
374 * it first, don't bother updating
375 */
Stephen Hemmingerf8ae7372006-03-20 22:58:36 -0800376 spin_unlock(&br->hash_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700378}