LXR linux/net/bridge/br

   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 <asm/atomic.h>
  24#include <asm/unaligned.h>
  25#include "br_private.h"
  26
  27static struct kmem_cache *br_fdb_cache __read_mostly;
  28static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
  29                      const unsigned char *addr);
  30
  31static u32 fdb_salt __read_mostly;
  32
  33int __init br_fdb_init(void)
  34{
  35        br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
  36                                         sizeof(struct net_bridge_fdb_entry),
  37                                         0,
  38                                         SLAB_HWCACHE_ALIGN, NULL);
  39        if (!br_fdb_cache)
  40                return -ENOMEM;
  41
  42        get_random_bytes(&fdb_salt, sizeof(fdb_salt));
  43        return 0;
  44}
  45
  46void br_fdb_fini(void)
  47{
  48        kmem_cache_destroy(br_fdb_cache);
  49}
  50
  51
  52/* if topology_changing then use forward_delay (default 15 sec)
  53 * otherwise keep longer (default 5 minutes)
  54 */
  55static inline unsigned long hold_time(const struct net_bridge *br)
  56{
  57        return br->topology_change ? br->forward_delay : br->ageing_time;
  58}
  59
  60static inline int has_expired(const struct net_bridge *br,
  61                                  const struct net_bridge_fdb_entry *fdb)
  62{
  63        return !fdb->is_static
  64                && time_before_eq(fdb->ageing_timer + hold_time(br), jiffies);
  65}
  66
  67static inline int br_mac_hash(const unsigned char *mac)
  68{
  69        /* use 1 byte of OUI cnd 3 bytes of NIC */
  70        u32 key = get_unaligned((u32 *)(mac + 2));
  71        return jhash_1word(key, fdb_salt) & (BR_HASH_SIZE - 1);
  72}
  73
  74static void fdb_rcu_free(struct rcu_head *head)
  75{
  76        struct net_bridge_fdb_entry *ent
  77                = container_of(head, struct net_bridge_fdb_entry, rcu);
  78        kmem_cache_free(br_fdb_cache, ent);
  79}
  80
  81static inline void fdb_delete(struct net_bridge_fdb_entry *f)
  82{
  83        hlist_del_rcu(&f->hlist);
  84        call_rcu(&f->rcu, fdb_rcu_free);
  85}
  86
  87void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr)
  88{
  89        struct net_bridge *br = p->br;
  90        int i;
  91
  92        spin_lock_bh(&br->hash_lock);
  93
  94        /* Search all chains since old address/hash is unknown */
  95        for (i = 0; i < BR_HASH_SIZE; i++) {
  96                struct hlist_node *h;
  97                hlist_for_each(h, &br->hash[i]) {
  98                        struct net_bridge_fdb_entry *f;
  99
 100                        f = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
 101                        if (f->dst == p && f->is_local) {
 102                                /* maybe another port has same hw addr? */
 103                                struct net_bridge_port *op;
 104                                list_for_each_entry(op, &br->port_list, list) {
 105                                        if (op != p &&
 106                                            !compare_ether_addr(op->dev->dev_addr,
 107                                                                f->addr.addr)) {
 108                                                f->dst = op;
 109                                                goto insert;
 110                                        }
 111                                }
 112
 113                                /* delete old one */
 114                                fdb_delete(f);
 115                                goto insert;
 116                        }
 117                }
 118        }
 119 insert:
 120        /* insert new address,  may fail if invalid address or dup. */
 121        fdb_insert(br, p, newaddr);
 122
 123        spin_unlock_bh(&br->hash_lock);
 124}
 125
 126void br_fdb_cleanup(unsigned long _data)
 127{
 128        struct net_bridge *br = (struct net_bridge *)_data;
 129        unsigned long delay = hold_time(br);
 130        unsigned long next_timer = jiffies + br->forward_delay;
 131        int i;
 132
 133        spin_lock_bh(&br->hash_lock);
 134        for (i = 0; i < BR_HASH_SIZE; i++) {
 135                struct net_bridge_fdb_entry *f;
 136                struct hlist_node *h, *n;
 137
 138                hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
 139                        unsigned long this_timer;
 140                        if (f->is_static)
 141                                continue;
 142                        this_timer = f->ageing_timer + delay;
 143                        if (time_before_eq(this_timer, jiffies))
 144                                fdb_delete(f);
 145                        else if (time_before(this_timer, next_timer))
 146                                next_timer = this_timer;
 147                }
 148        }
 149        spin_unlock_bh(&br->hash_lock);
 150
 151        /* Add HZ/4 to ensure we round the jiffies upwards to be after the next
 152         * timer, otherwise we might round down and will have no-op run. */
 153        mod_timer(&br->gc_timer, round_jiffies(next_timer + HZ/4));
 154}
 155
 156/* Completely flush all dynamic entries in forwarding database.*/
 157void br_fdb_flush(struct net_bridge *br)
 158{
 159        int i;
 160
 161        spin_lock_bh(&br->hash_lock);
 162        for (i = 0; i < BR_HASH_SIZE; i++) {
 163                struct net_bridge_fdb_entry *f;
 164                struct hlist_node *h, *n;
 165                hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
 166                        if (!f->is_static)
 167                                fdb_delete(f);
 168                }
 169        }
 170        spin_unlock_bh(&br->hash_lock);
 171}
 172
 173/* Flush all entries refering to a specific port.
 174 * if do_all is set also flush static entries
 175 */
 176void br_fdb_delete_by_port(struct net_bridge *br,
 177                           const struct net_bridge_port *p,
 178                           int do_all)
 179{
 180        int i;
 181
 182        spin_lock_bh(&br->hash_lock);
 183        for (i = 0; i < BR_HASH_SIZE; i++) {
 184                struct hlist_node *h, *g;
 185
 186                hlist_for_each_safe(h, g, &br->hash[i]) {
 187                        struct net_bridge_fdb_entry *f
 188                                = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
 189                        if (f->dst != p)
 190                                continue;
 191
 192                        if (f->is_static && !do_all)
 193                                continue;
 194                        /*
 195                         * if multiple ports all have the same device address
 196                         * then when one port is deleted, assign
 197                         * the local entry to other port
 198                         */
 199                        if (f->is_local) {
 200                                struct net_bridge_port *op;
 201                                list_for_each_entry(op, &br->port_list, list) {
 202                                        if (op != p &&
 203                                            !compare_ether_addr(op->dev->dev_addr,
 204                                                                f->addr.addr)) {
 205                                                f->dst = op;
 206                                                goto skip_delete;
 207                                        }
 208                                }
 209                        }
 210
 211                        fdb_delete(f);
 212                skip_delete: ;
 213                }
 214        }
 215        spin_unlock_bh(&br->hash_lock);
 216}
 217
 218/* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */
 219struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
 220                                          const unsigned char *addr)
 221{
 222        struct hlist_node *h;
 223        struct net_bridge_fdb_entry *fdb;
 224
 225        hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
 226                if (!compare_ether_addr(fdb->addr.addr, addr)) {
 227                        if (unlikely(has_expired(br, fdb)))
 228                                break;
 229                        return fdb;
 230                }
 231        }
 232
 233        return NULL;
 234}
 235
 236#if defined(CONFIG_ATM_LANE) || defined(CONFIG_ATM_LANE_MODULE)
 237/* Interface used by ATM LANE hook to test
 238 * if an addr is on some other bridge port */
 239int br_fdb_test_addr(struct net_device *dev, unsigned char *addr)
 240{
 241        struct net_bridge_fdb_entry *fdb;
 242        int ret;
 243
 244        if (!dev->br_port)
 245                return 0;
 246
 247        rcu_read_lock();
 248        fdb = __br_fdb_get(dev->br_port->br, addr);
 249        ret = fdb && fdb->dst->dev != dev &&
 250                fdb->dst->state == BR_STATE_FORWARDING;
 251        rcu_read_unlock();
 252
 253        return ret;
 254}
 255#endif /* CONFIG_ATM_LANE */
 256
 257/*
 258 * Fill buffer with forwarding table records in
 259 * the API format.
 260 */
 261int br_fdb_fillbuf(struct net_bridge *br, void *buf,
 262                   unsigned long maxnum, unsigned long skip)
 263{
 264        struct __fdb_entry *fe = buf;
 265        int i, num = 0;
 266        struct hlist_node *h;
 267        struct net_bridge_fdb_entry *f;
 268
 269        memset(buf, 0, maxnum*sizeof(struct __fdb_entry));
 270
 271        rcu_read_lock();
 272        for (i = 0; i < BR_HASH_SIZE; i++) {
 273                hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) {
 274                        if (num >= maxnum)
 275                                goto out;
 276
 277                        if (has_expired(br, f))
 278                                continue;
 279
 280                        if (skip) {
 281                                --skip;
 282                                continue;
 283                        }
 284
 285                        /* convert from internal format to API */
 286                        memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN);
 287
 288                        /* due to ABI compat need to split into hi/lo */
 289                        fe->port_no = f->dst->port_no;
 290                        fe->port_hi = f->dst->port_no >> 8;
 291
 292                        fe->is_local = f->is_local;
 293                        if (!f->is_static)
 294                                fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->ageing_timer);
 295                        ++fe;
 296                        ++num;
 297                }
 298        }
 299
 300 out:
 301        rcu_read_unlock();
 302
 303        return num;
 304}
 305
 306static inline struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
 307                                                    const unsigned char *addr)
 308{
 309        struct hlist_node *h;
 310        struct net_bridge_fdb_entry *fdb;
 311
 312        hlist_for_each_entry_rcu(fdb, h, head, hlist) {
 313                if (!compare_ether_addr(fdb->addr.addr, addr))
 314                        return fdb;
 315        }
 316        return NULL;
 317}
 318
 319static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
 320                                               struct net_bridge_port *source,
 321                                               const unsigned char *addr,
 322                                               int is_local)
 323{
 324        struct net_bridge_fdb_entry *fdb;
 325
 326        fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
 327        if (fdb) {
 328                memcpy(fdb->addr.addr, addr, ETH_ALEN);
 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