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