br_fdb.c 8.6 KB

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