blob: dc7c8df40c2c3093c0ec81c7af1fbeeac973ecd9 [file] [log] [blame]
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001/*
Rui Paulo264d9b72009-11-09 23:46:58 +00002 * Copyright (c) 2008, 2009 open80211s Ltd.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01003 * Author: Luis Carlos Cobo <luisca@cozybit.com>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License version 2 as
7 * published by the Free Software Foundation.
8 */
9
10#include <linux/etherdevice.h>
11#include <linux/list.h>
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010012#include <linux/random.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090013#include <linux/slab.h>
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010014#include <linux/spinlock.h>
15#include <linux/string.h>
16#include <net/mac80211.h>
Javier Cardona4777be42011-09-07 17:49:52 -070017#include "wme.h"
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010018#include "ieee80211_i.h"
19#include "mesh.h"
20
21/* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */
22#define INIT_PATHS_SIZE_ORDER 2
23
24/* Keep the mean chain length below this constant */
25#define MEAN_CHAIN_LEN 2
26
Johannes Bergbf7cd942013-02-15 14:40:31 +010027static inline bool mpath_expired(struct mesh_path *mpath)
28{
29 return (mpath->flags & MESH_PATH_ACTIVE) &&
30 time_after(jiffies, mpath->exp_time) &&
31 !(mpath->flags & MESH_PATH_FIXED);
32}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010033
34struct mpath_node {
35 struct hlist_node list;
36 struct rcu_head rcu;
37 /* This indirection allows two different tables to point to the same
38 * mesh_path structure, useful when resizing
39 */
40 struct mesh_path *mpath;
41};
42
Johannes Berg349eb8c2011-05-14 11:56:16 +020043static struct mesh_table __rcu *mesh_paths;
44static struct mesh_table __rcu *mpp_paths; /* Store paths for MPP&MAP */
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010045
Johannes Bergf5ea9122009-08-07 16:17:38 +020046int mesh_paths_generation;
Johannes Berg6b86bd62011-05-12 13:38:50 +020047
48/* This lock will have the grow table function as writer and add / delete nodes
Javier Cardona239289e2011-08-29 13:23:09 -070049 * as readers. RCU provides sufficient protection only when reading the table
50 * (i.e. doing lookups). Adding or adding or removing nodes requires we take
51 * the read lock or we risk operating on an old table. The write lock is only
52 * needed when modifying the number of buckets a table.
Johannes Berg6b86bd62011-05-12 13:38:50 +020053 */
54static DEFINE_RWLOCK(pathtbl_resize_lock);
55
56
Johannes Berg349eb8c2011-05-14 11:56:16 +020057static inline struct mesh_table *resize_dereference_mesh_paths(void)
58{
59 return rcu_dereference_protected(mesh_paths,
60 lockdep_is_held(&pathtbl_resize_lock));
61}
62
63static inline struct mesh_table *resize_dereference_mpp_paths(void)
64{
65 return rcu_dereference_protected(mpp_paths,
66 lockdep_is_held(&pathtbl_resize_lock));
67}
68
69/*
70 * CAREFUL -- "tbl" must not be an expression,
71 * in particular not an rcu_dereference(), since
72 * it's used twice. So it is illegal to do
73 * for_each_mesh_entry(rcu_dereference(...), ...)
74 */
Sasha Levinb67bfe02013-02-27 17:06:00 -080075#define for_each_mesh_entry(tbl, node, i) \
Johannes Berg349eb8c2011-05-14 11:56:16 +020076 for (i = 0; i <= tbl->hash_mask; i++) \
Sasha Levinb67bfe02013-02-27 17:06:00 -080077 hlist_for_each_entry_rcu(node, &tbl->hash_buckets[i], list)
Johannes Berg349eb8c2011-05-14 11:56:16 +020078
79
Johannes Berg6b86bd62011-05-12 13:38:50 +020080static struct mesh_table *mesh_table_alloc(int size_order)
81{
82 int i;
83 struct mesh_table *newtbl;
84
Javier Cardonad676ff42011-05-17 16:13:34 -070085 newtbl = kmalloc(sizeof(struct mesh_table), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020086 if (!newtbl)
87 return NULL;
88
89 newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) *
Javier Cardonad676ff42011-05-17 16:13:34 -070090 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020091
92 if (!newtbl->hash_buckets) {
93 kfree(newtbl);
94 return NULL;
95 }
96
97 newtbl->hashwlock = kmalloc(sizeof(spinlock_t) *
Javier Cardonad676ff42011-05-17 16:13:34 -070098 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020099 if (!newtbl->hashwlock) {
100 kfree(newtbl->hash_buckets);
101 kfree(newtbl);
102 return NULL;
103 }
104
105 newtbl->size_order = size_order;
106 newtbl->hash_mask = (1 << size_order) - 1;
107 atomic_set(&newtbl->entries, 0);
108 get_random_bytes(&newtbl->hash_rnd,
109 sizeof(newtbl->hash_rnd));
110 for (i = 0; i <= newtbl->hash_mask; i++)
111 spin_lock_init(&newtbl->hashwlock[i]);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700112 spin_lock_init(&newtbl->gates_lock);
Johannes Berg6b86bd62011-05-12 13:38:50 +0200113
114 return newtbl;
115}
116
Javier Cardona18889232009-08-10 12:15:52 -0700117static void __mesh_table_free(struct mesh_table *tbl)
118{
119 kfree(tbl->hash_buckets);
120 kfree(tbl->hashwlock);
121 kfree(tbl);
122}
123
Johannes Berg6b86bd62011-05-12 13:38:50 +0200124static void mesh_table_free(struct mesh_table *tbl, bool free_leafs)
Javier Cardona18889232009-08-10 12:15:52 -0700125{
126 struct hlist_head *mesh_hash;
127 struct hlist_node *p, *q;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700128 struct mpath_node *gate;
Javier Cardona18889232009-08-10 12:15:52 -0700129 int i;
130
131 mesh_hash = tbl->hash_buckets;
132 for (i = 0; i <= tbl->hash_mask; i++) {
Javier Cardona9b84b8082011-05-03 16:57:16 -0700133 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700134 hlist_for_each_safe(p, q, &mesh_hash[i]) {
135 tbl->free_node(p, free_leafs);
136 atomic_dec(&tbl->entries);
137 }
Javier Cardona9b84b8082011-05-03 16:57:16 -0700138 spin_unlock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700139 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700140 if (free_leafs) {
141 spin_lock_bh(&tbl->gates_lock);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800142 hlist_for_each_entry_safe(gate, q,
Javier Cardona5ee68e52011-08-09 16:45:08 -0700143 tbl->known_gates, list) {
144 hlist_del(&gate->list);
145 kfree(gate);
146 }
147 kfree(tbl->known_gates);
148 spin_unlock_bh(&tbl->gates_lock);
149 }
150
Javier Cardona18889232009-08-10 12:15:52 -0700151 __mesh_table_free(tbl);
152}
153
cozybit Inca3e6b122011-04-13 11:10:28 -0700154static int mesh_table_grow(struct mesh_table *oldtbl,
Johannes Berg6b86bd62011-05-12 13:38:50 +0200155 struct mesh_table *newtbl)
Javier Cardona18889232009-08-10 12:15:52 -0700156{
Javier Cardona18889232009-08-10 12:15:52 -0700157 struct hlist_head *oldhash;
158 struct hlist_node *p, *q;
159 int i;
160
cozybit Inca3e6b122011-04-13 11:10:28 -0700161 if (atomic_read(&oldtbl->entries)
162 < oldtbl->mean_chain_len * (oldtbl->hash_mask + 1))
163 return -EAGAIN;
Javier Cardona18889232009-08-10 12:15:52 -0700164
cozybit Inca3e6b122011-04-13 11:10:28 -0700165 newtbl->free_node = oldtbl->free_node;
166 newtbl->mean_chain_len = oldtbl->mean_chain_len;
167 newtbl->copy_node = oldtbl->copy_node;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700168 newtbl->known_gates = oldtbl->known_gates;
cozybit Inca3e6b122011-04-13 11:10:28 -0700169 atomic_set(&newtbl->entries, atomic_read(&oldtbl->entries));
Javier Cardona18889232009-08-10 12:15:52 -0700170
cozybit Inca3e6b122011-04-13 11:10:28 -0700171 oldhash = oldtbl->hash_buckets;
172 for (i = 0; i <= oldtbl->hash_mask; i++)
Javier Cardona18889232009-08-10 12:15:52 -0700173 hlist_for_each(p, &oldhash[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700174 if (oldtbl->copy_node(p, newtbl) < 0)
Javier Cardona18889232009-08-10 12:15:52 -0700175 goto errcopy;
176
cozybit Inca3e6b122011-04-13 11:10:28 -0700177 return 0;
Javier Cardona18889232009-08-10 12:15:52 -0700178
179errcopy:
180 for (i = 0; i <= newtbl->hash_mask; i++) {
181 hlist_for_each_safe(p, q, &newtbl->hash_buckets[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700182 oldtbl->free_node(p, 0);
Javier Cardona18889232009-08-10 12:15:52 -0700183 }
cozybit Inca3e6b122011-04-13 11:10:28 -0700184 return -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700185}
186
Johannes Berg4a3cb702013-02-12 16:43:19 +0100187static u32 mesh_table_hash(const u8 *addr, struct ieee80211_sub_if_data *sdata,
Johannes Berg6b86bd62011-05-12 13:38:50 +0200188 struct mesh_table *tbl)
189{
190 /* Use last four bytes of hw addr and interface index as hash index */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100191 return jhash_2words(*(u32 *)(addr+2), sdata->dev->ifindex,
192 tbl->hash_rnd) & tbl->hash_mask;
Johannes Berg6b86bd62011-05-12 13:38:50 +0200193}
Johannes Bergf5ea9122009-08-07 16:17:38 +0200194
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100195
196/**
197 *
198 * mesh_path_assign_nexthop - update mesh path next hop
199 *
200 * @mpath: mesh path to update
201 * @sta: next hop to assign
202 *
203 * Locking: mpath->state_lock must be held when calling this function
204 */
205void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta)
206{
Javier Cardona10c836d2009-07-09 14:42:16 -0700207 struct sk_buff *skb;
208 struct ieee80211_hdr *hdr;
Javier Cardona10c836d2009-07-09 14:42:16 -0700209 unsigned long flags;
210
Johannes Bergd0709a62008-02-25 16:27:46 +0100211 rcu_assign_pointer(mpath->next_hop, sta);
Javier Cardona10c836d2009-07-09 14:42:16 -0700212
Javier Cardona10c836d2009-07-09 14:42:16 -0700213 spin_lock_irqsave(&mpath->frame_queue.lock, flags);
Thomas Pedersenb22bd522012-08-09 18:15:39 -0700214 skb_queue_walk(&mpath->frame_queue, skb) {
Javier Cardona10c836d2009-07-09 14:42:16 -0700215 hdr = (struct ieee80211_hdr *) skb->data;
216 memcpy(hdr->addr1, sta->sta.addr, ETH_ALEN);
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800217 memcpy(hdr->addr2, mpath->sdata->vif.addr, ETH_ALEN);
Marco Porsch3f52b7e2013-01-30 18:14:08 +0100218 ieee80211_mps_set_frame_flags(sta->sdata, sta, hdr);
Javier Cardona10c836d2009-07-09 14:42:16 -0700219 }
220
Javier Cardona10c836d2009-07-09 14:42:16 -0700221 spin_unlock_irqrestore(&mpath->frame_queue.lock, flags);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100222}
223
Javier Cardona5ee68e52011-08-09 16:45:08 -0700224static void prepare_for_gate(struct sk_buff *skb, char *dst_addr,
225 struct mesh_path *gate_mpath)
226{
227 struct ieee80211_hdr *hdr;
228 struct ieee80211s_hdr *mshdr;
229 int mesh_hdrlen, hdrlen;
230 char *next_hop;
231
232 hdr = (struct ieee80211_hdr *) skb->data;
233 hdrlen = ieee80211_hdrlen(hdr->frame_control);
234 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
235
236 if (!(mshdr->flags & MESH_FLAGS_AE)) {
237 /* size of the fixed part of the mesh header */
238 mesh_hdrlen = 6;
239
240 /* make room for the two extended addresses */
241 skb_push(skb, 2 * ETH_ALEN);
242 memmove(skb->data, hdr, hdrlen + mesh_hdrlen);
243
244 hdr = (struct ieee80211_hdr *) skb->data;
245
246 /* we preserve the previous mesh header and only add
247 * the new addreses */
248 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
249 mshdr->flags = MESH_FLAGS_AE_A5_A6;
250 memcpy(mshdr->eaddr1, hdr->addr3, ETH_ALEN);
251 memcpy(mshdr->eaddr2, hdr->addr4, ETH_ALEN);
252 }
253
254 /* update next hop */
255 hdr = (struct ieee80211_hdr *) skb->data;
256 rcu_read_lock();
257 next_hop = rcu_dereference(gate_mpath->next_hop)->sta.addr;
258 memcpy(hdr->addr1, next_hop, ETH_ALEN);
259 rcu_read_unlock();
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800260 memcpy(hdr->addr2, gate_mpath->sdata->vif.addr, ETH_ALEN);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700261 memcpy(hdr->addr3, dst_addr, ETH_ALEN);
262}
263
264/**
265 *
266 * mesh_path_move_to_queue - Move or copy frames from one mpath queue to another
267 *
268 * This function is used to transfer or copy frames from an unresolved mpath to
269 * a gate mpath. The function also adds the Address Extension field and
270 * updates the next hop.
271 *
272 * If a frame already has an Address Extension field, only the next hop and
273 * destination addresses are updated.
274 *
275 * The gate mpath must be an active mpath with a valid mpath->next_hop.
276 *
277 * @mpath: An active mpath the frames will be sent to (i.e. the gate)
278 * @from_mpath: The failed mpath
279 * @copy: When true, copy all the frames to the new mpath queue. When false,
280 * move them.
281 */
282static void mesh_path_move_to_queue(struct mesh_path *gate_mpath,
283 struct mesh_path *from_mpath,
284 bool copy)
285{
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700286 struct sk_buff *skb, *fskb, *tmp;
287 struct sk_buff_head failq;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700288 unsigned long flags;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700289
290 BUG_ON(gate_mpath == from_mpath);
291 BUG_ON(!gate_mpath->next_hop);
292
Javier Cardona5ee68e52011-08-09 16:45:08 -0700293 __skb_queue_head_init(&failq);
294
295 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
296 skb_queue_splice_init(&from_mpath->frame_queue, &failq);
297 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
298
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700299 skb_queue_walk_safe(&failq, fskb, tmp) {
300 if (skb_queue_len(&gate_mpath->frame_queue) >=
301 MESH_FRAME_QUEUE_LEN) {
302 mpath_dbg(gate_mpath->sdata, "mpath queue full!\n");
303 break;
John W. Linville817a53d2011-08-24 15:12:41 -0400304 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700305
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700306 skb = skb_copy(fskb, GFP_ATOMIC);
307 if (WARN_ON(!skb))
308 break;
309
Javier Cardona5ee68e52011-08-09 16:45:08 -0700310 prepare_for_gate(skb, gate_mpath->dst, gate_mpath);
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700311 skb_queue_tail(&gate_mpath->frame_queue, skb);
312
313 if (copy)
314 continue;
315
316 __skb_unlink(fskb, &failq);
317 kfree_skb(fskb);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700318 }
319
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200320 mpath_dbg(gate_mpath->sdata, "Mpath queue for gate %pM has %d frames\n",
321 gate_mpath->dst, skb_queue_len(&gate_mpath->frame_queue));
Javier Cardona5ee68e52011-08-09 16:45:08 -0700322
323 if (!copy)
324 return;
325
326 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
327 skb_queue_splice(&failq, &from_mpath->frame_queue);
328 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
329}
330
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100331
Johannes Berg4a3cb702013-02-12 16:43:19 +0100332static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst,
333 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100334{
335 struct mesh_path *mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100336 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100337 struct mpath_node *node;
338
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200339 bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
Sasha Levinb67bfe02013-02-27 17:06:00 -0800340 hlist_for_each_entry_rcu(node, bucket, list) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100341 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200342 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000343 ether_addr_equal(dst, mpath->dst)) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100344 if (mpath_expired(mpath)) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100345 spin_lock_bh(&mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700346 mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100347 spin_unlock_bh(&mpath->state_lock);
348 }
349 return mpath;
350 }
351 }
352 return NULL;
353}
354
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100355/**
356 * mesh_path_lookup - look up a path in the mesh path table
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100357 * @sdata: local subif
Johannes Bergbf7cd942013-02-15 14:40:31 +0100358 * @dst: hardware address (ETH_ALEN length) of destination
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100359 *
360 * Returns: pointer to the mesh path structure, or NULL if not found
361 *
362 * Locking: must be called within a read rcu section.
363 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100364struct mesh_path *
365mesh_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100366{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800367 return mpath_lookup(rcu_dereference(mesh_paths), dst, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100368}
369
Johannes Bergbf7cd942013-02-15 14:40:31 +0100370struct mesh_path *
371mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst)
YanBo79617de2008-09-22 13:30:32 +0800372{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800373 return mpath_lookup(rcu_dereference(mpp_paths), dst, sdata);
YanBo79617de2008-09-22 13:30:32 +0800374}
375
376
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100377/**
378 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
379 * @idx: index
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200380 * @sdata: local subif, or NULL for all entries
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100381 *
382 * Returns: pointer to the mesh path structure, or NULL if not found.
383 *
384 * Locking: must be called within a read rcu section.
385 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100386struct mesh_path *
387mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100388{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200389 struct mesh_table *tbl = rcu_dereference(mesh_paths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100390 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100391 int i;
392 int j = 0;
393
Sasha Levinb67bfe02013-02-27 17:06:00 -0800394 for_each_mesh_entry(tbl, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200395 if (sdata && node->mpath->sdata != sdata)
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800396 continue;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100397 if (j++ == idx) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100398 if (mpath_expired(node->mpath)) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100399 spin_lock_bh(&node->mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700400 node->mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100401 spin_unlock_bh(&node->mpath->state_lock);
402 }
403 return node->mpath;
404 }
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800405 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100406
407 return NULL;
408}
409
Javier Cardona5ee68e52011-08-09 16:45:08 -0700410/**
Johannes Berg30be52e2011-11-21 11:23:50 +0100411 * mesh_path_add_gate - add the given mpath to a mesh gate to our path table
412 * @mpath: gate path to add to table
Javier Cardona5ee68e52011-08-09 16:45:08 -0700413 */
Johannes Berg30be52e2011-11-21 11:23:50 +0100414int mesh_path_add_gate(struct mesh_path *mpath)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700415{
Johannes Berg30be52e2011-11-21 11:23:50 +0100416 struct mesh_table *tbl;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700417 struct mpath_node *gate, *new_gate;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700418 int err;
419
420 rcu_read_lock();
Johannes Berg30be52e2011-11-21 11:23:50 +0100421 tbl = rcu_dereference(mesh_paths);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700422
Sasha Levinb67bfe02013-02-27 17:06:00 -0800423 hlist_for_each_entry_rcu(gate, tbl->known_gates, list)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700424 if (gate->mpath == mpath) {
425 err = -EEXIST;
426 goto err_rcu;
427 }
428
429 new_gate = kzalloc(sizeof(struct mpath_node), GFP_ATOMIC);
430 if (!new_gate) {
431 err = -ENOMEM;
432 goto err_rcu;
433 }
434
435 mpath->is_gate = true;
436 mpath->sdata->u.mesh.num_gates++;
437 new_gate->mpath = mpath;
438 spin_lock_bh(&tbl->gates_lock);
439 hlist_add_head_rcu(&new_gate->list, tbl->known_gates);
440 spin_unlock_bh(&tbl->gates_lock);
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200441 mpath_dbg(mpath->sdata,
442 "Mesh path: Recorded new gate: %pM. %d known gates\n",
443 mpath->dst, mpath->sdata->u.mesh.num_gates);
Johannes Bergbf7cd942013-02-15 14:40:31 +0100444 err = 0;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700445err_rcu:
446 rcu_read_unlock();
447 return err;
448}
449
450/**
451 * mesh_gate_del - remove a mesh gate from the list of known gates
452 * @tbl: table which holds our list of known gates
453 * @mpath: gate mpath
454 *
Javier Cardona5ee68e52011-08-09 16:45:08 -0700455 * Locking: must be called inside rcu_read_lock() section
456 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100457static void mesh_gate_del(struct mesh_table *tbl, struct mesh_path *mpath)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700458{
459 struct mpath_node *gate;
Sasha Levinb67bfe02013-02-27 17:06:00 -0800460 struct hlist_node *q;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700461
Sasha Levinb67bfe02013-02-27 17:06:00 -0800462 hlist_for_each_entry_safe(gate, q, tbl->known_gates, list) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100463 if (gate->mpath != mpath)
464 continue;
465 spin_lock_bh(&tbl->gates_lock);
466 hlist_del_rcu(&gate->list);
467 kfree_rcu(gate, rcu);
468 spin_unlock_bh(&tbl->gates_lock);
469 mpath->sdata->u.mesh.num_gates--;
470 mpath->is_gate = false;
471 mpath_dbg(mpath->sdata,
472 "Mesh path: Deleted gate: %pM. %d known gates\n",
473 mpath->dst, mpath->sdata->u.mesh.num_gates);
474 break;
475 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700476}
477
478/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700479 * mesh_gate_num - number of gates known to this interface
480 * @sdata: subif data
481 */
482int mesh_gate_num(struct ieee80211_sub_if_data *sdata)
483{
484 return sdata->u.mesh.num_gates;
485}
486
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100487/**
488 * mesh_path_add - allocate and add a new path to the mesh path table
Johannes Bergbf7cd942013-02-15 14:40:31 +0100489 * @dst: destination address of the path (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200490 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100491 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200492 * Returns: 0 on success
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100493 *
494 * State: the initial state of the new path is set to 0
495 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100496int mesh_path_add(struct ieee80211_sub_if_data *sdata, const u8 *dst)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100497{
Javier Cardona18889232009-08-10 12:15:52 -0700498 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
499 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200500 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100501 struct mesh_path *mpath, *new_mpath;
502 struct mpath_node *node, *new_node;
503 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100504 int grow = 0;
505 int err = 0;
506 u32 hash_idx;
507
Joe Perchesb203ca32012-05-08 18:56:52 +0000508 if (ether_addr_equal(dst, sdata->vif.addr))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100509 /* never add ourselves as neighbours */
510 return -ENOTSUPP;
511
512 if (is_multicast_ether_addr(dst))
513 return -ENOTSUPP;
514
Johannes Berg472dbc42008-09-11 00:01:49 +0200515 if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100516 return -ENOSPC;
517
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400518 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700519 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400520 if (!new_mpath)
521 goto err_path_alloc;
522
Javier Cardona18889232009-08-10 12:15:52 -0700523 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400524 if (!new_node)
525 goto err_node_alloc;
Pavel Emelyanovf84e71a2008-05-06 18:46:36 +0400526
Javier Cardona9b84b8082011-05-03 16:57:16 -0700527 read_lock_bh(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100528 memcpy(new_mpath->dst, dst, ETH_ALEN);
Johannes Berge83e6542012-07-13 16:23:07 +0200529 eth_broadcast_addr(new_mpath->rann_snd_addr);
Chun-Yeow Yeoh35bcd592012-04-10 12:31:56 +0800530 new_mpath->is_root = false;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200531 new_mpath->sdata = sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100532 new_mpath->flags = 0;
533 skb_queue_head_init(&new_mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100534 new_node->mpath = new_mpath;
535 new_mpath->timer.data = (unsigned long) new_mpath;
536 new_mpath->timer.function = mesh_path_timer;
537 new_mpath->exp_time = jiffies;
538 spin_lock_init(&new_mpath->state_lock);
539 init_timer(&new_mpath->timer);
540
Johannes Berg349eb8c2011-05-14 11:56:16 +0200541 tbl = resize_dereference_mesh_paths();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100542
Johannes Berg349eb8c2011-05-14 11:56:16 +0200543 hash_idx = mesh_table_hash(dst, sdata, tbl);
544 bucket = &tbl->hash_buckets[hash_idx];
545
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800546 spin_lock(&tbl->hashwlock[hash_idx]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100547
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400548 err = -EEXIST;
Sasha Levinb67bfe02013-02-27 17:06:00 -0800549 hlist_for_each_entry(node, bucket, list) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100550 mpath = node->mpath;
Felix Fietkau888d04d2012-03-01 15:22:09 +0100551 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000552 ether_addr_equal(dst, mpath->dst))
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400553 goto err_exists;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100554 }
555
556 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200557 if (atomic_inc_return(&tbl->entries) >=
558 tbl->mean_chain_len * (tbl->hash_mask + 1))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100559 grow = 1;
560
Johannes Bergf5ea9122009-08-07 16:17:38 +0200561 mesh_paths_generation++;
562
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800563 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700564 read_unlock_bh(&pathtbl_resize_lock);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400565 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700566 set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200567 ieee80211_queue_work(&local->hw, &sdata->work);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100568 }
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400569 return 0;
570
571err_exists:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800572 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700573 read_unlock_bh(&pathtbl_resize_lock);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400574 kfree(new_node);
575err_node_alloc:
576 kfree(new_mpath);
577err_path_alloc:
Johannes Berg472dbc42008-09-11 00:01:49 +0200578 atomic_dec(&sdata->u.mesh.mpaths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100579 return err;
580}
581
Johannes Berg1928eca2011-05-14 11:00:52 +0200582static void mesh_table_free_rcu(struct rcu_head *rcu)
583{
584 struct mesh_table *tbl = container_of(rcu, struct mesh_table, rcu_head);
585
586 mesh_table_free(tbl, false);
587}
588
Javier Cardona18889232009-08-10 12:15:52 -0700589void mesh_mpath_table_grow(void)
590{
591 struct mesh_table *oldtbl, *newtbl;
592
Javier Cardona9b84b8082011-05-03 16:57:16 -0700593 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200594 oldtbl = resize_dereference_mesh_paths();
595 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200596 if (!newtbl)
597 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200598 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700599 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200600 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700601 }
602 rcu_assign_pointer(mesh_paths, newtbl);
Javier Cardona18889232009-08-10 12:15:52 -0700603
Johannes Berg1928eca2011-05-14 11:00:52 +0200604 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
605
606 out:
607 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700608}
609
610void mesh_mpp_table_grow(void)
611{
612 struct mesh_table *oldtbl, *newtbl;
613
Javier Cardona9b84b8082011-05-03 16:57:16 -0700614 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200615 oldtbl = resize_dereference_mpp_paths();
616 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200617 if (!newtbl)
618 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200619 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700620 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200621 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700622 }
623 rcu_assign_pointer(mpp_paths, newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200624 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
Javier Cardona18889232009-08-10 12:15:52 -0700625
Johannes Berg1928eca2011-05-14 11:00:52 +0200626 out:
627 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700628}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100629
Johannes Bergbf7cd942013-02-15 14:40:31 +0100630int mpp_path_add(struct ieee80211_sub_if_data *sdata,
631 const u8 *dst, const u8 *mpp)
YanBo79617de2008-09-22 13:30:32 +0800632{
Javier Cardona18889232009-08-10 12:15:52 -0700633 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
634 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200635 struct mesh_table *tbl;
YanBo79617de2008-09-22 13:30:32 +0800636 struct mesh_path *mpath, *new_mpath;
637 struct mpath_node *node, *new_node;
638 struct hlist_head *bucket;
YanBo79617de2008-09-22 13:30:32 +0800639 int grow = 0;
640 int err = 0;
641 u32 hash_idx;
642
Joe Perchesb203ca32012-05-08 18:56:52 +0000643 if (ether_addr_equal(dst, sdata->vif.addr))
YanBo79617de2008-09-22 13:30:32 +0800644 /* never add ourselves as neighbours */
645 return -ENOTSUPP;
646
647 if (is_multicast_ether_addr(dst))
648 return -ENOTSUPP;
649
650 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700651 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800652 if (!new_mpath)
653 goto err_path_alloc;
654
Javier Cardona18889232009-08-10 12:15:52 -0700655 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800656 if (!new_node)
657 goto err_node_alloc;
658
Javier Cardona9b84b8082011-05-03 16:57:16 -0700659 read_lock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800660 memcpy(new_mpath->dst, dst, ETH_ALEN);
661 memcpy(new_mpath->mpp, mpp, ETH_ALEN);
662 new_mpath->sdata = sdata;
663 new_mpath->flags = 0;
664 skb_queue_head_init(&new_mpath->frame_queue);
665 new_node->mpath = new_mpath;
Thomas Pedersenc61336612011-08-25 10:36:14 -0700666 init_timer(&new_mpath->timer);
YanBo79617de2008-09-22 13:30:32 +0800667 new_mpath->exp_time = jiffies;
668 spin_lock_init(&new_mpath->state_lock);
669
Johannes Berg349eb8c2011-05-14 11:56:16 +0200670 tbl = resize_dereference_mpp_paths();
YanBo79617de2008-09-22 13:30:32 +0800671
Johannes Berg349eb8c2011-05-14 11:56:16 +0200672 hash_idx = mesh_table_hash(dst, sdata, tbl);
673 bucket = &tbl->hash_buckets[hash_idx];
674
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800675 spin_lock(&tbl->hashwlock[hash_idx]);
YanBo79617de2008-09-22 13:30:32 +0800676
677 err = -EEXIST;
Sasha Levinb67bfe02013-02-27 17:06:00 -0800678 hlist_for_each_entry(node, bucket, list) {
YanBo79617de2008-09-22 13:30:32 +0800679 mpath = node->mpath;
Felix Fietkau888d04d2012-03-01 15:22:09 +0100680 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000681 ether_addr_equal(dst, mpath->dst))
YanBo79617de2008-09-22 13:30:32 +0800682 goto err_exists;
683 }
684
685 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200686 if (atomic_inc_return(&tbl->entries) >=
687 tbl->mean_chain_len * (tbl->hash_mask + 1))
YanBo79617de2008-09-22 13:30:32 +0800688 grow = 1;
689
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800690 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700691 read_unlock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800692 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700693 set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200694 ieee80211_queue_work(&local->hw, &sdata->work);
YanBo79617de2008-09-22 13:30:32 +0800695 }
696 return 0;
697
698err_exists:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800699 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700700 read_unlock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800701 kfree(new_node);
702err_node_alloc:
703 kfree(new_mpath);
704err_path_alloc:
705 return err;
706}
707
708
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100709/**
710 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
711 *
712 * @sta: broken peer link
713 *
714 * This function must be called from the rate control algorithm if enough
715 * delivery errors suggest that a peer link is no longer usable.
716 */
717void mesh_plink_broken(struct sta_info *sta)
718{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200719 struct mesh_table *tbl;
Johannes Berg15ff6362009-11-17 13:34:04 +0100720 static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100721 struct mesh_path *mpath;
722 struct mpath_node *node;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200723 struct ieee80211_sub_if_data *sdata = sta->sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100724 int i;
Thomas Pedersen25d49e42011-08-11 19:35:15 -0700725 __le16 reason = cpu_to_le16(WLAN_REASON_MESH_PATH_DEST_UNREACHABLE);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100726
727 rcu_read_lock();
Johannes Berg349eb8c2011-05-14 11:56:16 +0200728 tbl = rcu_dereference(mesh_paths);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800729 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100730 mpath = node->mpath;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200731 if (rcu_dereference(mpath->next_hop) == sta &&
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100732 mpath->flags & MESH_PATH_ACTIVE &&
733 !(mpath->flags & MESH_PATH_FIXED)) {
Javier Cardonaf5e50cd2011-08-29 13:23:05 -0700734 spin_lock_bh(&mpath->state_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100735 mpath->flags &= ~MESH_PATH_ACTIVE;
Rui Paulod19b3bf2009-11-09 23:46:55 +0000736 ++mpath->sn;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100737 spin_unlock_bh(&mpath->state_lock);
Johannes Bergbf7cd942013-02-15 14:40:31 +0100738 mesh_path_error_tx(sdata,
739 sdata->u.mesh.mshcfg.element_ttl,
740 mpath->dst, cpu_to_le32(mpath->sn),
741 reason, bcast);
Javier Cardonaf5e50cd2011-08-29 13:23:05 -0700742 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100743 }
744 rcu_read_unlock();
745}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100746
Javier Cardona19c50b32011-08-29 13:23:07 -0700747static void mesh_path_node_reclaim(struct rcu_head *rp)
748{
749 struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
750 struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
751
752 del_timer_sync(&node->mpath->timer);
753 atomic_dec(&sdata->u.mesh.mpaths);
754 kfree(node->mpath);
755 kfree(node);
756}
757
758/* needs to be called with the corresponding hashwlock taken */
759static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
760{
761 struct mesh_path *mpath;
762 mpath = node->mpath;
763 spin_lock(&mpath->state_lock);
764 mpath->flags |= MESH_PATH_RESOLVING;
765 if (mpath->is_gate)
766 mesh_gate_del(tbl, mpath);
767 hlist_del_rcu(&node->list);
768 call_rcu(&node->rcu, mesh_path_node_reclaim);
769 spin_unlock(&mpath->state_lock);
770 atomic_dec(&tbl->entries);
771}
772
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100773/**
774 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
775 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000776 * @sta: mesh peer to match
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100777 *
Luis Carlos Cobob4e08ea2008-02-29 15:46:08 -0800778 * RCU notes: this function is called when a mesh plink transitions from
779 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
780 * allows path creation. This will happen before the sta can be freed (because
Johannes Bergd0709a62008-02-25 16:27:46 +0100781 * sta_info_destroy() calls this) so any reader in a rcu read block will be
782 * protected against the plink disappearing.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100783 */
784void mesh_path_flush_by_nexthop(struct sta_info *sta)
785{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200786 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100787 struct mesh_path *mpath;
788 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100789 int i;
790
Johannes Berg349eb8c2011-05-14 11:56:16 +0200791 rcu_read_lock();
Javier Cardona239289e2011-08-29 13:23:09 -0700792 read_lock_bh(&pathtbl_resize_lock);
793 tbl = resize_dereference_mesh_paths();
Sasha Levinb67bfe02013-02-27 17:06:00 -0800794 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100795 mpath = node->mpath;
Javier Cardonacd72e812011-08-29 13:23:08 -0700796 if (rcu_dereference(mpath->next_hop) == sta) {
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800797 spin_lock(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700798 __mesh_path_del(tbl, node);
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800799 spin_unlock(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700800 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100801 }
Javier Cardona239289e2011-08-29 13:23:09 -0700802 read_unlock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200803 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100804}
805
Javier Cardonacd72e812011-08-29 13:23:08 -0700806static void table_flush_by_iface(struct mesh_table *tbl,
807 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100808{
809 struct mesh_path *mpath;
810 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100811 int i;
812
Javier Cardonacd72e812011-08-29 13:23:08 -0700813 WARN_ON(!rcu_read_lock_held());
Sasha Levinb67bfe02013-02-27 17:06:00 -0800814 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100815 mpath = node->mpath;
Javier Cardonacd72e812011-08-29 13:23:08 -0700816 if (mpath->sdata != sdata)
817 continue;
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700818 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700819 __mesh_path_del(tbl, node);
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700820 spin_unlock_bh(&tbl->hashwlock[i]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100821 }
822}
823
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700824/**
825 * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
826 *
827 * This function deletes both mesh paths as well as mesh portal paths.
828 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000829 * @sdata: interface data to match
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700830 *
831 */
832void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100833{
Javier Cardonacd72e812011-08-29 13:23:08 -0700834 struct mesh_table *tbl;
Johannes Bergd0709a62008-02-25 16:27:46 +0100835
Javier Cardonacd72e812011-08-29 13:23:08 -0700836 rcu_read_lock();
Javier Cardona239289e2011-08-29 13:23:09 -0700837 read_lock_bh(&pathtbl_resize_lock);
838 tbl = resize_dereference_mesh_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700839 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700840 tbl = resize_dereference_mpp_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700841 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700842 read_unlock_bh(&pathtbl_resize_lock);
Javier Cardonacd72e812011-08-29 13:23:08 -0700843 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100844}
845
846/**
847 * mesh_path_del - delete a mesh path from the table
848 *
849 * @addr: dst address (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200850 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100851 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200852 * Returns: 0 if successful
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100853 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100854int mesh_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100855{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200856 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100857 struct mesh_path *mpath;
858 struct mpath_node *node;
859 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100860 int hash_idx;
861 int err = 0;
862
Javier Cardona9b84b8082011-05-03 16:57:16 -0700863 read_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200864 tbl = resize_dereference_mesh_paths();
865 hash_idx = mesh_table_hash(addr, sdata, tbl);
866 bucket = &tbl->hash_buckets[hash_idx];
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100867
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800868 spin_lock(&tbl->hashwlock[hash_idx]);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800869 hlist_for_each_entry(node, bucket, list) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100870 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200871 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000872 ether_addr_equal(addr, mpath->dst)) {
Javier Cardona19c50b32011-08-29 13:23:07 -0700873 __mesh_path_del(tbl, node);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100874 goto enddel;
875 }
876 }
877
878 err = -ENXIO;
879enddel:
Johannes Bergf5ea9122009-08-07 16:17:38 +0200880 mesh_paths_generation++;
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800881 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700882 read_unlock_bh(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100883 return err;
884}
885
886/**
887 * mesh_path_tx_pending - sends pending frames in a mesh path queue
888 *
889 * @mpath: mesh path to activate
890 *
891 * Locking: the state_lock of the mpath structure must NOT be held when calling
892 * this function.
893 */
894void mesh_path_tx_pending(struct mesh_path *mpath)
895{
Javier Cardona249b4052009-07-07 10:55:03 -0700896 if (mpath->flags & MESH_PATH_ACTIVE)
897 ieee80211_add_pending_skbs(mpath->sdata->local,
898 &mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100899}
900
901/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700902 * mesh_path_send_to_gates - sends pending frames to all known mesh gates
903 *
904 * @mpath: mesh path whose queue will be emptied
905 *
906 * If there is only one gate, the frames are transferred from the failed mpath
907 * queue to that gate's queue. If there are more than one gates, the frames
908 * are copied from each gate to the next. After frames are copied, the
909 * mpath queues are emptied onto the transmission queue.
910 */
911int mesh_path_send_to_gates(struct mesh_path *mpath)
912{
913 struct ieee80211_sub_if_data *sdata = mpath->sdata;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700914 struct mesh_table *tbl;
915 struct mesh_path *from_mpath = mpath;
916 struct mpath_node *gate = NULL;
917 bool copy = false;
918 struct hlist_head *known_gates;
919
920 rcu_read_lock();
921 tbl = rcu_dereference(mesh_paths);
922 known_gates = tbl->known_gates;
923 rcu_read_unlock();
924
925 if (!known_gates)
926 return -EHOSTUNREACH;
927
Sasha Levinb67bfe02013-02-27 17:06:00 -0800928 hlist_for_each_entry_rcu(gate, known_gates, list) {
Javier Cardona5ee68e52011-08-09 16:45:08 -0700929 if (gate->mpath->sdata != sdata)
930 continue;
931
932 if (gate->mpath->flags & MESH_PATH_ACTIVE) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200933 mpath_dbg(sdata, "Forwarding to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700934 mesh_path_move_to_queue(gate->mpath, from_mpath, copy);
935 from_mpath = gate->mpath;
936 copy = true;
937 } else {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200938 mpath_dbg(sdata,
939 "Not forwarding %p (flags %#x)\n",
940 gate->mpath, gate->mpath->flags);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700941 }
942 }
943
Sasha Levinb67bfe02013-02-27 17:06:00 -0800944 hlist_for_each_entry_rcu(gate, known_gates, list)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700945 if (gate->mpath->sdata == sdata) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200946 mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700947 mesh_path_tx_pending(gate->mpath);
948 }
949
950 return (from_mpath == mpath) ? -EHOSTUNREACH : 0;
951}
952
953/**
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100954 * mesh_path_discard_frame - discard a frame whose path could not be resolved
955 *
956 * @skb: frame to discard
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200957 * @sdata: network subif the frame was to be sent through
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100958 *
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100959 * Locking: the function must me called within a rcu_read_lock region
960 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100961void mesh_path_discard_frame(struct ieee80211_sub_if_data *sdata,
962 struct sk_buff *skb)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100963{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100964 kfree_skb(skb);
Johannes Berg472dbc42008-09-11 00:01:49 +0200965 sdata->u.mesh.mshstats.dropped_frames_no_route++;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100966}
967
968/**
969 * mesh_path_flush_pending - free the pending queue of a mesh path
970 *
971 * @mpath: mesh path whose queue has to be freed
972 *
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300973 * Locking: the function must me called within a rcu_read_lock region
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100974 */
975void mesh_path_flush_pending(struct mesh_path *mpath)
976{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100977 struct sk_buff *skb;
978
Javier Cardona00e3f252011-08-09 16:45:07 -0700979 while ((skb = skb_dequeue(&mpath->frame_queue)) != NULL)
Johannes Bergbf7cd942013-02-15 14:40:31 +0100980 mesh_path_discard_frame(mpath->sdata, skb);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100981}
982
983/**
984 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
985 *
986 * @mpath: the mesh path to modify
987 * @next_hop: the next hop to force
988 *
989 * Locking: this function must be called holding mpath->state_lock
990 */
991void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop)
992{
993 spin_lock_bh(&mpath->state_lock);
994 mesh_path_assign_nexthop(mpath, next_hop);
Rui Paulod19b3bf2009-11-09 23:46:55 +0000995 mpath->sn = 0xffff;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100996 mpath->metric = 0;
997 mpath->hop_count = 0;
998 mpath->exp_time = 0;
999 mpath->flags |= MESH_PATH_FIXED;
1000 mesh_path_activate(mpath);
1001 spin_unlock_bh(&mpath->state_lock);
1002 mesh_path_tx_pending(mpath);
1003}
1004
1005static void mesh_path_node_free(struct hlist_node *p, bool free_leafs)
1006{
1007 struct mesh_path *mpath;
1008 struct mpath_node *node = hlist_entry(p, struct mpath_node, list);
1009 mpath = node->mpath;
1010 hlist_del_rcu(p);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001011 if (free_leafs) {
1012 del_timer_sync(&mpath->timer);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001013 kfree(mpath);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001014 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001015 kfree(node);
1016}
1017
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001018static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001019{
1020 struct mesh_path *mpath;
1021 struct mpath_node *node, *new_node;
1022 u32 hash_idx;
1023
Pavel Emelyanov8566dc32008-05-07 19:51:51 +04001024 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov00242c42008-05-07 19:48:14 +04001025 if (new_node == NULL)
1026 return -ENOMEM;
1027
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001028 node = hlist_entry(p, struct mpath_node, list);
1029 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001030 new_node->mpath = mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001031 hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001032 hlist_add_head(&new_node->list,
1033 &newtbl->hash_buckets[hash_idx]);
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001034 return 0;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001035}
1036
1037int mesh_pathtbl_init(void)
1038{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001039 struct mesh_table *tbl_path, *tbl_mpp;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001040 int ret;
YanBo79617de2008-09-22 13:30:32 +08001041
Johannes Berg349eb8c2011-05-14 11:56:16 +02001042 tbl_path = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1043 if (!tbl_path)
1044 return -ENOMEM;
1045 tbl_path->free_node = &mesh_path_node_free;
1046 tbl_path->copy_node = &mesh_path_node_copy;
1047 tbl_path->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001048 tbl_path->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001049 if (!tbl_path->known_gates) {
1050 ret = -ENOMEM;
1051 goto free_path;
1052 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001053 INIT_HLIST_HEAD(tbl_path->known_gates);
1054
Johannes Berg349eb8c2011-05-14 11:56:16 +02001055
1056 tbl_mpp = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1057 if (!tbl_mpp) {
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001058 ret = -ENOMEM;
1059 goto free_path;
YanBo79617de2008-09-22 13:30:32 +08001060 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001061 tbl_mpp->free_node = &mesh_path_node_free;
1062 tbl_mpp->copy_node = &mesh_path_node_copy;
1063 tbl_mpp->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001064 tbl_mpp->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001065 if (!tbl_mpp->known_gates) {
1066 ret = -ENOMEM;
1067 goto free_mpp;
1068 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001069 INIT_HLIST_HEAD(tbl_mpp->known_gates);
Johannes Berg349eb8c2011-05-14 11:56:16 +02001070
1071 /* Need no locking since this is during init */
1072 RCU_INIT_POINTER(mesh_paths, tbl_path);
1073 RCU_INIT_POINTER(mpp_paths, tbl_mpp);
YanBo79617de2008-09-22 13:30:32 +08001074
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001075 return 0;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001076
1077free_mpp:
1078 mesh_table_free(tbl_mpp, true);
1079free_path:
1080 mesh_table_free(tbl_path, true);
1081 return ret;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001082}
1083
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001084void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001085{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001086 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001087 struct mesh_path *mpath;
1088 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001089 int i;
1090
Johannes Berg349eb8c2011-05-14 11:56:16 +02001091 rcu_read_lock();
1092 tbl = rcu_dereference(mesh_paths);
Sasha Levinb67bfe02013-02-27 17:06:00 -08001093 for_each_mesh_entry(tbl, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001094 if (node->mpath->sdata != sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001095 continue;
1096 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001097 if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
1098 (!(mpath->flags & MESH_PATH_FIXED)) &&
Javier Cardonaf5e50cd2011-08-29 13:23:05 -07001099 time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
Johannes Bergbf7cd942013-02-15 14:40:31 +01001100 mesh_path_del(mpath->sdata, mpath->dst);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001101 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001102 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001103}
1104
1105void mesh_pathtbl_unregister(void)
1106{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001107 /* no need for locking during exit path */
Eric Dumazet33d480c2011-08-11 19:30:52 +00001108 mesh_table_free(rcu_dereference_protected(mesh_paths, 1), true);
1109 mesh_table_free(rcu_dereference_protected(mpp_paths, 1), true);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001110}