br_fdb.c revision 0b040829952d84bf2a62526f0e24b624e0699447
1/* 2 * Forwarding database 3 * Linux ethernet bridge 4 * 5 * Authors: 6 * Lennert Buytenhek <buytenh@gnu.org> 7 * 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. 12 */ 13 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" 25 26static struct kmem_cache *br_fdb_cache __read_mostly; 27static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 28 const unsigned char *addr); 29 30static u32 fdb_salt __read_mostly; 31 32int __init br_fdb_init(void) 33{ 34 br_fdb_cache = kmem_cache_create("bridge_fdb_cache", 35 sizeof(struct net_bridge_fdb_entry), 36 0, 37 SLAB_HWCACHE_ALIGN, NULL); 38 if (!br_fdb_cache) 39 return -ENOMEM; 40 41 get_random_bytes(&fdb_salt, sizeof(fdb_salt)); 42 return 0; 43} 44 45void br_fdb_fini(void) 46{ 47 kmem_cache_destroy(br_fdb_cache); 48} 49 50 51/* if topology_changing then use forward_delay (default 15 sec) 52 * otherwise keep longer (default 5 minutes) 53 */ 54static inline unsigned long hold_time(const struct net_bridge *br) 55{ 56 return br->topology_change ? br->forward_delay : br->ageing_time; 57} 58 59static inline int has_expired(const struct net_bridge *br, 60 const struct net_bridge_fdb_entry *fdb) 61{ 62 return !fdb->is_static 63 && time_before_eq(fdb->ageing_timer + hold_time(br), jiffies); 64} 65 66static inline int br_mac_hash(const unsigned char *mac) 67{ 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); 71} 72 73static inline void fdb_delete(struct net_bridge_fdb_entry *f) 74{ 75 hlist_del_rcu(&f->hlist); 76 br_fdb_put(f); 77} 78 79void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr) 80{ 81 struct net_bridge *br = p->br; 82 int i; 83 84 spin_lock_bh(&br->hash_lock); 85 86 /* Search all chains since old address/hash is unknown */ 87 for (i = 0; i < BR_HASH_SIZE; i++) { 88 struct hlist_node *h; 89 hlist_for_each(h, &br->hash[i]) { 90 struct net_bridge_fdb_entry *f; 91 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) { 97 if (op != p && 98 !compare_ether_addr(op->dev->dev_addr, 99 f->addr.addr)) { 100 f->dst = op; 101 goto insert; 102 } 103 } 104 105 /* delete old one */ 106 fdb_delete(f); 107 goto insert; 108 } 109 } 110 } 111 insert: 112 /* insert new address, may fail if invalid address or dup. */ 113 fdb_insert(br, p, newaddr); 114 115 spin_unlock_bh(&br->hash_lock); 116} 117 118void br_fdb_cleanup(unsigned long _data) 119{ 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; 123 int i; 124 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; 129 130 hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) { 131 unsigned long this_timer; 132 if (f->is_static) 133 continue; 134 this_timer = f->ageing_timer + delay; 135 if (time_before_eq(this_timer, jiffies)) 136 fdb_delete(f); 137 else if (time_before(this_timer, next_timer)) 138 next_timer = this_timer; 139 } 140 } 141 spin_unlock_bh(&br->hash_lock); 142 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)); 146} 147 148/* Completely flush all dynamic entries in forwarding database.*/ 149void br_fdb_flush(struct net_bridge *br) 150{ 151 int i; 152 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) { 158 if (!f->is_static) 159 fdb_delete(f); 160 } 161 } 162 spin_unlock_bh(&br->hash_lock); 163} 164 165/* Flush all entries refering to a specific port. 166 * if do_all is set also flush static entries 167 */ 168void br_fdb_delete_by_port(struct net_bridge *br, 169 const struct net_bridge_port *p, 170 int do_all) 171{ 172 int i; 173 174 spin_lock_bh(&br->hash_lock); 175 for (i = 0; i < BR_HASH_SIZE; i++) { 176 struct hlist_node *h, *g; 177 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); 181 if (f->dst != p) 182 continue; 183 184 if (f->is_static && !do_all) 185 continue; 186 /* 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 190 */ 191 if (f->is_local) { 192 struct net_bridge_port *op; 193 list_for_each_entry(op, &br->port_list, list) { 194 if (op != p && 195 !compare_ether_addr(op->dev->dev_addr, 196 f->addr.addr)) { 197 f->dst = op; 198 goto skip_delete; 199 } 200 } 201 } 202 203 fdb_delete(f); 204 skip_delete: ; 205 } 206 } 207 spin_unlock_bh(&br->hash_lock); 208} 209 210/* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */ 211struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br, 212 const unsigned char *addr) 213{ 214 struct hlist_node *h; 215 struct net_bridge_fdb_entry *fdb; 216 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))) 220 break; 221 return fdb; 222 } 223 } 224 225 return NULL; 226} 227 228/* Interface used by ATM hook that keeps a ref count */ 229struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br, 230 unsigned char *addr) 231{ 232 struct net_bridge_fdb_entry *fdb; 233 234 rcu_read_lock(); 235 fdb = __br_fdb_get(br, addr); 236 if (fdb && !atomic_inc_not_zero(&fdb->use_count)) 237 fdb = NULL; 238 rcu_read_unlock(); 239 return fdb; 240} 241 242static void fdb_rcu_free(struct rcu_head *head) 243{ 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); 247} 248 249/* Set entry up for deletion with RCU */ 250void br_fdb_put(struct net_bridge_fdb_entry *ent) 251{ 252 if (atomic_dec_and_test(&ent->use_count)) 253 call_rcu(&ent->rcu, fdb_rcu_free); 254} 255 256/* 257 * Fill buffer with forwarding table records in 258 * the API format. 259 */ 260int br_fdb_fillbuf(struct net_bridge *br, void *buf, 261 unsigned long maxnum, unsigned long skip) 262{ 263 struct __fdb_entry *fe = buf; 264 int i, num = 0; 265 struct hlist_node *h; 266 struct net_bridge_fdb_entry *f; 267 268 memset(buf, 0, maxnum*sizeof(struct __fdb_entry)); 269 270 rcu_read_lock(); 271 for (i = 0; i < BR_HASH_SIZE; i++) { 272 hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) { 273 if (num >= maxnum) 274 goto out; 275 276 if (has_expired(br, f)) 277 continue; 278 279 if (skip) { 280 --skip; 281 continue; 282 } 283 284 /* convert from internal format to API */ 285 memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN); 286 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; 290 291 fe->is_local = f->is_local; 292 if (!f->is_static) 293 fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer); 294 ++fe; 295 ++num; 296 } 297 } 298 299 out: 300 rcu_read_unlock(); 301 302 return num; 303} 304 305static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head, 306 const unsigned char *addr) 307{ 308 struct hlist_node *h; 309 struct net_bridge_fdb_entry *fdb; 310 311 hlist_for_each_entry_rcu(fdb, h, head, hlist) { 312 if (!compare_ether_addr(fdb->addr.addr, addr)) 313 return fdb; 314 } 315 return NULL; 316} 317 318static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head, 319 struct net_bridge_port *source, 320 const unsigned char *addr, 321 int is_local) 322{ 323 struct net_bridge_fdb_entry *fdb; 324 325 fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC); 326 if (fdb) { 327 memcpy(fdb->addr.addr, addr, ETH_ALEN); 328 atomic_set(&fdb->use_count, 1); 329 hlist_add_head_rcu(&fdb->hlist, head); 330 331 fdb->dst = source; 332 fdb->is_local = is_local; 333 fdb->is_static = is_local; 334 fdb->ageing_timer = jiffies; 335 } 336 return fdb; 337} 338 339static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 340 const unsigned char *addr) 341{ 342 struct hlist_head *head = &br->hash[br_mac_hash(addr)]; 343 struct net_bridge_fdb_entry *fdb; 344 345 if (!is_valid_ether_addr(addr)) 346 return -EINVAL; 347 348 fdb = fdb_find(head, addr); 349 if (fdb) { 350 /* it is okay to have multiple ports with same 351 * address, just use the first one. 352 */ 353 if (fdb->is_local) 354 return 0; 355 356 printk(KERN_WARNING "%s adding interface with same address " 357 "as a received packet\n", 358 source->dev->name); 359 fdb_delete(fdb); 360 } 361 362 if (!fdb_create(head, source, addr, 1)) 363 return -ENOMEM; 364 365 return 0; 366} 367 368int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 369 const unsigned char *addr) 370{ 371 int ret; 372 373 spin_lock_bh(&br->hash_lock); 374 ret = fdb_insert(br, source, addr); 375 spin_unlock_bh(&br->hash_lock); 376 return ret; 377} 378 379void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source, 380 const unsigned char *addr) 381{ 382 struct hlist_head *head = &br->hash[br_mac_hash(addr)]; 383 struct net_bridge_fdb_entry *fdb; 384 385 /* some users want to always flood. */ 386 if (hold_time(br) == 0) 387 return; 388 389 /* ignore packets unless we are using this port */ 390 if (!(source->state == BR_STATE_LEARNING || 391 source->state == BR_STATE_FORWARDING)) 392 return; 393 394 fdb = fdb_find(head, addr); 395 if (likely(fdb)) { 396 /* attempt to update an entry for a local interface */ 397 if (unlikely(fdb->is_local)) { 398 if (net_ratelimit()) 399 printk(KERN_WARNING "%s: received packet with " 400 " own address as source address\n", 401 source->dev->name); 402 } else { 403 /* fastpath: update of existing entry */ 404 fdb->dst = source; 405 fdb->ageing_timer = jiffies; 406 } 407 } else { 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 413 */ 414 spin_unlock(&br->hash_lock); 415 } 416} 417