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/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" 27 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); 31 32 static u32 fdb_salt __read_mostly; 33 34 int __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); 40 if (!br_fdb_cache) 41 return -ENOMEM; 42 43 get_random_bytes(&fdb_salt, sizeof(fdb_salt)); 44 return 0; 45 } 46 47 void br_fdb_fini(void) 48 { 49 kmem_cache_destroy(br_fdb_cache); 50 } 51 52 53 /* if topology_changing then use forward_delay (default 15 sec) 54 * otherwise keep longer (default 5 minutes) 55 */ 56 static inline unsigned long hold_time(const struct net_bridge *br) 57 { 58 return br->topology_change ? br->forward_delay : br->ageing_time; 59 } 60 61 static inline int has_expired(const struct net_bridge *br, 62 const struct net_bridge_fdb_entry *fdb) 63 { 64 return !fdb->is_static && 65 time_before_eq(fdb->ageing_timer + hold_time(br), jiffies); 66 } 67 68 static inline int br_mac_hash(const unsigned char *mac) 69 { 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); 73 } 74 75 static void fdb_rcu_free(struct rcu_head *head) 76 { 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); 80 } 81 82 static inline void fdb_delete(struct net_bridge_fdb_entry *f) 83 { 84 hlist_del_rcu(&f->hlist); 85 call_rcu(&f->rcu, fdb_rcu_free); 86 } 87 88 void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr) 89 { 90 struct net_bridge *br = p->br; 91 int i; 92 93 spin_lock_bh(&br->hash_lock); 94 95 /* Search all chains since old address/hash is unknown */ 96 for (i = 0; i < BR_HASH_SIZE; i++) { 97 struct hlist_node *h; 98 hlist_for_each(h, &br->hash[i]) { 99 struct net_bridge_fdb_entry *f; 100 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) { 106 if (op != p && 107 !compare_ether_addr(op->dev->dev_addr, 108 f->addr.addr)) { 109 f->dst = op; 110 goto insert; 111 } 112 } 113 114 /* delete old one */ 115 fdb_delete(f); 116 goto insert; 117 } 118 } 119 } 120 insert: 121 /* insert new address, may fail if invalid address or dup. */ 122 fdb_insert(br, p, newaddr); 123 124 spin_unlock_bh(&br->hash_lock); 125 } 126 127 void br_fdb_cleanup(unsigned long _data) 128 { 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; 132 int i; 133 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; 138 139 hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) { 140 unsigned long this_timer; 141 if (f->is_static) 142 continue; 143 this_timer = f->ageing_timer + delay; 144 if (time_before_eq(this_timer, jiffies)) 145 fdb_delete(f); 146 else if (time_before(this_timer, next_timer)) 147 next_timer = this_timer; 148 } 149 } 150 spin_unlock_bh(&br->hash_lock); 151 152 mod_timer(&br->gc_timer, round_jiffies_up(next_timer)); 153 } 154 155 /* Completely flush all dynamic entries in forwarding database.*/ 156 void br_fdb_flush(struct net_bridge *br) 157 { 158 int i; 159 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) { 165 if (!f->is_static) 166 fdb_delete(f); 167 } 168 } 169 spin_unlock_bh(&br->hash_lock); 170 } 171 172 /* Flush all entries refering to a specific port. 173 * if do_all is set also flush static entries 174 */ 175 void br_fdb_delete_by_port(struct net_bridge *br, 176 const struct net_bridge_port *p, 177 int do_all) 178 { 179 int i; 180 181 spin_lock_bh(&br->hash_lock); 182 for (i = 0; i < BR_HASH_SIZE; i++) { 183 struct hlist_node *h, *g; 184 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); 188 if (f->dst != p) 189 continue; 190 191 if (f->is_static && !do_all) 192 continue; 193 /* 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 197 */ 198 if (f->is_local) { 199 struct net_bridge_port *op; 200 list_for_each_entry(op, &br->port_list, list) { 201 if (op != p && 202 !compare_ether_addr(op->dev->dev_addr, 203 f->addr.addr)) { 204 f->dst = op; 205 goto skip_delete; 206 } 207 } 208 } 209 210 fdb_delete(f); 211 skip_delete: ; 212 } 213 } 214 spin_unlock_bh(&br->hash_lock); 215 } 216 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) 220 { 221 struct hlist_node *h; 222 struct net_bridge_fdb_entry *fdb; 223 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))) 227 break; 228 return fdb; 229 } 230 } 231 232 return NULL; 233 } 234 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) 239 { 240 struct net_bridge_fdb_entry *fdb; 241 struct net_bridge_port *port; 242 int ret; 243 244 rcu_read_lock(); 245 port = br_port_get_rcu(dev); 246 if (!port) 247 ret = 0; 248 else { 249 fdb = __br_fdb_get(port->br, addr); 250 ret = fdb && fdb->dst->dev != dev && 251 fdb->dst->state == BR_STATE_FORWARDING; 252 } 253 rcu_read_unlock(); 254 255 return ret; 256 } 257 #endif /* CONFIG_ATM_LANE */ 258 259 /* 260 * Fill buffer with forwarding table records in 261 * the API format. 262 */ 263 int br_fdb_fillbuf(struct net_bridge *br, void *buf, 264 unsigned long maxnum, unsigned long skip) 265 { 266 struct __fdb_entry *fe = buf; 267 int i, num = 0; 268 struct hlist_node *h; 269 struct net_bridge_fdb_entry *f; 270 271 memset(buf, 0, maxnum*sizeof(struct __fdb_entry)); 272 273 rcu_read_lock(); 274 for (i = 0; i < BR_HASH_SIZE; i++) { 275 hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) { 276 if (num >= maxnum) 277 goto out; 278 279 if (has_expired(br, f)) 280 continue; 281 282 if (skip) { 283 --skip; 284 continue; 285 } 286 287 /* convert from internal format to API */ 288 memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN); 289 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; 293 294 fe->is_local = f->is_local; 295 if (!f->is_static) 296 fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer); 297 ++fe; 298 ++num; 299 } 300 } 301 302 out: 303 rcu_read_unlock(); 304 305 return num; 306 } 307 308 static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head, 309 const unsigned char *addr) 310 { 311 struct hlist_node *h; 312 struct net_bridge_fdb_entry *fdb; 313 314 hlist_for_each_entry_rcu(fdb, h, head, hlist) { 315 if (!compare_ether_addr(fdb->addr.addr, addr)) 316 return fdb; 317 } 318 return NULL; 319 } 320 321 static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head, 322 struct net_bridge_port *source, 323 const unsigned char *addr, 324 int is_local) 325 { 326 struct net_bridge_fdb_entry *fdb; 327 328 fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC); 329 if (fdb) { 330 memcpy(fdb->addr.addr, addr, ETH_ALEN); 331 hlist_add_head_rcu(&fdb->hlist, head); 332 333 fdb->dst = source; 334 fdb->is_local = is_local; 335 fdb->is_static = is_local; 336 fdb->ageing_timer = jiffies; 337 } 338 return fdb; 339 } 340 341 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 342 const unsigned char *addr) 343 { 344 struct hlist_head *head = &br->hash[br_mac_hash(addr)]; 345 struct net_bridge_fdb_entry *fdb; 346 347 if (!is_valid_ether_addr(addr)) 348 return -EINVAL; 349 350 fdb = fdb_find(head, addr); 351 if (fdb) { 352 /* it is okay to have multiple ports with same 353 * address, just use the first one. 354 */ 355 if (fdb->is_local) 356 return 0; 357 br_warn(br, "adding interface %s with same address " 358 "as a received packet\n", 359 source->dev->name); 360 fdb_delete(fdb); 361 } 362 363 if (!fdb_create(head, source, addr, 1)) 364 return -ENOMEM; 365 366 return 0; 367 } 368 369 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 370 const unsigned char *addr) 371 { 372 int ret; 373 374 spin_lock_bh(&br->hash_lock); 375 ret = fdb_insert(br, source, addr); 376 spin_unlock_bh(&br->hash_lock); 377 return ret; 378 } 379 380 void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source, 381 const unsigned char *addr) 382 { 383 struct hlist_head *head = &br->hash[br_mac_hash(addr)]; 384 struct net_bridge_fdb_entry *fdb; 385 386 /* some users want to always flood. */ 387 if (hold_time(br) == 0) 388 return; 389 390 /* ignore packets unless we are using this port */ 391 if (!(source->state == BR_STATE_LEARNING || 392 source->state == BR_STATE_FORWARDING)) 393 return; 394 395 fdb = fdb_find(head, addr); 396 if (likely(fdb)) { 397 /* attempt to update an entry for a local interface */ 398 if (unlikely(fdb->is_local)) { 399 if (net_ratelimit()) 400 br_warn(br, "received packet on %s with " 401 "own address as source address\n", 402 source->dev->name); 403 } else { 404 /* fastpath: update of existing entry */ 405 fdb->dst = source; 406 fdb->ageing_timer = jiffies; 407 } 408 } else { 409 spin_lock(&br->hash_lock); 410 if (!fdb_find(head, addr)) 411 fdb_create(head, source, addr, 0); 412 /* else we lose race and someone else inserts 413 * it first, don't bother updating 414 */ 415 spin_unlock(&br->hash_lock); 416 } 417 } 418