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 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); 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 132 void br_fdb_delete_by_port(struct net_bridge *br, 133 const struct net_bridge_port *p, 134 int do_all) 135 { 136 int i; 137 138 spin_lock_bh(&br->hash_lock); 139 for (i = 0; i < BR_HASH_SIZE; i++) { 140 struct hlist_node *h, *g; 141 142 hlist_for_each_safe(h, g, &br->hash[i]) { 143 struct net_bridge_fdb_entry *f 144 = hlist_entry(h, struct net_bridge_fdb_entry, hlist); 145 if (f->dst != p) 146 continue; 147 148 if (f->is_static && !do_all) 149 continue; 150 /* 151 * if multiple ports all have the same device address 152 * then when one port is deleted, assign 153 * the local entry to other port 154 */ 155 if (f->is_local) { 156 struct net_bridge_port *op; 157 list_for_each_entry(op, &br->port_list, list) { 158 if (op != p && 159 !compare_ether_addr(op->dev->dev_addr, 160 f->addr.addr)) { 161 f->dst = op; 162 goto skip_delete; 163 } 164 } 165 } 166 167 fdb_delete(f); 168 skip_delete: ; 169 } 170 } 171 spin_unlock_bh(&br->hash_lock); 172 } 173 174 /* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */ 175 struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br, 176 const unsigned char *addr) 177 { 178 struct hlist_node *h; 179 struct net_bridge_fdb_entry *fdb; 180 181 hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) { 182 if (!compare_ether_addr(fdb->addr.addr, addr)) { 183 if (unlikely(has_expired(br, fdb))) 184 break; 185 return fdb; 186 } 187 } 188 189 return NULL; 190 } 191 192 /* Interface used by ATM hook that keeps a ref count */ 193 struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br, 194 unsigned char *addr) 195 { 196 struct net_bridge_fdb_entry *fdb; 197 198 rcu_read_lock(); 199 fdb = __br_fdb_get(br, addr); 200 if (fdb) 201 atomic_inc(&fdb->use_count); 202 rcu_read_unlock(); 203 return fdb; 204 } 205 206 static void fdb_rcu_free(struct rcu_head *head) 207 { 208 struct net_bridge_fdb_entry *ent 209 = container_of(head, struct net_bridge_fdb_entry, rcu); 210 kmem_cache_free(br_fdb_cache, ent); 211 } 212 213 /* Set entry up for deletion with RCU */ 214 void br_fdb_put(struct net_bridge_fdb_entry *ent) 215 { 216 if (atomic_dec_and_test(&ent->use_count)) 217 call_rcu(&ent->rcu, fdb_rcu_free); 218 } 219 220 /* 221 * Fill buffer with forwarding table records in 222 * the API format. 223 */ 224 int br_fdb_fillbuf(struct net_bridge *br, void *buf, 225 unsigned long maxnum, unsigned long skip) 226 { 227 struct __fdb_entry *fe = buf; 228 int i, num = 0; 229 struct hlist_node *h; 230 struct net_bridge_fdb_entry *f; 231 232 memset(buf, 0, maxnum*sizeof(struct __fdb_entry)); 233 234 rcu_read_lock(); 235 for (i = 0; i < BR_HASH_SIZE; i++) { 236 hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) { 237 if (num >= maxnum) 238 goto out; 239 240 if (has_expired(br, f)) 241 continue; 242 243 if (skip) { 244 --skip; 245 continue; 246 } 247 248 /* convert from internal format to API */ 249 memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN); 250 fe->port_no = f->dst->port_no; 251 fe->is_local = f->is_local; 252 if (!f->is_static) 253 fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer); 254 ++fe; 255 ++num; 256 } 257 } 258 259 out: 260 rcu_read_unlock(); 261 262 return num; 263 } 264 265 static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head, 266 const unsigned char *addr) 267 { 268 struct hlist_node *h; 269 struct net_bridge_fdb_entry *fdb; 270 271 hlist_for_each_entry_rcu(fdb, h, head, hlist) { 272 if (!compare_ether_addr(fdb->addr.addr, addr)) 273 return fdb; 274 } 275 return NULL; 276 } 277 278 static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head, 279 struct net_bridge_port *source, 280 const unsigned char *addr, 281 int is_local) 282 { 283 struct net_bridge_fdb_entry *fdb; 284 285 fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC); 286 if (fdb) { 287 memcpy(fdb->addr.addr, addr, ETH_ALEN); 288 atomic_set(&fdb->use_count, 1); 289 hlist_add_head_rcu(&fdb->hlist, head); 290 291 fdb->dst = source; 292 fdb->is_local = is_local; 293 fdb->is_static = is_local; 294 fdb->ageing_timer = jiffies; 295 } 296 return fdb; 297 } 298 299 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 300 const unsigned char *addr) 301 { 302 struct hlist_head *head = &br->hash[br_mac_hash(addr)]; 303 struct net_bridge_fdb_entry *fdb; 304 305 if (!is_valid_ether_addr(addr)) 306 return -EINVAL; 307 308 fdb = fdb_find(head, addr); 309 if (fdb) { 310 /* it is okay to have multiple ports with same 311 * address, just use the first one. 312 */ 313 if (fdb->is_local) 314 return 0; 315 316 printk(KERN_WARNING "%s adding interface with same address " 317 "as a received packet\n", 318 source->dev->name); 319 fdb_delete(fdb); 320 } 321 322 if (!fdb_create(head, source, addr, 1)) 323 return -ENOMEM; 324 325 return 0; 326 } 327 328 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source, 329 const unsigned char *addr) 330 { 331 int ret; 332 333 spin_lock_bh(&br->hash_lock); 334 ret = fdb_insert(br, source, addr); 335 spin_unlock_bh(&br->hash_lock); 336 return ret; 337 } 338 339 void br_fdb_update(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 /* some users want to always flood. */ 346 if (hold_time(br) == 0) 347 return; 348 349 fdb = fdb_find(head, addr); 350 if (likely(fdb)) { 351 /* attempt to update an entry for a local interface */ 352 if (unlikely(fdb->is_local)) { 353 if (net_ratelimit()) 354 printk(KERN_WARNING "%s: received packet with " 355 " own address as source address\n", 356 source->dev->name); 357 } else { 358 /* fastpath: update of existing entry */ 359 fdb->dst = source; 360 fdb->ageing_timer = jiffies; 361 } 362 } else { 363 spin_lock(&br->hash_lock); 364 if (!fdb_find(head, addr)) 365 fdb_create(head, source, addr, 0); 366 /* else we lose race and someone else inserts 367 * it first, don't bother updating 368 */ 369 spin_unlock(&br->hash_lock); 370 } 371 } 372