blob: b890e225a8f1b98681c53c764fc5252e5f2d5c8d [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;
Henning Roggea2db2ed2014-09-12 08:58:50 +020047int mpp_paths_generation;
Johannes Berg6b86bd62011-05-12 13:38:50 +020048
49/* This lock will have the grow table function as writer and add / delete nodes
Javier Cardona239289e2011-08-29 13:23:09 -070050 * as readers. RCU provides sufficient protection only when reading the table
51 * (i.e. doing lookups). Adding or adding or removing nodes requires we take
52 * the read lock or we risk operating on an old table. The write lock is only
53 * needed when modifying the number of buckets a table.
Johannes Berg6b86bd62011-05-12 13:38:50 +020054 */
55static DEFINE_RWLOCK(pathtbl_resize_lock);
56
57
Johannes Berg349eb8c2011-05-14 11:56:16 +020058static inline struct mesh_table *resize_dereference_mesh_paths(void)
59{
60 return rcu_dereference_protected(mesh_paths,
61 lockdep_is_held(&pathtbl_resize_lock));
62}
63
64static inline struct mesh_table *resize_dereference_mpp_paths(void)
65{
66 return rcu_dereference_protected(mpp_paths,
67 lockdep_is_held(&pathtbl_resize_lock));
68}
69
70/*
71 * CAREFUL -- "tbl" must not be an expression,
72 * in particular not an rcu_dereference(), since
73 * it's used twice. So it is illegal to do
74 * for_each_mesh_entry(rcu_dereference(...), ...)
75 */
Sasha Levinb67bfe02013-02-27 17:06:00 -080076#define for_each_mesh_entry(tbl, node, i) \
Johannes Berg349eb8c2011-05-14 11:56:16 +020077 for (i = 0; i <= tbl->hash_mask; i++) \
Sasha Levinb67bfe02013-02-27 17:06:00 -080078 hlist_for_each_entry_rcu(node, &tbl->hash_buckets[i], list)
Johannes Berg349eb8c2011-05-14 11:56:16 +020079
80
Johannes Berg6b86bd62011-05-12 13:38:50 +020081static struct mesh_table *mesh_table_alloc(int size_order)
82{
83 int i;
84 struct mesh_table *newtbl;
85
Javier Cardonad676ff42011-05-17 16:13:34 -070086 newtbl = kmalloc(sizeof(struct mesh_table), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020087 if (!newtbl)
88 return NULL;
89
90 newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) *
Javier Cardonad676ff42011-05-17 16:13:34 -070091 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020092
93 if (!newtbl->hash_buckets) {
94 kfree(newtbl);
95 return NULL;
96 }
97
98 newtbl->hashwlock = kmalloc(sizeof(spinlock_t) *
Javier Cardonad676ff42011-05-17 16:13:34 -070099 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +0200100 if (!newtbl->hashwlock) {
101 kfree(newtbl->hash_buckets);
102 kfree(newtbl);
103 return NULL;
104 }
105
106 newtbl->size_order = size_order;
107 newtbl->hash_mask = (1 << size_order) - 1;
108 atomic_set(&newtbl->entries, 0);
109 get_random_bytes(&newtbl->hash_rnd,
110 sizeof(newtbl->hash_rnd));
111 for (i = 0; i <= newtbl->hash_mask; i++)
112 spin_lock_init(&newtbl->hashwlock[i]);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700113 spin_lock_init(&newtbl->gates_lock);
Johannes Berg6b86bd62011-05-12 13:38:50 +0200114
115 return newtbl;
116}
117
Javier Cardona18889232009-08-10 12:15:52 -0700118static void __mesh_table_free(struct mesh_table *tbl)
119{
120 kfree(tbl->hash_buckets);
121 kfree(tbl->hashwlock);
122 kfree(tbl);
123}
124
Johannes Berg6b86bd62011-05-12 13:38:50 +0200125static void mesh_table_free(struct mesh_table *tbl, bool free_leafs)
Javier Cardona18889232009-08-10 12:15:52 -0700126{
127 struct hlist_head *mesh_hash;
128 struct hlist_node *p, *q;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700129 struct mpath_node *gate;
Javier Cardona18889232009-08-10 12:15:52 -0700130 int i;
131
132 mesh_hash = tbl->hash_buckets;
133 for (i = 0; i <= tbl->hash_mask; i++) {
Javier Cardona9b84b8082011-05-03 16:57:16 -0700134 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700135 hlist_for_each_safe(p, q, &mesh_hash[i]) {
136 tbl->free_node(p, free_leafs);
137 atomic_dec(&tbl->entries);
138 }
Javier Cardona9b84b8082011-05-03 16:57:16 -0700139 spin_unlock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700140 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700141 if (free_leafs) {
142 spin_lock_bh(&tbl->gates_lock);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800143 hlist_for_each_entry_safe(gate, q,
Javier Cardona5ee68e52011-08-09 16:45:08 -0700144 tbl->known_gates, list) {
145 hlist_del(&gate->list);
146 kfree(gate);
147 }
148 kfree(tbl->known_gates);
149 spin_unlock_bh(&tbl->gates_lock);
150 }
151
Javier Cardona18889232009-08-10 12:15:52 -0700152 __mesh_table_free(tbl);
153}
154
cozybit Inca3e6b122011-04-13 11:10:28 -0700155static int mesh_table_grow(struct mesh_table *oldtbl,
Johannes Berg6b86bd62011-05-12 13:38:50 +0200156 struct mesh_table *newtbl)
Javier Cardona18889232009-08-10 12:15:52 -0700157{
Javier Cardona18889232009-08-10 12:15:52 -0700158 struct hlist_head *oldhash;
159 struct hlist_node *p, *q;
160 int i;
161
cozybit Inca3e6b122011-04-13 11:10:28 -0700162 if (atomic_read(&oldtbl->entries)
163 < oldtbl->mean_chain_len * (oldtbl->hash_mask + 1))
164 return -EAGAIN;
Javier Cardona18889232009-08-10 12:15:52 -0700165
cozybit Inca3e6b122011-04-13 11:10:28 -0700166 newtbl->free_node = oldtbl->free_node;
167 newtbl->mean_chain_len = oldtbl->mean_chain_len;
168 newtbl->copy_node = oldtbl->copy_node;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700169 newtbl->known_gates = oldtbl->known_gates;
cozybit Inca3e6b122011-04-13 11:10:28 -0700170 atomic_set(&newtbl->entries, atomic_read(&oldtbl->entries));
Javier Cardona18889232009-08-10 12:15:52 -0700171
cozybit Inca3e6b122011-04-13 11:10:28 -0700172 oldhash = oldtbl->hash_buckets;
173 for (i = 0; i <= oldtbl->hash_mask; i++)
Javier Cardona18889232009-08-10 12:15:52 -0700174 hlist_for_each(p, &oldhash[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700175 if (oldtbl->copy_node(p, newtbl) < 0)
Javier Cardona18889232009-08-10 12:15:52 -0700176 goto errcopy;
177
cozybit Inca3e6b122011-04-13 11:10:28 -0700178 return 0;
Javier Cardona18889232009-08-10 12:15:52 -0700179
180errcopy:
181 for (i = 0; i <= newtbl->hash_mask; i++) {
182 hlist_for_each_safe(p, q, &newtbl->hash_buckets[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700183 oldtbl->free_node(p, 0);
Javier Cardona18889232009-08-10 12:15:52 -0700184 }
cozybit Inca3e6b122011-04-13 11:10:28 -0700185 return -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700186}
187
Johannes Berg4a3cb702013-02-12 16:43:19 +0100188static u32 mesh_table_hash(const u8 *addr, struct ieee80211_sub_if_data *sdata,
Johannes Berg6b86bd62011-05-12 13:38:50 +0200189 struct mesh_table *tbl)
190{
191 /* Use last four bytes of hw addr and interface index as hash index */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100192 return jhash_2words(*(u32 *)(addr+2), sdata->dev->ifindex,
193 tbl->hash_rnd) & tbl->hash_mask;
Johannes Berg6b86bd62011-05-12 13:38:50 +0200194}
Johannes Bergf5ea9122009-08-07 16:17:38 +0200195
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100196
197/**
198 *
199 * mesh_path_assign_nexthop - update mesh path next hop
200 *
201 * @mpath: mesh path to update
202 * @sta: next hop to assign
203 *
204 * Locking: mpath->state_lock must be held when calling this function
205 */
206void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta)
207{
Javier Cardona10c836d2009-07-09 14:42:16 -0700208 struct sk_buff *skb;
209 struct ieee80211_hdr *hdr;
Javier Cardona10c836d2009-07-09 14:42:16 -0700210 unsigned long flags;
211
Johannes Bergd0709a62008-02-25 16:27:46 +0100212 rcu_assign_pointer(mpath->next_hop, sta);
Javier Cardona10c836d2009-07-09 14:42:16 -0700213
Javier Cardona10c836d2009-07-09 14:42:16 -0700214 spin_lock_irqsave(&mpath->frame_queue.lock, flags);
Thomas Pedersenb22bd522012-08-09 18:15:39 -0700215 skb_queue_walk(&mpath->frame_queue, skb) {
Javier Cardona10c836d2009-07-09 14:42:16 -0700216 hdr = (struct ieee80211_hdr *) skb->data;
217 memcpy(hdr->addr1, sta->sta.addr, ETH_ALEN);
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800218 memcpy(hdr->addr2, mpath->sdata->vif.addr, ETH_ALEN);
Marco Porsch3f52b7e2013-01-30 18:14:08 +0100219 ieee80211_mps_set_frame_flags(sta->sdata, sta, hdr);
Javier Cardona10c836d2009-07-09 14:42:16 -0700220 }
221
Javier Cardona10c836d2009-07-09 14:42:16 -0700222 spin_unlock_irqrestore(&mpath->frame_queue.lock, flags);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100223}
224
Javier Cardona5ee68e52011-08-09 16:45:08 -0700225static void prepare_for_gate(struct sk_buff *skb, char *dst_addr,
226 struct mesh_path *gate_mpath)
227{
228 struct ieee80211_hdr *hdr;
229 struct ieee80211s_hdr *mshdr;
230 int mesh_hdrlen, hdrlen;
231 char *next_hop;
232
233 hdr = (struct ieee80211_hdr *) skb->data;
234 hdrlen = ieee80211_hdrlen(hdr->frame_control);
235 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
236
237 if (!(mshdr->flags & MESH_FLAGS_AE)) {
238 /* size of the fixed part of the mesh header */
239 mesh_hdrlen = 6;
240
241 /* make room for the two extended addresses */
242 skb_push(skb, 2 * ETH_ALEN);
243 memmove(skb->data, hdr, hdrlen + mesh_hdrlen);
244
245 hdr = (struct ieee80211_hdr *) skb->data;
246
247 /* we preserve the previous mesh header and only add
248 * the new addreses */
249 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
250 mshdr->flags = MESH_FLAGS_AE_A5_A6;
251 memcpy(mshdr->eaddr1, hdr->addr3, ETH_ALEN);
252 memcpy(mshdr->eaddr2, hdr->addr4, ETH_ALEN);
253 }
254
255 /* update next hop */
256 hdr = (struct ieee80211_hdr *) skb->data;
257 rcu_read_lock();
258 next_hop = rcu_dereference(gate_mpath->next_hop)->sta.addr;
259 memcpy(hdr->addr1, next_hop, ETH_ALEN);
260 rcu_read_unlock();
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800261 memcpy(hdr->addr2, gate_mpath->sdata->vif.addr, ETH_ALEN);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700262 memcpy(hdr->addr3, dst_addr, ETH_ALEN);
263}
264
265/**
266 *
267 * mesh_path_move_to_queue - Move or copy frames from one mpath queue to another
268 *
269 * This function is used to transfer or copy frames from an unresolved mpath to
270 * a gate mpath. The function also adds the Address Extension field and
271 * updates the next hop.
272 *
273 * If a frame already has an Address Extension field, only the next hop and
274 * destination addresses are updated.
275 *
276 * The gate mpath must be an active mpath with a valid mpath->next_hop.
277 *
278 * @mpath: An active mpath the frames will be sent to (i.e. the gate)
279 * @from_mpath: The failed mpath
280 * @copy: When true, copy all the frames to the new mpath queue. When false,
281 * move them.
282 */
283static void mesh_path_move_to_queue(struct mesh_path *gate_mpath,
284 struct mesh_path *from_mpath,
285 bool copy)
286{
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700287 struct sk_buff *skb, *fskb, *tmp;
288 struct sk_buff_head failq;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700289 unsigned long flags;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700290
Johannes Berg8c5bb1f2014-04-29 17:55:26 +0200291 if (WARN_ON(gate_mpath == from_mpath))
292 return;
293 if (WARN_ON(!gate_mpath->next_hop))
294 return;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700295
Javier Cardona5ee68e52011-08-09 16:45:08 -0700296 __skb_queue_head_init(&failq);
297
298 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
299 skb_queue_splice_init(&from_mpath->frame_queue, &failq);
300 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
301
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700302 skb_queue_walk_safe(&failq, fskb, tmp) {
303 if (skb_queue_len(&gate_mpath->frame_queue) >=
304 MESH_FRAME_QUEUE_LEN) {
305 mpath_dbg(gate_mpath->sdata, "mpath queue full!\n");
306 break;
John W. Linville817a53d2011-08-24 15:12:41 -0400307 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700308
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700309 skb = skb_copy(fskb, GFP_ATOMIC);
310 if (WARN_ON(!skb))
311 break;
312
Javier Cardona5ee68e52011-08-09 16:45:08 -0700313 prepare_for_gate(skb, gate_mpath->dst, gate_mpath);
Thomas Pedersen4bd4c2d2012-08-09 18:15:40 -0700314 skb_queue_tail(&gate_mpath->frame_queue, skb);
315
316 if (copy)
317 continue;
318
319 __skb_unlink(fskb, &failq);
320 kfree_skb(fskb);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700321 }
322
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200323 mpath_dbg(gate_mpath->sdata, "Mpath queue for gate %pM has %d frames\n",
324 gate_mpath->dst, skb_queue_len(&gate_mpath->frame_queue));
Javier Cardona5ee68e52011-08-09 16:45:08 -0700325
326 if (!copy)
327 return;
328
329 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
330 skb_queue_splice(&failq, &from_mpath->frame_queue);
331 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
332}
333
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100334
Johannes Berg4a3cb702013-02-12 16:43:19 +0100335static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst,
336 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100337{
338 struct mesh_path *mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100339 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100340 struct mpath_node *node;
341
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200342 bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
Sasha Levinb67bfe02013-02-27 17:06:00 -0800343 hlist_for_each_entry_rcu(node, bucket, list) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100344 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200345 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000346 ether_addr_equal(dst, mpath->dst)) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100347 if (mpath_expired(mpath)) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100348 spin_lock_bh(&mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700349 mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100350 spin_unlock_bh(&mpath->state_lock);
351 }
352 return mpath;
353 }
354 }
355 return NULL;
356}
357
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100358/**
359 * mesh_path_lookup - look up a path in the mesh path table
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100360 * @sdata: local subif
Johannes Bergbf7cd942013-02-15 14:40:31 +0100361 * @dst: hardware address (ETH_ALEN length) of destination
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100362 *
363 * Returns: pointer to the mesh path structure, or NULL if not found
364 *
365 * Locking: must be called within a read rcu section.
366 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100367struct mesh_path *
368mesh_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100369{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800370 return mpath_lookup(rcu_dereference(mesh_paths), dst, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100371}
372
Johannes Bergbf7cd942013-02-15 14:40:31 +0100373struct mesh_path *
374mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst)
YanBo79617de2008-09-22 13:30:32 +0800375{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800376 return mpath_lookup(rcu_dereference(mpp_paths), dst, sdata);
YanBo79617de2008-09-22 13:30:32 +0800377}
378
379
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100380/**
381 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
382 * @idx: index
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200383 * @sdata: local subif, or NULL for all entries
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100384 *
385 * Returns: pointer to the mesh path structure, or NULL if not found.
386 *
387 * Locking: must be called within a read rcu section.
388 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100389struct mesh_path *
390mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100391{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200392 struct mesh_table *tbl = rcu_dereference(mesh_paths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100393 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100394 int i;
395 int j = 0;
396
Sasha Levinb67bfe02013-02-27 17:06:00 -0800397 for_each_mesh_entry(tbl, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200398 if (sdata && node->mpath->sdata != sdata)
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800399 continue;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100400 if (j++ == idx) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100401 if (mpath_expired(node->mpath)) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100402 spin_lock_bh(&node->mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700403 node->mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100404 spin_unlock_bh(&node->mpath->state_lock);
405 }
406 return node->mpath;
407 }
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800408 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100409
410 return NULL;
411}
412
Javier Cardona5ee68e52011-08-09 16:45:08 -0700413/**
Henning Roggea2db2ed2014-09-12 08:58:50 +0200414 * mpp_path_lookup_by_idx - look up a path in the proxy path table by its index
415 * @idx: index
416 * @sdata: local subif, or NULL for all entries
417 *
418 * Returns: pointer to the proxy path structure, or NULL if not found.
419 *
420 * Locking: must be called within a read rcu section.
421 */
422struct mesh_path *
423mpp_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx)
424{
425 struct mesh_table *tbl = rcu_dereference(mpp_paths);
426 struct mpath_node *node;
427 int i;
428 int j = 0;
429
430 for_each_mesh_entry(tbl, node, i) {
431 if (sdata && node->mpath->sdata != sdata)
432 continue;
433 if (j++ == idx)
434 return node->mpath;
435 }
436
437 return NULL;
438}
439
440/**
Johannes Berg30be52e2011-11-21 11:23:50 +0100441 * mesh_path_add_gate - add the given mpath to a mesh gate to our path table
442 * @mpath: gate path to add to table
Javier Cardona5ee68e52011-08-09 16:45:08 -0700443 */
Johannes Berg30be52e2011-11-21 11:23:50 +0100444int mesh_path_add_gate(struct mesh_path *mpath)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700445{
Johannes Berg30be52e2011-11-21 11:23:50 +0100446 struct mesh_table *tbl;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700447 struct mpath_node *gate, *new_gate;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700448 int err;
449
450 rcu_read_lock();
Johannes Berg30be52e2011-11-21 11:23:50 +0100451 tbl = rcu_dereference(mesh_paths);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700452
Sasha Levinb67bfe02013-02-27 17:06:00 -0800453 hlist_for_each_entry_rcu(gate, tbl->known_gates, list)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700454 if (gate->mpath == mpath) {
455 err = -EEXIST;
456 goto err_rcu;
457 }
458
459 new_gate = kzalloc(sizeof(struct mpath_node), GFP_ATOMIC);
460 if (!new_gate) {
461 err = -ENOMEM;
462 goto err_rcu;
463 }
464
465 mpath->is_gate = true;
466 mpath->sdata->u.mesh.num_gates++;
467 new_gate->mpath = mpath;
468 spin_lock_bh(&tbl->gates_lock);
469 hlist_add_head_rcu(&new_gate->list, tbl->known_gates);
470 spin_unlock_bh(&tbl->gates_lock);
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200471 mpath_dbg(mpath->sdata,
472 "Mesh path: Recorded new gate: %pM. %d known gates\n",
473 mpath->dst, mpath->sdata->u.mesh.num_gates);
Johannes Bergbf7cd942013-02-15 14:40:31 +0100474 err = 0;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700475err_rcu:
476 rcu_read_unlock();
477 return err;
478}
479
480/**
481 * mesh_gate_del - remove a mesh gate from the list of known gates
482 * @tbl: table which holds our list of known gates
483 * @mpath: gate mpath
484 *
Javier Cardona5ee68e52011-08-09 16:45:08 -0700485 * Locking: must be called inside rcu_read_lock() section
486 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100487static void mesh_gate_del(struct mesh_table *tbl, struct mesh_path *mpath)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700488{
489 struct mpath_node *gate;
Sasha Levinb67bfe02013-02-27 17:06:00 -0800490 struct hlist_node *q;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700491
Sasha Levinb67bfe02013-02-27 17:06:00 -0800492 hlist_for_each_entry_safe(gate, q, tbl->known_gates, list) {
Johannes Bergbf7cd942013-02-15 14:40:31 +0100493 if (gate->mpath != mpath)
494 continue;
495 spin_lock_bh(&tbl->gates_lock);
496 hlist_del_rcu(&gate->list);
497 kfree_rcu(gate, rcu);
498 spin_unlock_bh(&tbl->gates_lock);
499 mpath->sdata->u.mesh.num_gates--;
500 mpath->is_gate = false;
501 mpath_dbg(mpath->sdata,
502 "Mesh path: Deleted gate: %pM. %d known gates\n",
503 mpath->dst, mpath->sdata->u.mesh.num_gates);
504 break;
505 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700506}
507
508/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700509 * mesh_gate_num - number of gates known to this interface
510 * @sdata: subif data
511 */
512int mesh_gate_num(struct ieee80211_sub_if_data *sdata)
513{
514 return sdata->u.mesh.num_gates;
515}
516
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100517/**
518 * mesh_path_add - allocate and add a new path to the mesh path table
Johannes Bergbf7cd942013-02-15 14:40:31 +0100519 * @dst: destination address of the path (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200520 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100521 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200522 * Returns: 0 on success
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100523 *
524 * State: the initial state of the new path is set to 0
525 */
Bob Copelandae76eef2013-03-29 09:38:39 -0400526struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata,
527 const u8 *dst)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100528{
Javier Cardona18889232009-08-10 12:15:52 -0700529 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
530 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200531 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100532 struct mesh_path *mpath, *new_mpath;
533 struct mpath_node *node, *new_node;
534 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100535 int grow = 0;
Bob Copelandae76eef2013-03-29 09:38:39 -0400536 int err;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100537 u32 hash_idx;
538
Joe Perchesb203ca32012-05-08 18:56:52 +0000539 if (ether_addr_equal(dst, sdata->vif.addr))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100540 /* never add ourselves as neighbours */
Bob Copelandae76eef2013-03-29 09:38:39 -0400541 return ERR_PTR(-ENOTSUPP);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100542
543 if (is_multicast_ether_addr(dst))
Bob Copelandae76eef2013-03-29 09:38:39 -0400544 return ERR_PTR(-ENOTSUPP);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100545
Johannes Berg472dbc42008-09-11 00:01:49 +0200546 if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0)
Bob Copelandae76eef2013-03-29 09:38:39 -0400547 return ERR_PTR(-ENOSPC);
548
549 read_lock_bh(&pathtbl_resize_lock);
550 tbl = resize_dereference_mesh_paths();
551
552 hash_idx = mesh_table_hash(dst, sdata, tbl);
553 bucket = &tbl->hash_buckets[hash_idx];
554
555 spin_lock(&tbl->hashwlock[hash_idx]);
556
557 hlist_for_each_entry(node, bucket, list) {
558 mpath = node->mpath;
559 if (mpath->sdata == sdata &&
560 ether_addr_equal(dst, mpath->dst))
561 goto found;
562 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100563
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400564 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700565 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400566 if (!new_mpath)
567 goto err_path_alloc;
568
Javier Cardona18889232009-08-10 12:15:52 -0700569 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400570 if (!new_node)
571 goto err_node_alloc;
Pavel Emelyanovf84e71a2008-05-06 18:46:36 +0400572
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100573 memcpy(new_mpath->dst, dst, ETH_ALEN);
Johannes Berge83e6542012-07-13 16:23:07 +0200574 eth_broadcast_addr(new_mpath->rann_snd_addr);
Chun-Yeow Yeoh35bcd592012-04-10 12:31:56 +0800575 new_mpath->is_root = false;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200576 new_mpath->sdata = sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100577 new_mpath->flags = 0;
578 skb_queue_head_init(&new_mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100579 new_node->mpath = new_mpath;
580 new_mpath->timer.data = (unsigned long) new_mpath;
581 new_mpath->timer.function = mesh_path_timer;
582 new_mpath->exp_time = jiffies;
583 spin_lock_init(&new_mpath->state_lock);
584 init_timer(&new_mpath->timer);
585
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100586 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200587 if (atomic_inc_return(&tbl->entries) >=
588 tbl->mean_chain_len * (tbl->hash_mask + 1))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100589 grow = 1;
590
Johannes Bergf5ea9122009-08-07 16:17:38 +0200591 mesh_paths_generation++;
592
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400593 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700594 set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200595 ieee80211_queue_work(&local->hw, &sdata->work);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100596 }
Bob Copelandae76eef2013-03-29 09:38:39 -0400597 mpath = new_mpath;
598found:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800599 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700600 read_unlock_bh(&pathtbl_resize_lock);
Bob Copelandae76eef2013-03-29 09:38:39 -0400601 return mpath;
602
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400603err_node_alloc:
604 kfree(new_mpath);
605err_path_alloc:
Johannes Berg472dbc42008-09-11 00:01:49 +0200606 atomic_dec(&sdata->u.mesh.mpaths);
Bob Copelandae76eef2013-03-29 09:38:39 -0400607 spin_unlock(&tbl->hashwlock[hash_idx]);
608 read_unlock_bh(&pathtbl_resize_lock);
609 return ERR_PTR(err);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100610}
611
Johannes Berg1928eca2011-05-14 11:00:52 +0200612static void mesh_table_free_rcu(struct rcu_head *rcu)
613{
614 struct mesh_table *tbl = container_of(rcu, struct mesh_table, rcu_head);
615
616 mesh_table_free(tbl, false);
617}
618
Javier Cardona18889232009-08-10 12:15:52 -0700619void mesh_mpath_table_grow(void)
620{
621 struct mesh_table *oldtbl, *newtbl;
622
Javier Cardona9b84b8082011-05-03 16:57:16 -0700623 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200624 oldtbl = resize_dereference_mesh_paths();
625 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200626 if (!newtbl)
627 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200628 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700629 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200630 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700631 }
632 rcu_assign_pointer(mesh_paths, newtbl);
Javier Cardona18889232009-08-10 12:15:52 -0700633
Johannes Berg1928eca2011-05-14 11:00:52 +0200634 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
635
636 out:
637 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700638}
639
640void mesh_mpp_table_grow(void)
641{
642 struct mesh_table *oldtbl, *newtbl;
643
Javier Cardona9b84b8082011-05-03 16:57:16 -0700644 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200645 oldtbl = resize_dereference_mpp_paths();
646 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200647 if (!newtbl)
648 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200649 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700650 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200651 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700652 }
653 rcu_assign_pointer(mpp_paths, newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200654 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
Javier Cardona18889232009-08-10 12:15:52 -0700655
Johannes Berg1928eca2011-05-14 11:00:52 +0200656 out:
657 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700658}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100659
Johannes Bergbf7cd942013-02-15 14:40:31 +0100660int mpp_path_add(struct ieee80211_sub_if_data *sdata,
661 const u8 *dst, const u8 *mpp)
YanBo79617de2008-09-22 13:30:32 +0800662{
Javier Cardona18889232009-08-10 12:15:52 -0700663 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
664 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200665 struct mesh_table *tbl;
YanBo79617de2008-09-22 13:30:32 +0800666 struct mesh_path *mpath, *new_mpath;
667 struct mpath_node *node, *new_node;
668 struct hlist_head *bucket;
YanBo79617de2008-09-22 13:30:32 +0800669 int grow = 0;
670 int err = 0;
671 u32 hash_idx;
672
Joe Perchesb203ca32012-05-08 18:56:52 +0000673 if (ether_addr_equal(dst, sdata->vif.addr))
YanBo79617de2008-09-22 13:30:32 +0800674 /* never add ourselves as neighbours */
675 return -ENOTSUPP;
676
677 if (is_multicast_ether_addr(dst))
678 return -ENOTSUPP;
679
680 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700681 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800682 if (!new_mpath)
683 goto err_path_alloc;
684
Javier Cardona18889232009-08-10 12:15:52 -0700685 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800686 if (!new_node)
687 goto err_node_alloc;
688
Javier Cardona9b84b8082011-05-03 16:57:16 -0700689 read_lock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800690 memcpy(new_mpath->dst, dst, ETH_ALEN);
691 memcpy(new_mpath->mpp, mpp, ETH_ALEN);
692 new_mpath->sdata = sdata;
693 new_mpath->flags = 0;
694 skb_queue_head_init(&new_mpath->frame_queue);
695 new_node->mpath = new_mpath;
Thomas Pedersenc61336612011-08-25 10:36:14 -0700696 init_timer(&new_mpath->timer);
YanBo79617de2008-09-22 13:30:32 +0800697 new_mpath->exp_time = jiffies;
698 spin_lock_init(&new_mpath->state_lock);
699
Johannes Berg349eb8c2011-05-14 11:56:16 +0200700 tbl = resize_dereference_mpp_paths();
YanBo79617de2008-09-22 13:30:32 +0800701
Johannes Berg349eb8c2011-05-14 11:56:16 +0200702 hash_idx = mesh_table_hash(dst, sdata, tbl);
703 bucket = &tbl->hash_buckets[hash_idx];
704
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800705 spin_lock(&tbl->hashwlock[hash_idx]);
YanBo79617de2008-09-22 13:30:32 +0800706
707 err = -EEXIST;
Sasha Levinb67bfe02013-02-27 17:06:00 -0800708 hlist_for_each_entry(node, bucket, list) {
YanBo79617de2008-09-22 13:30:32 +0800709 mpath = node->mpath;
Felix Fietkau888d04d2012-03-01 15:22:09 +0100710 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000711 ether_addr_equal(dst, mpath->dst))
YanBo79617de2008-09-22 13:30:32 +0800712 goto err_exists;
713 }
714
715 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200716 if (atomic_inc_return(&tbl->entries) >=
717 tbl->mean_chain_len * (tbl->hash_mask + 1))
YanBo79617de2008-09-22 13:30:32 +0800718 grow = 1;
719
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800720 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700721 read_unlock_bh(&pathtbl_resize_lock);
Henning Roggea2db2ed2014-09-12 08:58:50 +0200722
723 mpp_paths_generation++;
724
YanBo79617de2008-09-22 13:30:32 +0800725 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700726 set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200727 ieee80211_queue_work(&local->hw, &sdata->work);
YanBo79617de2008-09-22 13:30:32 +0800728 }
729 return 0;
730
731err_exists:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800732 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700733 read_unlock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800734 kfree(new_node);
735err_node_alloc:
736 kfree(new_mpath);
737err_path_alloc:
738 return err;
739}
740
741
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100742/**
743 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
744 *
745 * @sta: broken peer link
746 *
747 * This function must be called from the rate control algorithm if enough
748 * delivery errors suggest that a peer link is no longer usable.
749 */
750void mesh_plink_broken(struct sta_info *sta)
751{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200752 struct mesh_table *tbl;
Johannes Berg15ff6362009-11-17 13:34:04 +0100753 static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100754 struct mesh_path *mpath;
755 struct mpath_node *node;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200756 struct ieee80211_sub_if_data *sdata = sta->sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100757 int i;
758
759 rcu_read_lock();
Johannes Berg349eb8c2011-05-14 11:56:16 +0200760 tbl = rcu_dereference(mesh_paths);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800761 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100762 mpath = node->mpath;
Andreea-Cristina Bernat2688eba2014-08-17 16:18:02 +0300763 if (rcu_access_pointer(mpath->next_hop) == sta &&
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100764 mpath->flags & MESH_PATH_ACTIVE &&
765 !(mpath->flags & MESH_PATH_FIXED)) {
Javier Cardonaf5e50cd2011-08-29 13:23:05 -0700766 spin_lock_bh(&mpath->state_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100767 mpath->flags &= ~MESH_PATH_ACTIVE;
Rui Paulod19b3bf2009-11-09 23:46:55 +0000768 ++mpath->sn;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100769 spin_unlock_bh(&mpath->state_lock);
Johannes Bergbf7cd942013-02-15 14:40:31 +0100770 mesh_path_error_tx(sdata,
Chun-Yeow Yeohf63f8422013-11-13 15:39:12 +0800771 sdata->u.mesh.mshcfg.element_ttl,
772 mpath->dst, mpath->sn,
773 WLAN_REASON_MESH_PATH_DEST_UNREACHABLE, bcast);
Javier Cardonaf5e50cd2011-08-29 13:23:05 -0700774 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100775 }
776 rcu_read_unlock();
777}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100778
Javier Cardona19c50b32011-08-29 13:23:07 -0700779static void mesh_path_node_reclaim(struct rcu_head *rp)
780{
781 struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
782 struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
783
784 del_timer_sync(&node->mpath->timer);
785 atomic_dec(&sdata->u.mesh.mpaths);
786 kfree(node->mpath);
787 kfree(node);
788}
789
790/* needs to be called with the corresponding hashwlock taken */
791static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
792{
793 struct mesh_path *mpath;
794 mpath = node->mpath;
795 spin_lock(&mpath->state_lock);
796 mpath->flags |= MESH_PATH_RESOLVING;
797 if (mpath->is_gate)
798 mesh_gate_del(tbl, mpath);
799 hlist_del_rcu(&node->list);
800 call_rcu(&node->rcu, mesh_path_node_reclaim);
801 spin_unlock(&mpath->state_lock);
802 atomic_dec(&tbl->entries);
803}
804
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100805/**
806 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
807 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000808 * @sta: mesh peer to match
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100809 *
Luis Carlos Cobob4e08ea2008-02-29 15:46:08 -0800810 * RCU notes: this function is called when a mesh plink transitions from
811 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
812 * allows path creation. This will happen before the sta can be freed (because
Johannes Bergd0709a62008-02-25 16:27:46 +0100813 * sta_info_destroy() calls this) so any reader in a rcu read block will be
814 * protected against the plink disappearing.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100815 */
816void mesh_path_flush_by_nexthop(struct sta_info *sta)
817{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200818 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100819 struct mesh_path *mpath;
820 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100821 int i;
822
Johannes Berg349eb8c2011-05-14 11:56:16 +0200823 rcu_read_lock();
Javier Cardona239289e2011-08-29 13:23:09 -0700824 read_lock_bh(&pathtbl_resize_lock);
825 tbl = resize_dereference_mesh_paths();
Sasha Levinb67bfe02013-02-27 17:06:00 -0800826 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100827 mpath = node->mpath;
Andreea-Cristina Bernat2688eba2014-08-17 16:18:02 +0300828 if (rcu_access_pointer(mpath->next_hop) == sta) {
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800829 spin_lock(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700830 __mesh_path_del(tbl, node);
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800831 spin_unlock(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700832 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100833 }
Javier Cardona239289e2011-08-29 13:23:09 -0700834 read_unlock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200835 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100836}
837
Javier Cardonacd72e812011-08-29 13:23:08 -0700838static void table_flush_by_iface(struct mesh_table *tbl,
839 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100840{
841 struct mesh_path *mpath;
842 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100843 int i;
844
Javier Cardonacd72e812011-08-29 13:23:08 -0700845 WARN_ON(!rcu_read_lock_held());
Sasha Levinb67bfe02013-02-27 17:06:00 -0800846 for_each_mesh_entry(tbl, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100847 mpath = node->mpath;
Javier Cardonacd72e812011-08-29 13:23:08 -0700848 if (mpath->sdata != sdata)
849 continue;
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700850 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700851 __mesh_path_del(tbl, node);
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700852 spin_unlock_bh(&tbl->hashwlock[i]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100853 }
854}
855
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700856/**
857 * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
858 *
859 * This function deletes both mesh paths as well as mesh portal paths.
860 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000861 * @sdata: interface data to match
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700862 *
863 */
864void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100865{
Javier Cardonacd72e812011-08-29 13:23:08 -0700866 struct mesh_table *tbl;
Johannes Bergd0709a62008-02-25 16:27:46 +0100867
Javier Cardonacd72e812011-08-29 13:23:08 -0700868 rcu_read_lock();
Javier Cardona239289e2011-08-29 13:23:09 -0700869 read_lock_bh(&pathtbl_resize_lock);
870 tbl = resize_dereference_mesh_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700871 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700872 tbl = resize_dereference_mpp_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700873 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700874 read_unlock_bh(&pathtbl_resize_lock);
Javier Cardonacd72e812011-08-29 13:23:08 -0700875 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100876}
877
878/**
879 * mesh_path_del - delete a mesh path from the table
880 *
881 * @addr: dst address (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200882 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100883 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200884 * Returns: 0 if successful
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100885 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100886int mesh_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100887{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200888 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100889 struct mesh_path *mpath;
890 struct mpath_node *node;
891 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100892 int hash_idx;
893 int err = 0;
894
Javier Cardona9b84b8082011-05-03 16:57:16 -0700895 read_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200896 tbl = resize_dereference_mesh_paths();
897 hash_idx = mesh_table_hash(addr, sdata, tbl);
898 bucket = &tbl->hash_buckets[hash_idx];
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100899
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800900 spin_lock(&tbl->hashwlock[hash_idx]);
Sasha Levinb67bfe02013-02-27 17:06:00 -0800901 hlist_for_each_entry(node, bucket, list) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100902 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200903 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000904 ether_addr_equal(addr, mpath->dst)) {
Javier Cardona19c50b32011-08-29 13:23:07 -0700905 __mesh_path_del(tbl, node);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100906 goto enddel;
907 }
908 }
909
910 err = -ENXIO;
911enddel:
Johannes Bergf5ea9122009-08-07 16:17:38 +0200912 mesh_paths_generation++;
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800913 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700914 read_unlock_bh(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100915 return err;
916}
917
918/**
919 * mesh_path_tx_pending - sends pending frames in a mesh path queue
920 *
921 * @mpath: mesh path to activate
922 *
923 * Locking: the state_lock of the mpath structure must NOT be held when calling
924 * this function.
925 */
926void mesh_path_tx_pending(struct mesh_path *mpath)
927{
Javier Cardona249b4052009-07-07 10:55:03 -0700928 if (mpath->flags & MESH_PATH_ACTIVE)
929 ieee80211_add_pending_skbs(mpath->sdata->local,
930 &mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100931}
932
933/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700934 * mesh_path_send_to_gates - sends pending frames to all known mesh gates
935 *
936 * @mpath: mesh path whose queue will be emptied
937 *
938 * If there is only one gate, the frames are transferred from the failed mpath
939 * queue to that gate's queue. If there are more than one gates, the frames
940 * are copied from each gate to the next. After frames are copied, the
941 * mpath queues are emptied onto the transmission queue.
942 */
943int mesh_path_send_to_gates(struct mesh_path *mpath)
944{
945 struct ieee80211_sub_if_data *sdata = mpath->sdata;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700946 struct mesh_table *tbl;
947 struct mesh_path *from_mpath = mpath;
948 struct mpath_node *gate = NULL;
949 bool copy = false;
950 struct hlist_head *known_gates;
951
952 rcu_read_lock();
953 tbl = rcu_dereference(mesh_paths);
954 known_gates = tbl->known_gates;
955 rcu_read_unlock();
956
957 if (!known_gates)
958 return -EHOSTUNREACH;
959
Sasha Levinb67bfe02013-02-27 17:06:00 -0800960 hlist_for_each_entry_rcu(gate, known_gates, list) {
Javier Cardona5ee68e52011-08-09 16:45:08 -0700961 if (gate->mpath->sdata != sdata)
962 continue;
963
964 if (gate->mpath->flags & MESH_PATH_ACTIVE) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200965 mpath_dbg(sdata, "Forwarding to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700966 mesh_path_move_to_queue(gate->mpath, from_mpath, copy);
967 from_mpath = gate->mpath;
968 copy = true;
969 } else {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200970 mpath_dbg(sdata,
971 "Not forwarding %p (flags %#x)\n",
972 gate->mpath, gate->mpath->flags);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700973 }
974 }
975
Sasha Levinb67bfe02013-02-27 17:06:00 -0800976 hlist_for_each_entry_rcu(gate, known_gates, list)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700977 if (gate->mpath->sdata == sdata) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200978 mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700979 mesh_path_tx_pending(gate->mpath);
980 }
981
982 return (from_mpath == mpath) ? -EHOSTUNREACH : 0;
983}
984
985/**
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100986 * mesh_path_discard_frame - discard a frame whose path could not be resolved
987 *
988 * @skb: frame to discard
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200989 * @sdata: network subif the frame was to be sent through
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100990 *
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100991 * Locking: the function must me called within a rcu_read_lock region
992 */
Johannes Bergbf7cd942013-02-15 14:40:31 +0100993void mesh_path_discard_frame(struct ieee80211_sub_if_data *sdata,
994 struct sk_buff *skb)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100995{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100996 kfree_skb(skb);
Johannes Berg472dbc42008-09-11 00:01:49 +0200997 sdata->u.mesh.mshstats.dropped_frames_no_route++;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100998}
999
1000/**
1001 * mesh_path_flush_pending - free the pending queue of a mesh path
1002 *
1003 * @mpath: mesh path whose queue has to be freed
1004 *
Lucas De Marchi25985ed2011-03-30 22:57:33 -03001005 * Locking: the function must me called within a rcu_read_lock region
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001006 */
1007void mesh_path_flush_pending(struct mesh_path *mpath)
1008{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001009 struct sk_buff *skb;
1010
Javier Cardona00e3f252011-08-09 16:45:07 -07001011 while ((skb = skb_dequeue(&mpath->frame_queue)) != NULL)
Johannes Bergbf7cd942013-02-15 14:40:31 +01001012 mesh_path_discard_frame(mpath->sdata, skb);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001013}
1014
1015/**
1016 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
1017 *
1018 * @mpath: the mesh path to modify
1019 * @next_hop: the next hop to force
1020 *
1021 * Locking: this function must be called holding mpath->state_lock
1022 */
1023void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop)
1024{
1025 spin_lock_bh(&mpath->state_lock);
1026 mesh_path_assign_nexthop(mpath, next_hop);
Rui Paulod19b3bf2009-11-09 23:46:55 +00001027 mpath->sn = 0xffff;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001028 mpath->metric = 0;
1029 mpath->hop_count = 0;
1030 mpath->exp_time = 0;
1031 mpath->flags |= MESH_PATH_FIXED;
1032 mesh_path_activate(mpath);
1033 spin_unlock_bh(&mpath->state_lock);
1034 mesh_path_tx_pending(mpath);
1035}
1036
1037static void mesh_path_node_free(struct hlist_node *p, bool free_leafs)
1038{
1039 struct mesh_path *mpath;
1040 struct mpath_node *node = hlist_entry(p, struct mpath_node, list);
1041 mpath = node->mpath;
1042 hlist_del_rcu(p);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001043 if (free_leafs) {
1044 del_timer_sync(&mpath->timer);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001045 kfree(mpath);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001046 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001047 kfree(node);
1048}
1049
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001050static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001051{
1052 struct mesh_path *mpath;
1053 struct mpath_node *node, *new_node;
1054 u32 hash_idx;
1055
Pavel Emelyanov8566dc32008-05-07 19:51:51 +04001056 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov00242c42008-05-07 19:48:14 +04001057 if (new_node == NULL)
1058 return -ENOMEM;
1059
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001060 node = hlist_entry(p, struct mpath_node, list);
1061 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001062 new_node->mpath = mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001063 hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001064 hlist_add_head(&new_node->list,
1065 &newtbl->hash_buckets[hash_idx]);
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001066 return 0;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001067}
1068
1069int mesh_pathtbl_init(void)
1070{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001071 struct mesh_table *tbl_path, *tbl_mpp;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001072 int ret;
YanBo79617de2008-09-22 13:30:32 +08001073
Johannes Berg349eb8c2011-05-14 11:56:16 +02001074 tbl_path = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1075 if (!tbl_path)
1076 return -ENOMEM;
1077 tbl_path->free_node = &mesh_path_node_free;
1078 tbl_path->copy_node = &mesh_path_node_copy;
1079 tbl_path->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001080 tbl_path->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001081 if (!tbl_path->known_gates) {
1082 ret = -ENOMEM;
1083 goto free_path;
1084 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001085 INIT_HLIST_HEAD(tbl_path->known_gates);
1086
Johannes Berg349eb8c2011-05-14 11:56:16 +02001087
1088 tbl_mpp = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1089 if (!tbl_mpp) {
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001090 ret = -ENOMEM;
1091 goto free_path;
YanBo79617de2008-09-22 13:30:32 +08001092 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001093 tbl_mpp->free_node = &mesh_path_node_free;
1094 tbl_mpp->copy_node = &mesh_path_node_copy;
1095 tbl_mpp->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001096 tbl_mpp->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001097 if (!tbl_mpp->known_gates) {
1098 ret = -ENOMEM;
1099 goto free_mpp;
1100 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001101 INIT_HLIST_HEAD(tbl_mpp->known_gates);
Johannes Berg349eb8c2011-05-14 11:56:16 +02001102
1103 /* Need no locking since this is during init */
1104 RCU_INIT_POINTER(mesh_paths, tbl_path);
1105 RCU_INIT_POINTER(mpp_paths, tbl_mpp);
YanBo79617de2008-09-22 13:30:32 +08001106
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001107 return 0;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001108
1109free_mpp:
1110 mesh_table_free(tbl_mpp, true);
1111free_path:
1112 mesh_table_free(tbl_path, true);
1113 return ret;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001114}
1115
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001116void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001117{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001118 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001119 struct mesh_path *mpath;
1120 struct mpath_node *node;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001121 int i;
1122
Johannes Berg349eb8c2011-05-14 11:56:16 +02001123 rcu_read_lock();
1124 tbl = rcu_dereference(mesh_paths);
Sasha Levinb67bfe02013-02-27 17:06:00 -08001125 for_each_mesh_entry(tbl, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001126 if (node->mpath->sdata != sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001127 continue;
1128 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001129 if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
1130 (!(mpath->flags & MESH_PATH_FIXED)) &&
Javier Cardonaf5e50cd2011-08-29 13:23:05 -07001131 time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
Johannes Bergbf7cd942013-02-15 14:40:31 +01001132 mesh_path_del(mpath->sdata, mpath->dst);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001133 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001134 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001135}
1136
1137void mesh_pathtbl_unregister(void)
1138{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001139 /* no need for locking during exit path */
Eric Dumazet33d480c2011-08-11 19:30:52 +00001140 mesh_table_free(rcu_dereference_protected(mesh_paths, 1), true);
1141 mesh_table_free(rcu_dereference_protected(mpp_paths, 1), true);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001142}