net/bridge/br_fdb.c

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