linux/net/bridge/br_fdb.c
<<
>>
Prefs
   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 inline void fdb_delete(struct net_bridge_fdb_entry *f)
  75{
  76        hlist_del_rcu(&f->hlist);
  77        br_fdb_put(f);
  78}
  79
  80void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr)
  81{
  82        struct net_bridge *br = p->br;
  83        int i;
  84
  85        spin_lock_bh(&br->hash_lock);
  86
  87        /* Search all chains since old address/hash is unknown */
  88        for (i = 0; i < BR_HASH_SIZE; i++) {
  89                struct hlist_node *h;
  90                hlist_for_each(h, &br->hash[i]) {
  91                        struct net_bridge_fdb_entry *f;
  92
  93                        f = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
  94                        if (f->dst == p && f->is_local) {
  95                                /* maybe another port has same hw addr? */
  96                                struct net_bridge_port *op;
  97                                list_for_each_entry(op, &br->port_list, list) {
  98                                        if (op != p &&
  99                                            !compare_ether_addr(op->dev->dev_addr,
 100                                                                f->addr.addr)) {
 101                                                f->dst = op;
 102                                                goto insert;
 103                                        }
 104                                }
 105
 106                                /* delete old one */
 107                                fdb_delete(f);
 108                                goto insert;
 109                        }
 110                }
 111        }
 112 insert:
 113        /* insert new address,  may fail if invalid address or dup. */
 114        fdb_insert(br, p, newaddr);
 115
 116        spin_unlock_bh(&br->hash_lock);
 117}
 118
 119void br_fdb_cleanup(unsigned long _data)
 120{
 121        struct net_bridge *br = (struct net_bridge *)_data;
 122        unsigned long delay = hold_time(br);
 123        unsigned long next_timer = jiffies + br->forward_delay;
 124        int i;
 125
 126        spin_lock_bh(&br->hash_lock);
 127        for (i = 0; i < BR_HASH_SIZE; i++) {
 128                struct net_bridge_fdb_entry *f;
 129                struct hlist_node *h, *n;
 130
 131                hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
 132                        unsigned long this_timer;
 133                        if (f->is_static)
 134                                continue;
 135                        this_timer = f->ageing_timer + delay;
 136                        if (time_before_eq(this_timer, jiffies))
 137                                fdb_delete(f);
 138                        else if (time_before(this_timer, next_timer))
 139                                next_timer = this_timer;
 140                }
 141        }
 142        spin_unlock_bh(&br->hash_lock);
 143
 144        /* Add HZ/4 to ensure we round the jiffies upwards to be after the next
 145         * timer, otherwise we might round down and will have no-op run. */
 146        mod_timer(&br->gc_timer, round_jiffies(next_timer + HZ/4));
 147}
 148
 149/* Completely flush all dynamic entries in forwarding database.*/
 150void br_fdb_flush(struct net_bridge *br)
 151{
 152        int i;
 153
 154        spin_lock_bh(&br->hash_lock);
 155        for (i = 0; i < BR_HASH_SIZE; i++) {
 156                struct net_bridge_fdb_entry *f;
 157                struct hlist_node *h, *n;
 158                hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
 159                        if (!f->is_static)
 160                                fdb_delete(f);
 161                }
 162        }
 163        spin_unlock_bh(&br->hash_lock);
 164}
 165
 166/* Flush all entries refering to a specific port.
 167 * if do_all is set also flush static entries
 168 */
 169void br_fdb_delete_by_port(struct net_bridge *br,
 170                           const struct net_bridge_port *p,
 171                           int do_all)
 172{
 173        int i;
 174
 175        spin_lock_bh(&br->hash_lock);
 176        for (i = 0; i < BR_HASH_SIZE; i++) {
 177                struct hlist_node *h, *g;
 178
 179                hlist_for_each_safe(h, g, &br->hash[i]) {
 180                        struct net_bridge_fdb_entry *f
 181                                = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
 182                        if (f->dst != p)
 183                                continue;
 184
 185                        if (f->is_static && !do_all)
 186                                continue;
 187                        /*
 188                         * if multiple ports all have the same device address
 189                         * then when one port is deleted, assign
 190                         * the local entry to other port
 191                         */
 192                        if (f->is_local) {
 193                                struct net_bridge_port *op;
 194                                list_for_each_entry(op, &br->port_list, list) {
 195                                        if (op != p &&
 196                                            !compare_ether_addr(op->dev->dev_addr,
 197                                                                f->addr.addr)) {
 198                                                f->dst = op;
 199                                                goto skip_delete;
 200                                        }
 201                                }
 202                        }
 203
 204                        fdb_delete(f);
 205                skip_delete: ;
 206                }
 207        }
 208        spin_unlock_bh(&br->hash_lock);
 209}
 210
 211/* No locking or refcounting, assumes caller has no preempt (rcu_read_lock) */
 212struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
 213                                          const unsigned char *addr)
 214{
 215        struct hlist_node *h;
 216        struct net_bridge_fdb_entry *fdb;
 217
 218        hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
 219                if (!compare_ether_addr(fdb->addr.addr, addr)) {
 220                        if (unlikely(has_expired(br, fdb)))
 221                                break;
 222                        return fdb;
 223                }
 224        }
 225
 226        return NULL;
 227}
 228
 229/* Interface used by ATM hook that keeps a ref count */
 230struct net_bridge_fdb_entry *br_fdb_get(struct net_bridge *br,
 231                                        unsigned char *addr)
 232{
 233        struct net_bridge_fdb_entry *fdb;
 234
 235        rcu_read_lock();
 236        fdb = __br_fdb_get(br, addr);
 237        if (fdb && !atomic_inc_not_zero(&fdb->use_count))
 238                fdb = NULL;
 239        rcu_read_unlock();
 240        return fdb;
 241}
 242
 243static void fdb_rcu_free(struct rcu_head *head)
 244{
 245        struct net_bridge_fdb_entry *ent
 246                = container_of(head, struct net_bridge_fdb_entry, rcu);
 247        kmem_cache_free(br_fdb_cache, ent);
 248}
 249
 250/* Set entry up for deletion with RCU  */
 251void br_fdb_put(struct net_bridge_fdb_entry *ent)
 252{
 253        if (atomic_dec_and_test(&ent->use_count))
 254                call_rcu(&ent->rcu, fdb_rcu_free);
 255}
 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                atomic_set(&fdb->use_count, 1);
 330                hlist_add_head_rcu(&fdb->hlist, head);
 331
 332                fdb->dst = source;
 333                fdb->is_local = is_local;
 334                fdb->is_static = is_local;
 335                fdb->ageing_timer = jiffies;
 336        }
 337        return fdb;
 338}
 339
 340static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
 341                  const unsigned char *addr)
 342{
 343        struct hlist_head *head = &br->hash[br_mac_hash(addr)];
 344        struct net_bridge_fdb_entry *fdb;
 345
 346        if (!is_valid_ether_addr(addr))
 347                return -EINVAL;
 348
 349        fdb = fdb_find(head, addr);
 350        if (fdb) {
 351                /* it is okay to have multiple ports with same
 352                 * address, just use the first one.
 353                 */
 354                if (fdb->is_local)
 355                        return 0;
 356
 357                printk(KERN_WARNING "%s adding interface 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
 369int 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
 380void 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                                printk(KERN_WARNING "%s: received packet 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
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.