Merge branch 'next-i2c' of git://git.fluff.org/bjdooks/linux
[pandora-kernel.git] / net / bridge / br_fdb.c
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 <linux/slab.h>
24 #include <linux/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 static void fdb_notify(const struct net_bridge_fdb_entry *, int);
32
33 static u32 fdb_salt __read_mostly;
34
35 int __init br_fdb_init(void)
36 {
37         br_fdb_cache = kmem_cache_create("bridge_fdb_cache",
38                                          sizeof(struct net_bridge_fdb_entry),
39                                          0,
40                                          SLAB_HWCACHE_ALIGN, NULL);
41         if (!br_fdb_cache)
42                 return -ENOMEM;
43
44         get_random_bytes(&fdb_salt, sizeof(fdb_salt));
45         return 0;
46 }
47
48 void br_fdb_fini(void)
49 {
50         kmem_cache_destroy(br_fdb_cache);
51 }
52
53
54 /* if topology_changing then use forward_delay (default 15 sec)
55  * otherwise keep longer (default 5 minutes)
56  */
57 static inline unsigned long hold_time(const struct net_bridge *br)
58 {
59         return br->topology_change ? br->forward_delay : br->ageing_time;
60 }
61
62 static inline int has_expired(const struct net_bridge *br,
63                                   const struct net_bridge_fdb_entry *fdb)
64 {
65         return !fdb->is_static &&
66                 time_before_eq(fdb->updated + hold_time(br), jiffies);
67 }
68
69 static inline int br_mac_hash(const unsigned char *mac)
70 {
71         /* use 1 byte of OUI cnd 3 bytes of NIC */
72         u32 key = get_unaligned((u32 *)(mac + 2));
73         return jhash_1word(key, fdb_salt) & (BR_HASH_SIZE - 1);
74 }
75
76 static void fdb_rcu_free(struct rcu_head *head)
77 {
78         struct net_bridge_fdb_entry *ent
79                 = container_of(head, struct net_bridge_fdb_entry, rcu);
80         kmem_cache_free(br_fdb_cache, ent);
81 }
82
83 static inline void fdb_delete(struct net_bridge_fdb_entry *f)
84 {
85         fdb_notify(f, RTM_DELNEIGH);
86         hlist_del_rcu(&f->hlist);
87         call_rcu(&f->rcu, fdb_rcu_free);
88 }
89
90 void br_fdb_changeaddr(struct net_bridge_port *p, const unsigned char *newaddr)
91 {
92         struct net_bridge *br = p->br;
93         int i;
94
95         spin_lock_bh(&br->hash_lock);
96
97         /* Search all chains since old address/hash is unknown */
98         for (i = 0; i < BR_HASH_SIZE; i++) {
99                 struct hlist_node *h;
100                 hlist_for_each(h, &br->hash[i]) {
101                         struct net_bridge_fdb_entry *f;
102
103                         f = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
104                         if (f->dst == p && f->is_local) {
105                                 /* maybe another port has same hw addr? */
106                                 struct net_bridge_port *op;
107                                 list_for_each_entry(op, &br->port_list, list) {
108                                         if (op != p &&
109                                             !compare_ether_addr(op->dev->dev_addr,
110                                                                 f->addr.addr)) {
111                                                 f->dst = op;
112                                                 goto insert;
113                                         }
114                                 }
115
116                                 /* delete old one */
117                                 fdb_delete(f);
118                                 goto insert;
119                         }
120                 }
121         }
122  insert:
123         /* insert new address,  may fail if invalid address or dup. */
124         fdb_insert(br, p, newaddr);
125
126         spin_unlock_bh(&br->hash_lock);
127 }
128
129 void br_fdb_cleanup(unsigned long _data)
130 {
131         struct net_bridge *br = (struct net_bridge *)_data;
132         unsigned long delay = hold_time(br);
133         unsigned long next_timer = jiffies + br->ageing_time;
134         int i;
135
136         spin_lock_bh(&br->hash_lock);
137         for (i = 0; i < BR_HASH_SIZE; i++) {
138                 struct net_bridge_fdb_entry *f;
139                 struct hlist_node *h, *n;
140
141                 hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
142                         unsigned long this_timer;
143                         if (f->is_static)
144                                 continue;
145                         this_timer = f->updated + delay;
146                         if (time_before_eq(this_timer, jiffies))
147                                 fdb_delete(f);
148                         else if (time_before(this_timer, next_timer))
149                                 next_timer = this_timer;
150                 }
151         }
152         spin_unlock_bh(&br->hash_lock);
153
154         mod_timer(&br->gc_timer, round_jiffies_up(next_timer));
155 }
156
157 /* Completely flush all dynamic entries in forwarding database.*/
158 void br_fdb_flush(struct net_bridge *br)
159 {
160         int i;
161
162         spin_lock_bh(&br->hash_lock);
163         for (i = 0; i < BR_HASH_SIZE; i++) {
164                 struct net_bridge_fdb_entry *f;
165                 struct hlist_node *h, *n;
166                 hlist_for_each_entry_safe(f, h, n, &br->hash[i], hlist) {
167                         if (!f->is_static)
168                                 fdb_delete(f);
169                 }
170         }
171         spin_unlock_bh(&br->hash_lock);
172 }
173
174 /* Flush all entries referring to a specific port.
175  * if do_all is set also flush static entries
176  */
177 void br_fdb_delete_by_port(struct net_bridge *br,
178                            const struct net_bridge_port *p,
179                            int do_all)
180 {
181         int i;
182
183         spin_lock_bh(&br->hash_lock);
184         for (i = 0; i < BR_HASH_SIZE; i++) {
185                 struct hlist_node *h, *g;
186
187                 hlist_for_each_safe(h, g, &br->hash[i]) {
188                         struct net_bridge_fdb_entry *f
189                                 = hlist_entry(h, struct net_bridge_fdb_entry, hlist);
190                         if (f->dst != p)
191                                 continue;
192
193                         if (f->is_static && !do_all)
194                                 continue;
195                         /*
196                          * if multiple ports all have the same device address
197                          * then when one port is deleted, assign
198                          * the local entry to other port
199                          */
200                         if (f->is_local) {
201                                 struct net_bridge_port *op;
202                                 list_for_each_entry(op, &br->port_list, list) {
203                                         if (op != p &&
204                                             !compare_ether_addr(op->dev->dev_addr,
205                                                                 f->addr.addr)) {
206                                                 f->dst = op;
207                                                 goto skip_delete;
208                                         }
209                                 }
210                         }
211
212                         fdb_delete(f);
213                 skip_delete: ;
214                 }
215         }
216         spin_unlock_bh(&br->hash_lock);
217 }
218
219 /* No locking or refcounting, assumes caller has rcu_read_lock */
220 struct net_bridge_fdb_entry *__br_fdb_get(struct net_bridge *br,
221                                           const unsigned char *addr)
222 {
223         struct hlist_node *h;
224         struct net_bridge_fdb_entry *fdb;
225
226         hlist_for_each_entry_rcu(fdb, h, &br->hash[br_mac_hash(addr)], hlist) {
227                 if (!compare_ether_addr(fdb->addr.addr, addr)) {
228                         if (unlikely(has_expired(br, fdb)))
229                                 break;
230                         return fdb;
231                 }
232         }
233
234         return NULL;
235 }
236
237 #if defined(CONFIG_ATM_LANE) || defined(CONFIG_ATM_LANE_MODULE)
238 /* Interface used by ATM LANE hook to test
239  * if an addr is on some other bridge port */
240 int br_fdb_test_addr(struct net_device *dev, unsigned char *addr)
241 {
242         struct net_bridge_fdb_entry *fdb;
243         struct net_bridge_port *port;
244         int ret;
245
246         rcu_read_lock();
247         port = br_port_get_rcu(dev);
248         if (!port)
249                 ret = 0;
250         else {
251                 fdb = __br_fdb_get(port->br, addr);
252                 ret = fdb && fdb->dst->dev != dev &&
253                         fdb->dst->state == BR_STATE_FORWARDING;
254         }
255         rcu_read_unlock();
256
257         return ret;
258 }
259 #endif /* CONFIG_ATM_LANE */
260
261 /*
262  * Fill buffer with forwarding table records in
263  * the API format.
264  */
265 int br_fdb_fillbuf(struct net_bridge *br, void *buf,
266                    unsigned long maxnum, unsigned long skip)
267 {
268         struct __fdb_entry *fe = buf;
269         int i, num = 0;
270         struct hlist_node *h;
271         struct net_bridge_fdb_entry *f;
272
273         memset(buf, 0, maxnum*sizeof(struct __fdb_entry));
274
275         rcu_read_lock();
276         for (i = 0; i < BR_HASH_SIZE; i++) {
277                 hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) {
278                         if (num >= maxnum)
279                                 goto out;
280
281                         if (has_expired(br, f))
282                                 continue;
283
284                         if (skip) {
285                                 --skip;
286                                 continue;
287                         }
288
289                         /* convert from internal format to API */
290                         memcpy(fe->mac_addr, f->addr.addr, ETH_ALEN);
291
292                         /* due to ABI compat need to split into hi/lo */
293                         fe->port_no = f->dst->port_no;
294                         fe->port_hi = f->dst->port_no >> 8;
295
296                         fe->is_local = f->is_local;
297                         if (!f->is_static)
298                                 fe->ageing_timer_value = jiffies_to_clock_t(jiffies - f->updated);
299                         ++fe;
300                         ++num;
301                 }
302         }
303
304  out:
305         rcu_read_unlock();
306
307         return num;
308 }
309
310 static struct net_bridge_fdb_entry *fdb_find(struct hlist_head *head,
311                                              const unsigned char *addr)
312 {
313         struct hlist_node *h;
314         struct net_bridge_fdb_entry *fdb;
315
316         hlist_for_each_entry(fdb, h, head, hlist) {
317                 if (!compare_ether_addr(fdb->addr.addr, addr))
318                         return fdb;
319         }
320         return NULL;
321 }
322
323 static struct net_bridge_fdb_entry *fdb_find_rcu(struct hlist_head *head,
324                                                  const unsigned char *addr)
325 {
326         struct hlist_node *h;
327         struct net_bridge_fdb_entry *fdb;
328
329         hlist_for_each_entry_rcu(fdb, h, head, hlist) {
330                 if (!compare_ether_addr(fdb->addr.addr, addr))
331                         return fdb;
332         }
333         return NULL;
334 }
335
336 static struct net_bridge_fdb_entry *fdb_create(struct hlist_head *head,
337                                                struct net_bridge_port *source,
338                                                const unsigned char *addr)
339 {
340         struct net_bridge_fdb_entry *fdb;
341
342         fdb = kmem_cache_alloc(br_fdb_cache, GFP_ATOMIC);
343         if (fdb) {
344                 memcpy(fdb->addr.addr, addr, ETH_ALEN);
345                 fdb->dst = source;
346                 fdb->is_local = 0;
347                 fdb->is_static = 0;
348                 fdb->updated = fdb->used = jiffies;
349                 hlist_add_head_rcu(&fdb->hlist, head);
350                 fdb_notify(fdb, RTM_NEWNEIGH);
351         }
352         return fdb;
353 }
354
355 static int fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
356                   const unsigned char *addr)
357 {
358         struct hlist_head *head = &br->hash[br_mac_hash(addr)];
359         struct net_bridge_fdb_entry *fdb;
360
361         if (!is_valid_ether_addr(addr))
362                 return -EINVAL;
363
364         fdb = fdb_find(head, addr);
365         if (fdb) {
366                 /* it is okay to have multiple ports with same
367                  * address, just use the first one.
368                  */
369                 if (fdb->is_local)
370                         return 0;
371                 br_warn(br, "adding interface %s with same address "
372                        "as a received packet\n",
373                        source->dev->name);
374                 fdb_delete(fdb);
375         }
376
377         fdb = fdb_create(head, source, addr);
378         if (!fdb)
379                 return -ENOMEM;
380
381         fdb->is_local = fdb->is_static = 1;
382         return 0;
383 }
384
385 /* Add entry for local address of interface */
386 int br_fdb_insert(struct net_bridge *br, struct net_bridge_port *source,
387                   const unsigned char *addr)
388 {
389         int ret;
390
391         spin_lock_bh(&br->hash_lock);
392         ret = fdb_insert(br, source, addr);
393         spin_unlock_bh(&br->hash_lock);
394         return ret;
395 }
396
397 void br_fdb_update(struct net_bridge *br, struct net_bridge_port *source,
398                    const unsigned char *addr)
399 {
400         struct hlist_head *head = &br->hash[br_mac_hash(addr)];
401         struct net_bridge_fdb_entry *fdb;
402
403         /* some users want to always flood. */
404         if (hold_time(br) == 0)
405                 return;
406
407         /* ignore packets unless we are using this port */
408         if (!(source->state == BR_STATE_LEARNING ||
409               source->state == BR_STATE_FORWARDING))
410                 return;
411
412         fdb = fdb_find_rcu(head, addr);
413         if (likely(fdb)) {
414                 /* attempt to update an entry for a local interface */
415                 if (unlikely(fdb->is_local)) {
416                         if (net_ratelimit())
417                                 br_warn(br, "received packet on %s with "
418                                         "own address as source address\n",
419                                         source->dev->name);
420                 } else {
421                         /* fastpath: update of existing entry */
422                         fdb->dst = source;
423                         fdb->updated = jiffies;
424                 }
425         } else {
426                 spin_lock(&br->hash_lock);
427                 if (likely(!fdb_find(head, addr)))
428                         fdb_create(head, source, addr);
429
430                 /* else  we lose race and someone else inserts
431                  * it first, don't bother updating
432                  */
433                 spin_unlock(&br->hash_lock);
434         }
435 }
436
437 static int fdb_to_nud(const struct net_bridge_fdb_entry *fdb)
438 {
439         if (fdb->is_local)
440                 return NUD_PERMANENT;
441         else if (fdb->is_static)
442                 return NUD_NOARP;
443         else if (has_expired(fdb->dst->br, fdb))
444                 return NUD_STALE;
445         else
446                 return NUD_REACHABLE;
447 }
448
449 static int fdb_fill_info(struct sk_buff *skb,
450                          const struct net_bridge_fdb_entry *fdb,
451                          u32 pid, u32 seq, int type, unsigned int flags)
452 {
453         unsigned long now = jiffies;
454         struct nda_cacheinfo ci;
455         struct nlmsghdr *nlh;
456         struct ndmsg *ndm;
457
458         nlh = nlmsg_put(skb, pid, seq, type, sizeof(*ndm), flags);
459         if (nlh == NULL)
460                 return -EMSGSIZE;
461
462
463         ndm = nlmsg_data(nlh);
464         ndm->ndm_family  = AF_BRIDGE;
465         ndm->ndm_pad1    = 0;
466         ndm->ndm_pad2    = 0;
467         ndm->ndm_flags   = 0;
468         ndm->ndm_type    = 0;
469         ndm->ndm_ifindex = fdb->dst->dev->ifindex;
470         ndm->ndm_state   = fdb_to_nud(fdb);
471
472         NLA_PUT(skb, NDA_LLADDR, ETH_ALEN, &fdb->addr);
473
474         ci.ndm_used      = jiffies_to_clock_t(now - fdb->used);
475         ci.ndm_confirmed = 0;
476         ci.ndm_updated   = jiffies_to_clock_t(now - fdb->updated);
477         ci.ndm_refcnt    = 0;
478         NLA_PUT(skb, NDA_CACHEINFO, sizeof(ci), &ci);
479
480         return nlmsg_end(skb, nlh);
481
482 nla_put_failure:
483         nlmsg_cancel(skb, nlh);
484         return -EMSGSIZE;
485 }
486
487 static inline size_t fdb_nlmsg_size(void)
488 {
489         return NLMSG_ALIGN(sizeof(struct ndmsg))
490                 + nla_total_size(ETH_ALEN) /* NDA_LLADDR */
491                 + nla_total_size(sizeof(struct nda_cacheinfo));
492 }
493
494 static void fdb_notify(const struct net_bridge_fdb_entry *fdb, int type)
495 {
496         struct net *net = dev_net(fdb->dst->dev);
497         struct sk_buff *skb;
498         int err = -ENOBUFS;
499
500         skb = nlmsg_new(fdb_nlmsg_size(), GFP_ATOMIC);
501         if (skb == NULL)
502                 goto errout;
503
504         err = fdb_fill_info(skb, fdb, 0, 0, type, 0);
505         if (err < 0) {
506                 /* -EMSGSIZE implies BUG in fdb_nlmsg_size() */
507                 WARN_ON(err == -EMSGSIZE);
508                 kfree_skb(skb);
509                 goto errout;
510         }
511         rtnl_notify(skb, net, 0, RTNLGRP_NEIGH, NULL, GFP_ATOMIC);
512         return;
513 errout:
514         if (err < 0)
515                 rtnl_set_sk_err(net, RTNLGRP_NEIGH, err);
516 }
517
518 /* Dump information about entries, in response to GETNEIGH */
519 int br_fdb_dump(struct sk_buff *skb, struct netlink_callback *cb)
520 {
521         struct net *net = sock_net(skb->sk);
522         struct net_device *dev;
523         int idx = 0;
524
525         rcu_read_lock();
526         for_each_netdev_rcu(net, dev) {
527                 struct net_bridge *br = netdev_priv(dev);
528                 int i;
529
530                 if (!(dev->priv_flags & IFF_EBRIDGE))
531                         continue;
532
533                 for (i = 0; i < BR_HASH_SIZE; i++) {
534                         struct hlist_node *h;
535                         struct net_bridge_fdb_entry *f;
536
537                         hlist_for_each_entry_rcu(f, h, &br->hash[i], hlist) {
538                                 if (idx < cb->args[0])
539                                         goto skip;
540
541                                 if (fdb_fill_info(skb, f,
542                                                   NETLINK_CB(cb->skb).pid,
543                                                   cb->nlh->nlmsg_seq,
544                                                   RTM_NEWNEIGH,
545                                                   NLM_F_MULTI) < 0)
546                                         break;
547 skip:
548                                 ++idx;
549                         }
550                 }
551         }
552         rcu_read_unlock();
553
554         cb->args[0] = idx;
555
556         return skb->len;
557 }
558
559 /* Create new static fdb entry */
560 static int fdb_add_entry(struct net_bridge_port *source, const __u8 *addr,
561                          __u16 state)
562 {
563         struct net_bridge *br = source->br;
564         struct hlist_head *head = &br->hash[br_mac_hash(addr)];
565         struct net_bridge_fdb_entry *fdb;
566
567         fdb = fdb_find(head, addr);
568         if (fdb)
569                 return -EEXIST;
570
571         fdb = fdb_create(head, source, addr);
572         if (!fdb)
573                 return -ENOMEM;
574
575         if (state & NUD_PERMANENT)
576                 fdb->is_local = fdb->is_static = 1;
577         else if (state & NUD_NOARP)
578                 fdb->is_static = 1;
579         return 0;
580 }
581
582 /* Add new permanent fdb entry with RTM_NEWNEIGH */
583 int br_fdb_add(struct sk_buff *skb, struct nlmsghdr *nlh, void *arg)
584 {
585         struct net *net = sock_net(skb->sk);
586         struct ndmsg *ndm;
587         struct nlattr *tb[NDA_MAX+1];
588         struct net_device *dev;
589         struct net_bridge_port *p;
590         const __u8 *addr;
591         int err;
592
593         ASSERT_RTNL();
594         err = nlmsg_parse(nlh, sizeof(*ndm), tb, NDA_MAX, NULL);
595         if (err < 0)
596                 return err;
597
598         ndm = nlmsg_data(nlh);
599         if (ndm->ndm_ifindex == 0) {
600                 pr_info("bridge: RTM_NEWNEIGH with invalid ifindex\n");
601                 return -EINVAL;
602         }
603
604         dev = __dev_get_by_index(net, ndm->ndm_ifindex);
605         if (dev == NULL) {
606                 pr_info("bridge: RTM_NEWNEIGH with unknown ifindex\n");
607                 return -ENODEV;
608         }
609
610         if (!tb[NDA_LLADDR] || nla_len(tb[NDA_LLADDR]) != ETH_ALEN) {
611                 pr_info("bridge: RTM_NEWNEIGH with invalid address\n");
612                 return -EINVAL;
613         }
614
615         addr = nla_data(tb[NDA_LLADDR]);
616         if (!is_valid_ether_addr(addr)) {
617                 pr_info("bridge: RTM_NEWNEIGH with invalid ether address\n");
618                 return -EINVAL;
619         }
620
621         p = br_port_get_rtnl(dev);
622         if (p == NULL) {
623                 pr_info("bridge: RTM_NEWNEIGH %s not a bridge port\n",
624                         dev->name);
625                 return -EINVAL;
626         }
627
628         spin_lock_bh(&p->br->hash_lock);
629         err = fdb_add_entry(p, addr, ndm->ndm_state);
630         spin_unlock_bh(&p->br->hash_lock);
631
632         return err;
633 }
634
635 static int fdb_delete_by_addr(struct net_bridge_port *p, const u8 *addr)
636 {
637         struct net_bridge *br = p->br;
638         struct hlist_head *head = &br->hash[br_mac_hash(addr)];
639         struct net_bridge_fdb_entry *fdb;
640
641         fdb = fdb_find(head, addr);
642         if (!fdb)
643                 return -ENOENT;
644
645         fdb_delete(fdb);
646         return 0;
647 }
648
649 /* Remove neighbor entry with RTM_DELNEIGH */
650 int br_fdb_delete(struct sk_buff *skb, struct nlmsghdr *nlh, void *arg)
651 {
652         struct net *net = sock_net(skb->sk);
653         struct ndmsg *ndm;
654         struct net_bridge_port *p;
655         struct nlattr *llattr;
656         const __u8 *addr;
657         struct net_device *dev;
658         int err;
659
660         ASSERT_RTNL();
661         if (nlmsg_len(nlh) < sizeof(*ndm))
662                 return -EINVAL;
663
664         ndm = nlmsg_data(nlh);
665         if (ndm->ndm_ifindex == 0) {
666                 pr_info("bridge: RTM_DELNEIGH with invalid ifindex\n");
667                 return -EINVAL;
668         }
669
670         dev = __dev_get_by_index(net, ndm->ndm_ifindex);
671         if (dev == NULL) {
672                 pr_info("bridge: RTM_DELNEIGH with unknown ifindex\n");
673                 return -ENODEV;
674         }
675
676         llattr = nlmsg_find_attr(nlh, sizeof(*ndm), NDA_LLADDR);
677         if (llattr == NULL || nla_len(llattr) != ETH_ALEN) {
678                 pr_info("bridge: RTM_DELNEIGH with invalid address\n");
679                 return -EINVAL;
680         }
681
682         addr = nla_data(llattr);
683
684         p = br_port_get_rtnl(dev);
685         if (p == NULL) {
686                 pr_info("bridge: RTM_DELNEIGH %s not a bridge port\n",
687                         dev->name);
688                 return -EINVAL;
689         }
690
691         spin_lock_bh(&p->br->hash_lock);
692         err = fdb_delete_by_addr(p, addr);
693         spin_unlock_bh(&p->br->hash_lock);
694
695         return err;
696 }