xref: /openbmc/linux/net/bridge/br_fdb.c (revision 87c2ce3b)
1 /*
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>
23 #include <asm/atomic.h>
24 #include "br_private.h"
25 
26 static kmem_cache_t *br_fdb_cache __read_mostly;
27 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
28 		      const unsigned char *addr);
29 
30 void __init br_fdb_init(void)
31 {
32 	br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
33 					 sizeof(struct net_bridge_fdb_entry),
34 					 0,
35 					 SLAB_HWCACHE_ALIGN, NULL, NULL);
36 }
37 
38 void __exit br_fdb_fini(void)
39 {
40 	kmem_cache_destroy(br_fdb_cache);
41 }
42 
43 
44 /* if topology_changing then use forward_delay (default 15 sec)
45  * otherwise keep longer (default 5 minutes)
46  */
47 static __inline__ unsigned long hold_time(const struct net_bridge *br)
48 {
49 	return br->topology_change ? br->forward_delay : br->ageing_time;
50 }
51 
52 static __inline__ int has_expired(const struct net_bridge *br,
53 				  const struct net_bridge_fdb_entry *fdb)
54 {
55 	return !fdb->is_static
56 		&& time_before_eq(fdb->ageing_timer + hold_time(br), jiffies);
57 }
58 
59 static __inline__ int br_mac_hash(const unsigned char *mac)
60 {
61 	return jhash(mac, ETH_ALEN, 0) & (BR_HASH_SIZE - 1);
62 }
63 
64 static __inline__ void fdb_delete(struct net_bridge_fdb_entry *f)
65 {
66 	hlist_del_rcu(&f->hlist);
67 	br_fdb_put(f);
68 }
69 
70 void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr)
71 {
72 	struct net_bridge *br = p->br;
73 	int i;
74 
75 	spin_lock_bh(&br->hash_lock);
76 
77 	/* Search all chains since old address/hash is unknown */
78 	for (i = 0; i < BR_HASH_SIZE; i++) {
79 		struct hlist_node *h;
80 		hlist_for_each(h, &br->hash[i]) {
81 			struct net_bridge_fdb_entry *f;
82 
83 			f = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
84 			if (f->dst == p && f->is_local) {
85 				/* maybe another port has same hw addr? */
86 				struct net_bridge_port *op;
87 				list_for_each_entry(op, &br->port_list, list) {
88 					if (op != p &&
89 					    !compare_ether_addr(op->dev->dev_addr,
90 								f->addr.addr)) {
91 						f->dst = op;
92 						goto insert;
93 					}
94 				}
95 
96 				/* delete old one */
97 				fdb_delete(f);
98 				goto insert;
99 			}
100 		}
101 	}
102  insert:
103 	/* insert new address,  may fail if invalid address or dup. */
104 	fdb_insert(br, p, newaddr);
105 
106 	spin_unlock_bh(&br->hash_lock);
107 }
108 
109 void br_fdb_cleanup(unsigned long _data)
110 {
111 	struct net_bridge *br = (struct net_bridge *)_data;
112 	unsigned long delay = hold_time(br);
113 	int i;
114 
115 	spin_lock_bh(&br->hash_lock);
116 	for (i = 0; i < BR_HASH_SIZE; i++) {
117 		struct net_bridge_fdb_entry *f;
118 		struct hlist_node *h, *n;
119 
120 		hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
121 			if (!f->is_static &&
122 			    time_before_eq(f->ageing_timer + delay, jiffies))
123 				fdb_delete(f);
124 		}
125 	}
126 	spin_unlock_bh(&br->hash_lock);
127 
128 	mod_timer(&br->gc_timer, jiffies + HZ/10);
129 }
130 
131 void br_fdb_delete_by_port(struct net_bridge *br, struct net_bridge_port *p)
132 {
133 	int i;
134 
135 	spin_lock_bh(&br->hash_lock);
136 	for (i = 0; i < BR_HASH_SIZE; i++) {
137 		struct hlist_node *h, *g;
138 
139 		hlist_for_each_safe(h, g, &br->hash[i]) {
140 			struct net_bridge_fdb_entry *f
141 				= hlist_entry(h, struct net_bridge_fdb_entry, hlist);
142 			if (f->dst != p)
143 				continue;
144 
145 			/*
146 			 * if multiple ports all have the same device address
147 			 * then when one port is deleted, assign
148 			 * the local entry to other port
149 			 */
150 			if (f->is_local) {
151 				struct net_bridge_port *op;
152 				list_for_each_entry(op, &br->port_list, list) {
153 					if (op != p &&
154 					    !compare_ether_addr(op->dev->dev_addr,
155 								f->addr.addr)) {
156 						f->dst = op;
157 						goto skip_delete;
158 					}
159 				}
160 			}
161 
162 			fdb_delete(f);
163 		skip_delete: ;
164 		}
165 	}
166 	spin_unlock_bh(&br->hash_lock);
167 }
168 
169 /* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */
170 struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
171 					  const unsigned char *addr)
172 {
173 	struct hlist_node *h;
174 	struct net_bridge_fdb_entry *fdb;
175 
176 	hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
177 		if (!compare_ether_addr(fdb->addr.addr, addr)) {
178 			if (unlikely(has_expired(br, fdb)))
179 				break;
180 			return fdb;
181 		}
182 	}
183 
184 	return NULL;
185 }
186 
187 /* Interface used by ATM hook that keeps a ref count */
188 struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br,
189 					unsigned char *addr)
190 {
191 	struct net_bridge_fdb_entry *fdb;
192 
193 	rcu_read_lock();
194 	fdb = __br_fdb_get(br, addr);
195 	if (fdb)
196 		atomic_inc(&fdb->use_count);
197 	rcu_read_unlock();
198 	return fdb;
199 }
200 
201 static void fdb_rcu_free(struct rcu_head *head)
202 {
203 	struct net_bridge_fdb_entry *ent
204 		= container_of(head, struct net_bridge_fdb_entry, rcu);
205 	kmem_cache_free(br_fdb_cache, ent);
206 }
207 
208 /* Set entry up for deletion with RCU  */
209 void br_fdb_put(struct net_bridge_fdb_entry *ent)
210 {
211 	if (atomic_dec_and_test(&ent->use_count))
212 		call_rcu(&ent->rcu, fdb_rcu_free);
213 }
214 
215 /*
216  * Fill buffer with forwarding table records in
217  * the API format.
218  */
219 int br_fdb_fillbuf(struct net_bridge *br, void *buf,
220 		   unsigned long maxnum, unsigned long skip)
221 {
222 	struct __fdb_entry *fe = buf;
223 	int i, num = 0;
224 	struct hlist_node *h;
225 	struct net_bridge_fdb_entry *f;
226 
227 	memset(buf, 0, maxnum*sizeof(struct __fdb_entry));
228 
229 	rcu_read_lock();
230 	for (i = 0; i < BR_HASH_SIZE; i++) {
231 		hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) {
232 			if (num >= maxnum)
233 				goto out;
234 
235 			if (has_expired(br, f))
236 				continue;
237 
238 			if (skip) {
239 				--skip;
240 				continue;
241 			}
242 
243 			/* convert from internal format to API */
244 			memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN);
245 			fe->port_no = f->dst->port_no;
246 			fe->is_local = f->is_local;
247 			if (!f->is_static)
248 				fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer);
249 			++fe;
250 			++num;
251 		}
252 	}
253 
254  out:
255 	rcu_read_unlock();
256 
257 	return num;
258 }
259 
260 static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
261 						    const unsigned char *addr)
262 {
263 	struct hlist_node *h;
264 	struct net_bridge_fdb_entry *fdb;
265 
266 	hlist_for_each_entry_rcu(fdb, h, head, hlist) {
267 		if (!compare_ether_addr(fdb->addr.addr, addr))
268 			return fdb;
269 	}
270 	return NULL;
271 }
272 
273 static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
274 					       struct net_bridge_port *source,
275 					       const unsigned char *addr,
276 					       int is_local)
277 {
278 	struct net_bridge_fdb_entry *fdb;
279 
280 	fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
281 	if (fdb) {
282 		memcpy(fdb->addr.addr, addr, ETH_ALEN);
283 		atomic_set(&fdb->use_count, 1);
284 		hlist_add_head_rcu(&fdb->hlist, head);
285 
286 		fdb->dst = source;
287 		fdb->is_local = is_local;
288 		fdb->is_static = is_local;
289 		fdb->ageing_timer = jiffies;
290 	}
291 	return fdb;
292 }
293 
294 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
295 		  const unsigned char *addr)
296 {
297 	struct hlist_head *head = &br->hash[br_mac_hash(addr)];
298 	struct net_bridge_fdb_entry *fdb;
299 
300 	if (!is_valid_ether_addr(addr))
301 		return -EINVAL;
302 
303 	fdb = fdb_find(head, addr);
304 	if (fdb) {
305 		/* it is okay to have multiple ports with same
306 		 * address, just use the first one.
307 		 */
308 		if (fdb->is_local)
309 			return 0;
310 
311 		printk(KERN_WARNING "%s adding interface with same address "
312 		       "as a received packet\n",
313 		       source->dev->name);
314 		fdb_delete(fdb);
315  	}
316 
317 	if (!fdb_create(head, source, addr, 1))
318 		return -ENOMEM;
319 
320 	return 0;
321 }
322 
323 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
324 		  const unsigned char *addr)
325 {
326 	int ret;
327 
328 	spin_lock_bh(&br->hash_lock);
329 	ret = fdb_insert(br, source, addr);
330 	spin_unlock_bh(&br->hash_lock);
331 	return ret;
332 }
333 
334 void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source,
335 		   const unsigned char *addr)
336 {
337 	struct hlist_head *head = &br->hash[br_mac_hash(addr)];
338 	struct net_bridge_fdb_entry *fdb;
339 
340 	/* some users want to always flood. */
341 	if (hold_time(br) == 0)
342 		return;
343 
344 	rcu_read_lock();
345 	fdb = fdb_find(head, addr);
346 	if (likely(fdb)) {
347 		/* attempt to update an entry for a local interface */
348 		if (unlikely(fdb->is_local)) {
349 			if (net_ratelimit())
350 				printk(KERN_WARNING "%s: received packet with "
351 				       " own address as source address\n",
352 				       source->dev->name);
353 		} else {
354 			/* fastpath: update of existing entry */
355 			fdb->dst = source;
356 			fdb->ageing_timer = jiffies;
357 		}
358 	} else {
359 		spin_lock_bh(&br->hash_lock);
360 		if (!fdb_find(head, addr))
361 			fdb_create(head, source, addr, 0);
362 		/* else  we lose race and someone else inserts
363 		 * it first, don't bother updating
364 		 */
365 		spin_unlock_bh(&br->hash_lock);
366 	}
367 	rcu_read_unlock();
368 }
369