blob: b819d6b847d0ebe64fc20dc7d2e98da89e147a5b [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
27#define MPATH_EXPIRED(mpath) ((mpath->flags & MESH_PATH_ACTIVE) && \
28 time_after(jiffies, mpath->exp_time) && \
29 !(mpath->flags & MESH_PATH_FIXED))
30
31struct mpath_node {
32 struct hlist_node list;
33 struct rcu_head rcu;
34 /* This indirection allows two different tables to point to the same
35 * mesh_path structure, useful when resizing
36 */
37 struct mesh_path *mpath;
38};
39
Johannes Berg349eb8c2011-05-14 11:56:16 +020040static struct mesh_table __rcu *mesh_paths;
41static struct mesh_table __rcu *mpp_paths; /* Store paths for MPP&MAP */
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010042
Johannes Bergf5ea9122009-08-07 16:17:38 +020043int mesh_paths_generation;
Johannes Berg6b86bd62011-05-12 13:38:50 +020044
45/* This lock will have the grow table function as writer and add / delete nodes
Javier Cardona239289e2011-08-29 13:23:09 -070046 * as readers. RCU provides sufficient protection only when reading the table
47 * (i.e. doing lookups). Adding or adding or removing nodes requires we take
48 * the read lock or we risk operating on an old table. The write lock is only
49 * needed when modifying the number of buckets a table.
Johannes Berg6b86bd62011-05-12 13:38:50 +020050 */
51static DEFINE_RWLOCK(pathtbl_resize_lock);
52
53
Johannes Berg349eb8c2011-05-14 11:56:16 +020054static inline struct mesh_table *resize_dereference_mesh_paths(void)
55{
56 return rcu_dereference_protected(mesh_paths,
57 lockdep_is_held(&pathtbl_resize_lock));
58}
59
60static inline struct mesh_table *resize_dereference_mpp_paths(void)
61{
62 return rcu_dereference_protected(mpp_paths,
63 lockdep_is_held(&pathtbl_resize_lock));
64}
65
66/*
67 * CAREFUL -- "tbl" must not be an expression,
68 * in particular not an rcu_dereference(), since
69 * it's used twice. So it is illegal to do
70 * for_each_mesh_entry(rcu_dereference(...), ...)
71 */
72#define for_each_mesh_entry(tbl, p, node, i) \
73 for (i = 0; i <= tbl->hash_mask; i++) \
74 hlist_for_each_entry_rcu(node, p, &tbl->hash_buckets[i], list)
75
76
Johannes Berg6b86bd62011-05-12 13:38:50 +020077static struct mesh_table *mesh_table_alloc(int size_order)
78{
79 int i;
80 struct mesh_table *newtbl;
81
Javier Cardonad676ff42011-05-17 16:13:34 -070082 newtbl = kmalloc(sizeof(struct mesh_table), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020083 if (!newtbl)
84 return NULL;
85
86 newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) *
Javier Cardonad676ff42011-05-17 16:13:34 -070087 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020088
89 if (!newtbl->hash_buckets) {
90 kfree(newtbl);
91 return NULL;
92 }
93
94 newtbl->hashwlock = kmalloc(sizeof(spinlock_t) *
Javier Cardonad676ff42011-05-17 16:13:34 -070095 (1 << size_order), GFP_ATOMIC);
Johannes Berg6b86bd62011-05-12 13:38:50 +020096 if (!newtbl->hashwlock) {
97 kfree(newtbl->hash_buckets);
98 kfree(newtbl);
99 return NULL;
100 }
101
102 newtbl->size_order = size_order;
103 newtbl->hash_mask = (1 << size_order) - 1;
104 atomic_set(&newtbl->entries, 0);
105 get_random_bytes(&newtbl->hash_rnd,
106 sizeof(newtbl->hash_rnd));
107 for (i = 0; i <= newtbl->hash_mask; i++)
108 spin_lock_init(&newtbl->hashwlock[i]);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700109 spin_lock_init(&newtbl->gates_lock);
Johannes Berg6b86bd62011-05-12 13:38:50 +0200110
111 return newtbl;
112}
113
Javier Cardona18889232009-08-10 12:15:52 -0700114static void __mesh_table_free(struct mesh_table *tbl)
115{
116 kfree(tbl->hash_buckets);
117 kfree(tbl->hashwlock);
118 kfree(tbl);
119}
120
Johannes Berg6b86bd62011-05-12 13:38:50 +0200121static void mesh_table_free(struct mesh_table *tbl, bool free_leafs)
Javier Cardona18889232009-08-10 12:15:52 -0700122{
123 struct hlist_head *mesh_hash;
124 struct hlist_node *p, *q;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700125 struct mpath_node *gate;
Javier Cardona18889232009-08-10 12:15:52 -0700126 int i;
127
128 mesh_hash = tbl->hash_buckets;
129 for (i = 0; i <= tbl->hash_mask; i++) {
Javier Cardona9b84b8082011-05-03 16:57:16 -0700130 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700131 hlist_for_each_safe(p, q, &mesh_hash[i]) {
132 tbl->free_node(p, free_leafs);
133 atomic_dec(&tbl->entries);
134 }
Javier Cardona9b84b8082011-05-03 16:57:16 -0700135 spin_unlock_bh(&tbl->hashwlock[i]);
Javier Cardona18889232009-08-10 12:15:52 -0700136 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700137 if (free_leafs) {
138 spin_lock_bh(&tbl->gates_lock);
139 hlist_for_each_entry_safe(gate, p, q,
140 tbl->known_gates, list) {
141 hlist_del(&gate->list);
142 kfree(gate);
143 }
144 kfree(tbl->known_gates);
145 spin_unlock_bh(&tbl->gates_lock);
146 }
147
Javier Cardona18889232009-08-10 12:15:52 -0700148 __mesh_table_free(tbl);
149}
150
cozybit Inca3e6b122011-04-13 11:10:28 -0700151static int mesh_table_grow(struct mesh_table *oldtbl,
Johannes Berg6b86bd62011-05-12 13:38:50 +0200152 struct mesh_table *newtbl)
Javier Cardona18889232009-08-10 12:15:52 -0700153{
Javier Cardona18889232009-08-10 12:15:52 -0700154 struct hlist_head *oldhash;
155 struct hlist_node *p, *q;
156 int i;
157
cozybit Inca3e6b122011-04-13 11:10:28 -0700158 if (atomic_read(&oldtbl->entries)
159 < oldtbl->mean_chain_len * (oldtbl->hash_mask + 1))
160 return -EAGAIN;
Javier Cardona18889232009-08-10 12:15:52 -0700161
cozybit Inca3e6b122011-04-13 11:10:28 -0700162 newtbl->free_node = oldtbl->free_node;
163 newtbl->mean_chain_len = oldtbl->mean_chain_len;
164 newtbl->copy_node = oldtbl->copy_node;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700165 newtbl->known_gates = oldtbl->known_gates;
cozybit Inca3e6b122011-04-13 11:10:28 -0700166 atomic_set(&newtbl->entries, atomic_read(&oldtbl->entries));
Javier Cardona18889232009-08-10 12:15:52 -0700167
cozybit Inca3e6b122011-04-13 11:10:28 -0700168 oldhash = oldtbl->hash_buckets;
169 for (i = 0; i <= oldtbl->hash_mask; i++)
Javier Cardona18889232009-08-10 12:15:52 -0700170 hlist_for_each(p, &oldhash[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700171 if (oldtbl->copy_node(p, newtbl) < 0)
Javier Cardona18889232009-08-10 12:15:52 -0700172 goto errcopy;
173
cozybit Inca3e6b122011-04-13 11:10:28 -0700174 return 0;
Javier Cardona18889232009-08-10 12:15:52 -0700175
176errcopy:
177 for (i = 0; i <= newtbl->hash_mask; i++) {
178 hlist_for_each_safe(p, q, &newtbl->hash_buckets[i])
cozybit Inca3e6b122011-04-13 11:10:28 -0700179 oldtbl->free_node(p, 0);
Javier Cardona18889232009-08-10 12:15:52 -0700180 }
cozybit Inca3e6b122011-04-13 11:10:28 -0700181 return -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700182}
183
Johannes Berg6b86bd62011-05-12 13:38:50 +0200184static u32 mesh_table_hash(u8 *addr, struct ieee80211_sub_if_data *sdata,
185 struct mesh_table *tbl)
186{
187 /* Use last four bytes of hw addr and interface index as hash index */
188 return jhash_2words(*(u32 *)(addr+2), sdata->dev->ifindex, tbl->hash_rnd)
189 & tbl->hash_mask;
190}
Johannes Bergf5ea9122009-08-07 16:17:38 +0200191
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100192
193/**
194 *
195 * mesh_path_assign_nexthop - update mesh path next hop
196 *
197 * @mpath: mesh path to update
198 * @sta: next hop to assign
199 *
200 * Locking: mpath->state_lock must be held when calling this function
201 */
202void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta)
203{
Javier Cardona10c836d2009-07-09 14:42:16 -0700204 struct sk_buff *skb;
205 struct ieee80211_hdr *hdr;
Javier Cardona10c836d2009-07-09 14:42:16 -0700206 unsigned long flags;
207
Johannes Bergd0709a62008-02-25 16:27:46 +0100208 rcu_assign_pointer(mpath->next_hop, sta);
Javier Cardona10c836d2009-07-09 14:42:16 -0700209
Javier Cardona10c836d2009-07-09 14:42:16 -0700210 spin_lock_irqsave(&mpath->frame_queue.lock, flags);
Thomas Pedersenb22bd522012-08-09 18:15:39 -0700211 skb_queue_walk(&mpath->frame_queue, skb) {
Javier Cardona10c836d2009-07-09 14:42:16 -0700212 hdr = (struct ieee80211_hdr *) skb->data;
213 memcpy(hdr->addr1, sta->sta.addr, ETH_ALEN);
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800214 memcpy(hdr->addr2, mpath->sdata->vif.addr, ETH_ALEN);
Javier Cardona10c836d2009-07-09 14:42:16 -0700215 }
216
Javier Cardona10c836d2009-07-09 14:42:16 -0700217 spin_unlock_irqrestore(&mpath->frame_queue.lock, flags);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100218}
219
Javier Cardona5ee68e52011-08-09 16:45:08 -0700220static void prepare_for_gate(struct sk_buff *skb, char *dst_addr,
221 struct mesh_path *gate_mpath)
222{
223 struct ieee80211_hdr *hdr;
224 struct ieee80211s_hdr *mshdr;
225 int mesh_hdrlen, hdrlen;
226 char *next_hop;
227
228 hdr = (struct ieee80211_hdr *) skb->data;
229 hdrlen = ieee80211_hdrlen(hdr->frame_control);
230 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
231
232 if (!(mshdr->flags & MESH_FLAGS_AE)) {
233 /* size of the fixed part of the mesh header */
234 mesh_hdrlen = 6;
235
236 /* make room for the two extended addresses */
237 skb_push(skb, 2 * ETH_ALEN);
238 memmove(skb->data, hdr, hdrlen + mesh_hdrlen);
239
240 hdr = (struct ieee80211_hdr *) skb->data;
241
242 /* we preserve the previous mesh header and only add
243 * the new addreses */
244 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen);
245 mshdr->flags = MESH_FLAGS_AE_A5_A6;
246 memcpy(mshdr->eaddr1, hdr->addr3, ETH_ALEN);
247 memcpy(mshdr->eaddr2, hdr->addr4, ETH_ALEN);
248 }
249
250 /* update next hop */
251 hdr = (struct ieee80211_hdr *) skb->data;
252 rcu_read_lock();
253 next_hop = rcu_dereference(gate_mpath->next_hop)->sta.addr;
254 memcpy(hdr->addr1, next_hop, ETH_ALEN);
255 rcu_read_unlock();
Thomas Pedersen7e3c8862011-11-24 17:15:21 -0800256 memcpy(hdr->addr2, gate_mpath->sdata->vif.addr, ETH_ALEN);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700257 memcpy(hdr->addr3, dst_addr, ETH_ALEN);
258}
259
260/**
261 *
262 * mesh_path_move_to_queue - Move or copy frames from one mpath queue to another
263 *
264 * This function is used to transfer or copy frames from an unresolved mpath to
265 * a gate mpath. The function also adds the Address Extension field and
266 * updates the next hop.
267 *
268 * If a frame already has an Address Extension field, only the next hop and
269 * destination addresses are updated.
270 *
271 * The gate mpath must be an active mpath with a valid mpath->next_hop.
272 *
273 * @mpath: An active mpath the frames will be sent to (i.e. the gate)
274 * @from_mpath: The failed mpath
275 * @copy: When true, copy all the frames to the new mpath queue. When false,
276 * move them.
277 */
278static void mesh_path_move_to_queue(struct mesh_path *gate_mpath,
279 struct mesh_path *from_mpath,
280 bool copy)
281{
Thomas Pedersenc6133662011-08-25 10:36:14 -0700282 struct sk_buff *skb, *cp_skb = NULL;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700283 struct sk_buff_head gateq, failq;
284 unsigned long flags;
285 int num_skbs;
286
287 BUG_ON(gate_mpath == from_mpath);
288 BUG_ON(!gate_mpath->next_hop);
289
290 __skb_queue_head_init(&gateq);
291 __skb_queue_head_init(&failq);
292
293 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
294 skb_queue_splice_init(&from_mpath->frame_queue, &failq);
295 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
296
297 num_skbs = skb_queue_len(&failq);
298
299 while (num_skbs--) {
300 skb = __skb_dequeue(&failq);
John W. Linville817a53d2011-08-24 15:12:41 -0400301 if (copy) {
Javier Cardona5ee68e52011-08-09 16:45:08 -0700302 cp_skb = skb_copy(skb, GFP_ATOMIC);
John W. Linville817a53d2011-08-24 15:12:41 -0400303 if (cp_skb)
304 __skb_queue_tail(&failq, cp_skb);
305 }
Javier Cardona5ee68e52011-08-09 16:45:08 -0700306
307 prepare_for_gate(skb, gate_mpath->dst, gate_mpath);
308 __skb_queue_tail(&gateq, skb);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700309 }
310
311 spin_lock_irqsave(&gate_mpath->frame_queue.lock, flags);
312 skb_queue_splice(&gateq, &gate_mpath->frame_queue);
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200313 mpath_dbg(gate_mpath->sdata, "Mpath queue for gate %pM has %d frames\n",
314 gate_mpath->dst, skb_queue_len(&gate_mpath->frame_queue));
Javier Cardona5ee68e52011-08-09 16:45:08 -0700315 spin_unlock_irqrestore(&gate_mpath->frame_queue.lock, flags);
316
317 if (!copy)
318 return;
319
320 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags);
321 skb_queue_splice(&failq, &from_mpath->frame_queue);
322 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags);
323}
324
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100325
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800326static struct mesh_path *mpath_lookup(struct mesh_table *tbl, u8 *dst,
Javier Cardona239289e2011-08-29 13:23:09 -0700327 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100328{
329 struct mesh_path *mpath;
330 struct hlist_node *n;
331 struct hlist_head *bucket;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100332 struct mpath_node *node;
333
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200334 bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100335 hlist_for_each_entry_rcu(node, n, bucket, list) {
336 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200337 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000338 ether_addr_equal(dst, mpath->dst)) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100339 if (MPATH_EXPIRED(mpath)) {
340 spin_lock_bh(&mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700341 mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100342 spin_unlock_bh(&mpath->state_lock);
343 }
344 return mpath;
345 }
346 }
347 return NULL;
348}
349
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100350/**
351 * mesh_path_lookup - look up a path in the mesh path table
352 * @dst: hardware address (ETH_ALEN length) of destination
353 * @sdata: local subif
354 *
355 * Returns: pointer to the mesh path structure, or NULL if not found
356 *
357 * Locking: must be called within a read rcu section.
358 */
359struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
360{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800361 return mpath_lookup(rcu_dereference(mesh_paths), dst, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100362}
363
YanBo79617de2008-09-22 13:30:32 +0800364struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
365{
Luis R. Rodriguez5ad20dd2012-02-07 21:09:25 -0800366 return mpath_lookup(rcu_dereference(mpp_paths), dst, sdata);
YanBo79617de2008-09-22 13:30:32 +0800367}
368
369
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100370/**
371 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
372 * @idx: index
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200373 * @sdata: local subif, or NULL for all entries
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100374 *
375 * Returns: pointer to the mesh path structure, or NULL if not found.
376 *
377 * Locking: must be called within a read rcu section.
378 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200379struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100380{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200381 struct mesh_table *tbl = rcu_dereference(mesh_paths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100382 struct mpath_node *node;
383 struct hlist_node *p;
384 int i;
385 int j = 0;
386
Johannes Berg349eb8c2011-05-14 11:56:16 +0200387 for_each_mesh_entry(tbl, p, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200388 if (sdata && node->mpath->sdata != sdata)
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800389 continue;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100390 if (j++ == idx) {
391 if (MPATH_EXPIRED(node->mpath)) {
392 spin_lock_bh(&node->mpath->state_lock);
Javier Cardonaad99d142011-08-29 13:23:06 -0700393 node->mpath->flags &= ~MESH_PATH_ACTIVE;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100394 spin_unlock_bh(&node->mpath->state_lock);
395 }
396 return node->mpath;
397 }
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800398 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100399
400 return NULL;
401}
402
Javier Cardona5ee68e52011-08-09 16:45:08 -0700403/**
Johannes Berg30be52e2011-11-21 11:23:50 +0100404 * mesh_path_add_gate - add the given mpath to a mesh gate to our path table
405 * @mpath: gate path to add to table
Javier Cardona5ee68e52011-08-09 16:45:08 -0700406 */
Johannes Berg30be52e2011-11-21 11:23:50 +0100407int mesh_path_add_gate(struct mesh_path *mpath)
Javier Cardona5ee68e52011-08-09 16:45:08 -0700408{
Johannes Berg30be52e2011-11-21 11:23:50 +0100409 struct mesh_table *tbl;
Javier Cardona5ee68e52011-08-09 16:45:08 -0700410 struct mpath_node *gate, *new_gate;
411 struct hlist_node *n;
412 int err;
413
414 rcu_read_lock();
Johannes Berg30be52e2011-11-21 11:23:50 +0100415 tbl = rcu_dereference(mesh_paths);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700416
417 hlist_for_each_entry_rcu(gate, n, tbl->known_gates, list)
418 if (gate->mpath == mpath) {
419 err = -EEXIST;
420 goto err_rcu;
421 }
422
423 new_gate = kzalloc(sizeof(struct mpath_node), GFP_ATOMIC);
424 if (!new_gate) {
425 err = -ENOMEM;
426 goto err_rcu;
427 }
428
429 mpath->is_gate = true;
430 mpath->sdata->u.mesh.num_gates++;
431 new_gate->mpath = mpath;
432 spin_lock_bh(&tbl->gates_lock);
433 hlist_add_head_rcu(&new_gate->list, tbl->known_gates);
434 spin_unlock_bh(&tbl->gates_lock);
435 rcu_read_unlock();
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200436 mpath_dbg(mpath->sdata,
437 "Mesh path: Recorded new gate: %pM. %d known gates\n",
438 mpath->dst, mpath->sdata->u.mesh.num_gates);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700439 return 0;
440err_rcu:
441 rcu_read_unlock();
442 return err;
443}
444
445/**
446 * mesh_gate_del - remove a mesh gate from the list of known gates
447 * @tbl: table which holds our list of known gates
448 * @mpath: gate mpath
449 *
450 * Returns: 0 on success
451 *
452 * Locking: must be called inside rcu_read_lock() section
453 */
454static int mesh_gate_del(struct mesh_table *tbl, struct mesh_path *mpath)
455{
456 struct mpath_node *gate;
457 struct hlist_node *p, *q;
458
Javier Cardona5ee68e52011-08-09 16:45:08 -0700459 hlist_for_each_entry_safe(gate, p, q, tbl->known_gates, list)
460 if (gate->mpath == mpath) {
461 spin_lock_bh(&tbl->gates_lock);
462 hlist_del_rcu(&gate->list);
Paul E. McKenneyae1f18e2012-01-06 17:10:37 -0800463 kfree_rcu(gate, rcu);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700464 spin_unlock_bh(&tbl->gates_lock);
465 mpath->sdata->u.mesh.num_gates--;
466 mpath->is_gate = false;
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200467 mpath_dbg(mpath->sdata,
468 "Mesh path: Deleted gate: %pM. %d known gates\n",
Javier Cardona5ee68e52011-08-09 16:45:08 -0700469 mpath->dst, mpath->sdata->u.mesh.num_gates);
470 break;
471 }
472
473 return 0;
474}
475
476/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700477 * mesh_gate_num - number of gates known to this interface
478 * @sdata: subif data
479 */
480int mesh_gate_num(struct ieee80211_sub_if_data *sdata)
481{
482 return sdata->u.mesh.num_gates;
483}
484
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100485/**
486 * mesh_path_add - allocate and add a new path to the mesh path table
487 * @addr: destination address of the path (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200488 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100489 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200490 * Returns: 0 on success
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100491 *
492 * State: the initial state of the new path is set to 0
493 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200494int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100495{
Javier Cardona18889232009-08-10 12:15:52 -0700496 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
497 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200498 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100499 struct mesh_path *mpath, *new_mpath;
500 struct mpath_node *node, *new_node;
501 struct hlist_head *bucket;
502 struct hlist_node *n;
503 int grow = 0;
504 int err = 0;
505 u32 hash_idx;
506
Joe Perchesb203ca32012-05-08 18:56:52 +0000507 if (ether_addr_equal(dst, sdata->vif.addr))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100508 /* never add ourselves as neighbours */
509 return -ENOTSUPP;
510
511 if (is_multicast_ether_addr(dst))
512 return -ENOTSUPP;
513
Johannes Berg472dbc42008-09-11 00:01:49 +0200514 if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100515 return -ENOSPC;
516
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400517 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700518 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400519 if (!new_mpath)
520 goto err_path_alloc;
521
Javier Cardona18889232009-08-10 12:15:52 -0700522 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400523 if (!new_node)
524 goto err_node_alloc;
Pavel Emelyanovf84e71a2008-05-06 18:46:36 +0400525
Javier Cardona9b84b8082011-05-03 16:57:16 -0700526 read_lock_bh(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100527 memcpy(new_mpath->dst, dst, ETH_ALEN);
Johannes Berge83e6542012-07-13 16:23:07 +0200528 eth_broadcast_addr(new_mpath->rann_snd_addr);
Chun-Yeow Yeoh35bcd592012-04-10 12:31:56 +0800529 new_mpath->is_root = false;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200530 new_mpath->sdata = sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100531 new_mpath->flags = 0;
532 skb_queue_head_init(&new_mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100533 new_node->mpath = new_mpath;
534 new_mpath->timer.data = (unsigned long) new_mpath;
535 new_mpath->timer.function = mesh_path_timer;
536 new_mpath->exp_time = jiffies;
537 spin_lock_init(&new_mpath->state_lock);
538 init_timer(&new_mpath->timer);
539
Johannes Berg349eb8c2011-05-14 11:56:16 +0200540 tbl = resize_dereference_mesh_paths();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100541
Johannes Berg349eb8c2011-05-14 11:56:16 +0200542 hash_idx = mesh_table_hash(dst, sdata, tbl);
543 bucket = &tbl->hash_buckets[hash_idx];
544
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800545 spin_lock(&tbl->hashwlock[hash_idx]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100546
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400547 err = -EEXIST;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100548 hlist_for_each_entry(node, n, bucket, list) {
549 mpath = node->mpath;
Felix Fietkau888d04d2012-03-01 15:22:09 +0100550 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000551 ether_addr_equal(dst, mpath->dst))
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400552 goto err_exists;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100553 }
554
555 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200556 if (atomic_inc_return(&tbl->entries) >=
557 tbl->mean_chain_len * (tbl->hash_mask + 1))
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100558 grow = 1;
559
Johannes Bergf5ea9122009-08-07 16:17:38 +0200560 mesh_paths_generation++;
561
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800562 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700563 read_unlock_bh(&pathtbl_resize_lock);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400564 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700565 set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200566 ieee80211_queue_work(&local->hw, &sdata->work);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100567 }
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400568 return 0;
569
570err_exists:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800571 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700572 read_unlock_bh(&pathtbl_resize_lock);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400573 kfree(new_node);
574err_node_alloc:
575 kfree(new_mpath);
576err_path_alloc:
Johannes Berg472dbc42008-09-11 00:01:49 +0200577 atomic_dec(&sdata->u.mesh.mpaths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100578 return err;
579}
580
Johannes Berg1928eca2011-05-14 11:00:52 +0200581static void mesh_table_free_rcu(struct rcu_head *rcu)
582{
583 struct mesh_table *tbl = container_of(rcu, struct mesh_table, rcu_head);
584
585 mesh_table_free(tbl, false);
586}
587
Javier Cardona18889232009-08-10 12:15:52 -0700588void mesh_mpath_table_grow(void)
589{
590 struct mesh_table *oldtbl, *newtbl;
591
Javier Cardona9b84b8082011-05-03 16:57:16 -0700592 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200593 oldtbl = resize_dereference_mesh_paths();
594 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200595 if (!newtbl)
596 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200597 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700598 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200599 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700600 }
601 rcu_assign_pointer(mesh_paths, newtbl);
Javier Cardona18889232009-08-10 12:15:52 -0700602
Johannes Berg1928eca2011-05-14 11:00:52 +0200603 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
604
605 out:
606 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700607}
608
609void mesh_mpp_table_grow(void)
610{
611 struct mesh_table *oldtbl, *newtbl;
612
Javier Cardona9b84b8082011-05-03 16:57:16 -0700613 write_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200614 oldtbl = resize_dereference_mpp_paths();
615 newtbl = mesh_table_alloc(oldtbl->size_order + 1);
Johannes Berg1928eca2011-05-14 11:00:52 +0200616 if (!newtbl)
617 goto out;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200618 if (mesh_table_grow(oldtbl, newtbl) < 0) {
cozybit Inca3e6b122011-04-13 11:10:28 -0700619 __mesh_table_free(newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200620 goto out;
Javier Cardona18889232009-08-10 12:15:52 -0700621 }
622 rcu_assign_pointer(mpp_paths, newtbl);
Johannes Berg1928eca2011-05-14 11:00:52 +0200623 call_rcu(&oldtbl->rcu_head, mesh_table_free_rcu);
Javier Cardona18889232009-08-10 12:15:52 -0700624
Johannes Berg1928eca2011-05-14 11:00:52 +0200625 out:
626 write_unlock_bh(&pathtbl_resize_lock);
Javier Cardona18889232009-08-10 12:15:52 -0700627}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100628
YanBo79617de2008-09-22 13:30:32 +0800629int mpp_path_add(u8 *dst, u8 *mpp, struct ieee80211_sub_if_data *sdata)
630{
Javier Cardona18889232009-08-10 12:15:52 -0700631 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
632 struct ieee80211_local *local = sdata->local;
Johannes Berg349eb8c2011-05-14 11:56:16 +0200633 struct mesh_table *tbl;
YanBo79617de2008-09-22 13:30:32 +0800634 struct mesh_path *mpath, *new_mpath;
635 struct mpath_node *node, *new_node;
636 struct hlist_head *bucket;
637 struct hlist_node *n;
638 int grow = 0;
639 int err = 0;
640 u32 hash_idx;
641
Joe Perchesb203ca32012-05-08 18:56:52 +0000642 if (ether_addr_equal(dst, sdata->vif.addr))
YanBo79617de2008-09-22 13:30:32 +0800643 /* never add ourselves as neighbours */
644 return -ENOTSUPP;
645
646 if (is_multicast_ether_addr(dst))
647 return -ENOTSUPP;
648
649 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700650 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800651 if (!new_mpath)
652 goto err_path_alloc;
653
Javier Cardona18889232009-08-10 12:15:52 -0700654 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800655 if (!new_node)
656 goto err_node_alloc;
657
Javier Cardona9b84b8082011-05-03 16:57:16 -0700658 read_lock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800659 memcpy(new_mpath->dst, dst, ETH_ALEN);
660 memcpy(new_mpath->mpp, mpp, ETH_ALEN);
661 new_mpath->sdata = sdata;
662 new_mpath->flags = 0;
663 skb_queue_head_init(&new_mpath->frame_queue);
664 new_node->mpath = new_mpath;
Thomas Pedersenc6133662011-08-25 10:36:14 -0700665 init_timer(&new_mpath->timer);
YanBo79617de2008-09-22 13:30:32 +0800666 new_mpath->exp_time = jiffies;
667 spin_lock_init(&new_mpath->state_lock);
668
Johannes Berg349eb8c2011-05-14 11:56:16 +0200669 tbl = resize_dereference_mpp_paths();
YanBo79617de2008-09-22 13:30:32 +0800670
Johannes Berg349eb8c2011-05-14 11:56:16 +0200671 hash_idx = mesh_table_hash(dst, sdata, tbl);
672 bucket = &tbl->hash_buckets[hash_idx];
673
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800674 spin_lock(&tbl->hashwlock[hash_idx]);
YanBo79617de2008-09-22 13:30:32 +0800675
676 err = -EEXIST;
677 hlist_for_each_entry(node, n, bucket, list) {
678 mpath = node->mpath;
Felix Fietkau888d04d2012-03-01 15:22:09 +0100679 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000680 ether_addr_equal(dst, mpath->dst))
YanBo79617de2008-09-22 13:30:32 +0800681 goto err_exists;
682 }
683
684 hlist_add_head_rcu(&new_node->list, bucket);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200685 if (atomic_inc_return(&tbl->entries) >=
686 tbl->mean_chain_len * (tbl->hash_mask + 1))
YanBo79617de2008-09-22 13:30:32 +0800687 grow = 1;
688
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800689 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700690 read_unlock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800691 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700692 set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200693 ieee80211_queue_work(&local->hw, &sdata->work);
YanBo79617de2008-09-22 13:30:32 +0800694 }
695 return 0;
696
697err_exists:
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800698 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700699 read_unlock_bh(&pathtbl_resize_lock);
YanBo79617de2008-09-22 13:30:32 +0800700 kfree(new_node);
701err_node_alloc:
702 kfree(new_mpath);
703err_path_alloc:
704 return err;
705}
706
707
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100708/**
709 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
710 *
711 * @sta: broken peer link
712 *
713 * This function must be called from the rate control algorithm if enough
714 * delivery errors suggest that a peer link is no longer usable.
715 */
716void mesh_plink_broken(struct sta_info *sta)
717{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200718 struct mesh_table *tbl;
Johannes Berg15ff6362009-11-17 13:34:04 +0100719 static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100720 struct mesh_path *mpath;
721 struct mpath_node *node;
722 struct hlist_node *p;
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);
729 for_each_mesh_entry(tbl, p, 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);
Javier Cardona45904f22010-12-03 09:20:40 +0100738 mesh_path_error_tx(sdata->u.mesh.mshcfg.element_ttl,
739 mpath->dst, cpu_to_le32(mpath->sn),
Thomas Pedersen25d49e42011-08-11 19:35:15 -0700740 reason, bcast, sdata);
Javier Cardonaf5e50cd2011-08-29 13:23:05 -0700741 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100742 }
743 rcu_read_unlock();
744}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100745
Javier Cardona19c50b32011-08-29 13:23:07 -0700746static void mesh_path_node_reclaim(struct rcu_head *rp)
747{
748 struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
749 struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
750
751 del_timer_sync(&node->mpath->timer);
752 atomic_dec(&sdata->u.mesh.mpaths);
753 kfree(node->mpath);
754 kfree(node);
755}
756
757/* needs to be called with the corresponding hashwlock taken */
758static void __mesh_path_del(struct mesh_table *tbl, struct mpath_node *node)
759{
760 struct mesh_path *mpath;
761 mpath = node->mpath;
762 spin_lock(&mpath->state_lock);
763 mpath->flags |= MESH_PATH_RESOLVING;
764 if (mpath->is_gate)
765 mesh_gate_del(tbl, mpath);
766 hlist_del_rcu(&node->list);
767 call_rcu(&node->rcu, mesh_path_node_reclaim);
768 spin_unlock(&mpath->state_lock);
769 atomic_dec(&tbl->entries);
770}
771
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100772/**
773 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
774 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000775 * @sta: mesh peer to match
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100776 *
Luis Carlos Cobob4e08ea2008-02-29 15:46:08 -0800777 * RCU notes: this function is called when a mesh plink transitions from
778 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
779 * allows path creation. This will happen before the sta can be freed (because
Johannes Bergd0709a62008-02-25 16:27:46 +0100780 * sta_info_destroy() calls this) so any reader in a rcu read block will be
781 * protected against the plink disappearing.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100782 */
783void mesh_path_flush_by_nexthop(struct sta_info *sta)
784{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200785 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100786 struct mesh_path *mpath;
787 struct mpath_node *node;
788 struct hlist_node *p;
789 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();
Johannes Berg349eb8c2011-05-14 11:56:16 +0200794 for_each_mesh_entry(tbl, p, 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;
811 struct hlist_node *p;
812 int i;
813
Javier Cardonacd72e812011-08-29 13:23:08 -0700814 WARN_ON(!rcu_read_lock_held());
Johannes Berg349eb8c2011-05-14 11:56:16 +0200815 for_each_mesh_entry(tbl, p, node, i) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100816 mpath = node->mpath;
Javier Cardonacd72e812011-08-29 13:23:08 -0700817 if (mpath->sdata != sdata)
818 continue;
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700819 spin_lock_bh(&tbl->hashwlock[i]);
Javier Cardona19c50b32011-08-29 13:23:07 -0700820 __mesh_path_del(tbl, node);
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700821 spin_unlock_bh(&tbl->hashwlock[i]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100822 }
823}
824
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700825/**
826 * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface
827 *
828 * This function deletes both mesh paths as well as mesh portal paths.
829 *
Ben Hutchings2c530402012-07-10 10:55:09 +0000830 * @sdata: interface data to match
Javier Cardonaece1a2e2011-08-29 13:23:04 -0700831 *
832 */
833void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100834{
Javier Cardonacd72e812011-08-29 13:23:08 -0700835 struct mesh_table *tbl;
Johannes Bergd0709a62008-02-25 16:27:46 +0100836
Javier Cardonacd72e812011-08-29 13:23:08 -0700837 rcu_read_lock();
Javier Cardona239289e2011-08-29 13:23:09 -0700838 read_lock_bh(&pathtbl_resize_lock);
839 tbl = resize_dereference_mesh_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700840 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700841 tbl = resize_dereference_mpp_paths();
Javier Cardonacd72e812011-08-29 13:23:08 -0700842 table_flush_by_iface(tbl, sdata);
Javier Cardona239289e2011-08-29 13:23:09 -0700843 read_unlock_bh(&pathtbl_resize_lock);
Javier Cardonacd72e812011-08-29 13:23:08 -0700844 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100845}
846
847/**
848 * mesh_path_del - delete a mesh path from the table
849 *
850 * @addr: dst address (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200851 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100852 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200853 * Returns: 0 if successful
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100854 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200855int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100856{
Johannes Berg349eb8c2011-05-14 11:56:16 +0200857 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100858 struct mesh_path *mpath;
859 struct mpath_node *node;
860 struct hlist_head *bucket;
861 struct hlist_node *n;
862 int hash_idx;
863 int err = 0;
864
Javier Cardona9b84b8082011-05-03 16:57:16 -0700865 read_lock_bh(&pathtbl_resize_lock);
Johannes Berg349eb8c2011-05-14 11:56:16 +0200866 tbl = resize_dereference_mesh_paths();
867 hash_idx = mesh_table_hash(addr, sdata, tbl);
868 bucket = &tbl->hash_buckets[hash_idx];
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100869
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800870 spin_lock(&tbl->hashwlock[hash_idx]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100871 hlist_for_each_entry(node, n, bucket, list) {
872 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200873 if (mpath->sdata == sdata &&
Joe Perchesb203ca32012-05-08 18:56:52 +0000874 ether_addr_equal(addr, mpath->dst)) {
Javier Cardona19c50b32011-08-29 13:23:07 -0700875 __mesh_path_del(tbl, node);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100876 goto enddel;
877 }
878 }
879
880 err = -ENXIO;
881enddel:
Johannes Bergf5ea9122009-08-07 16:17:38 +0200882 mesh_paths_generation++;
Thomas Pedersenf06c7882012-03-06 16:42:09 -0800883 spin_unlock(&tbl->hashwlock[hash_idx]);
Javier Cardona9b84b8082011-05-03 16:57:16 -0700884 read_unlock_bh(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100885 return err;
886}
887
888/**
889 * mesh_path_tx_pending - sends pending frames in a mesh path queue
890 *
891 * @mpath: mesh path to activate
892 *
893 * Locking: the state_lock of the mpath structure must NOT be held when calling
894 * this function.
895 */
896void mesh_path_tx_pending(struct mesh_path *mpath)
897{
Javier Cardona249b4052009-07-07 10:55:03 -0700898 if (mpath->flags & MESH_PATH_ACTIVE)
899 ieee80211_add_pending_skbs(mpath->sdata->local,
900 &mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100901}
902
903/**
Javier Cardona5ee68e52011-08-09 16:45:08 -0700904 * mesh_path_send_to_gates - sends pending frames to all known mesh gates
905 *
906 * @mpath: mesh path whose queue will be emptied
907 *
908 * If there is only one gate, the frames are transferred from the failed mpath
909 * queue to that gate's queue. If there are more than one gates, the frames
910 * are copied from each gate to the next. After frames are copied, the
911 * mpath queues are emptied onto the transmission queue.
912 */
913int mesh_path_send_to_gates(struct mesh_path *mpath)
914{
915 struct ieee80211_sub_if_data *sdata = mpath->sdata;
916 struct hlist_node *n;
917 struct mesh_table *tbl;
918 struct mesh_path *from_mpath = mpath;
919 struct mpath_node *gate = NULL;
920 bool copy = false;
921 struct hlist_head *known_gates;
922
923 rcu_read_lock();
924 tbl = rcu_dereference(mesh_paths);
925 known_gates = tbl->known_gates;
926 rcu_read_unlock();
927
928 if (!known_gates)
929 return -EHOSTUNREACH;
930
931 hlist_for_each_entry_rcu(gate, n, known_gates, list) {
932 if (gate->mpath->sdata != sdata)
933 continue;
934
935 if (gate->mpath->flags & MESH_PATH_ACTIVE) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200936 mpath_dbg(sdata, "Forwarding to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700937 mesh_path_move_to_queue(gate->mpath, from_mpath, copy);
938 from_mpath = gate->mpath;
939 copy = true;
940 } else {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200941 mpath_dbg(sdata,
942 "Not forwarding %p (flags %#x)\n",
943 gate->mpath, gate->mpath->flags);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700944 }
945 }
946
947 hlist_for_each_entry_rcu(gate, n, known_gates, list)
948 if (gate->mpath->sdata == sdata) {
Johannes Bergbdcbd8e2012-06-22 11:29:50 +0200949 mpath_dbg(sdata, "Sending to %pM\n", gate->mpath->dst);
Javier Cardona5ee68e52011-08-09 16:45:08 -0700950 mesh_path_tx_pending(gate->mpath);
951 }
952
953 return (from_mpath == mpath) ? -EHOSTUNREACH : 0;
954}
955
956/**
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100957 * mesh_path_discard_frame - discard a frame whose path could not be resolved
958 *
959 * @skb: frame to discard
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200960 * @sdata: network subif the frame was to be sent through
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100961 *
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100962 * Locking: the function must me called within a rcu_read_lock region
963 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200964void mesh_path_discard_frame(struct sk_buff *skb,
965 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100966{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100967 kfree_skb(skb);
Johannes Berg472dbc42008-09-11 00:01:49 +0200968 sdata->u.mesh.mshstats.dropped_frames_no_route++;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100969}
970
971/**
972 * mesh_path_flush_pending - free the pending queue of a mesh path
973 *
974 * @mpath: mesh path whose queue has to be freed
975 *
Lucas De Marchi25985ed2011-03-30 22:57:33 -0300976 * Locking: the function must me called within a rcu_read_lock region
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100977 */
978void mesh_path_flush_pending(struct mesh_path *mpath)
979{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100980 struct sk_buff *skb;
981
Javier Cardona00e3f252011-08-09 16:45:07 -0700982 while ((skb = skb_dequeue(&mpath->frame_queue)) != NULL)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200983 mesh_path_discard_frame(skb, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100984}
985
986/**
987 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
988 *
989 * @mpath: the mesh path to modify
990 * @next_hop: the next hop to force
991 *
992 * Locking: this function must be called holding mpath->state_lock
993 */
994void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop)
995{
996 spin_lock_bh(&mpath->state_lock);
997 mesh_path_assign_nexthop(mpath, next_hop);
Rui Paulod19b3bf2009-11-09 23:46:55 +0000998 mpath->sn = 0xffff;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100999 mpath->metric = 0;
1000 mpath->hop_count = 0;
1001 mpath->exp_time = 0;
1002 mpath->flags |= MESH_PATH_FIXED;
1003 mesh_path_activate(mpath);
1004 spin_unlock_bh(&mpath->state_lock);
1005 mesh_path_tx_pending(mpath);
1006}
1007
1008static void mesh_path_node_free(struct hlist_node *p, bool free_leafs)
1009{
1010 struct mesh_path *mpath;
1011 struct mpath_node *node = hlist_entry(p, struct mpath_node, list);
1012 mpath = node->mpath;
1013 hlist_del_rcu(p);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001014 if (free_leafs) {
1015 del_timer_sync(&mpath->timer);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001016 kfree(mpath);
Javier Cardonad0df9ee2011-05-13 14:16:07 -07001017 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001018 kfree(node);
1019}
1020
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001021static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001022{
1023 struct mesh_path *mpath;
1024 struct mpath_node *node, *new_node;
1025 u32 hash_idx;
1026
Pavel Emelyanov8566dc32008-05-07 19:51:51 +04001027 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov00242c42008-05-07 19:48:14 +04001028 if (new_node == NULL)
1029 return -ENOMEM;
1030
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001031 node = hlist_entry(p, struct mpath_node, list);
1032 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001033 new_node->mpath = mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001034 hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001035 hlist_add_head(&new_node->list,
1036 &newtbl->hash_buckets[hash_idx]);
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +04001037 return 0;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001038}
1039
1040int mesh_pathtbl_init(void)
1041{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001042 struct mesh_table *tbl_path, *tbl_mpp;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001043 int ret;
YanBo79617de2008-09-22 13:30:32 +08001044
Johannes Berg349eb8c2011-05-14 11:56:16 +02001045 tbl_path = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1046 if (!tbl_path)
1047 return -ENOMEM;
1048 tbl_path->free_node = &mesh_path_node_free;
1049 tbl_path->copy_node = &mesh_path_node_copy;
1050 tbl_path->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001051 tbl_path->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001052 if (!tbl_path->known_gates) {
1053 ret = -ENOMEM;
1054 goto free_path;
1055 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001056 INIT_HLIST_HEAD(tbl_path->known_gates);
1057
Johannes Berg349eb8c2011-05-14 11:56:16 +02001058
1059 tbl_mpp = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
1060 if (!tbl_mpp) {
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001061 ret = -ENOMEM;
1062 goto free_path;
YanBo79617de2008-09-22 13:30:32 +08001063 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001064 tbl_mpp->free_node = &mesh_path_node_free;
1065 tbl_mpp->copy_node = &mesh_path_node_copy;
1066 tbl_mpp->mean_chain_len = MEAN_CHAIN_LEN;
Javier Cardona5ee68e52011-08-09 16:45:08 -07001067 tbl_mpp->known_gates = kzalloc(sizeof(struct hlist_head), GFP_ATOMIC);
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001068 if (!tbl_mpp->known_gates) {
1069 ret = -ENOMEM;
1070 goto free_mpp;
1071 }
Javier Cardona5ee68e52011-08-09 16:45:08 -07001072 INIT_HLIST_HEAD(tbl_mpp->known_gates);
Johannes Berg349eb8c2011-05-14 11:56:16 +02001073
1074 /* Need no locking since this is during init */
1075 RCU_INIT_POINTER(mesh_paths, tbl_path);
1076 RCU_INIT_POINTER(mpp_paths, tbl_mpp);
YanBo79617de2008-09-22 13:30:32 +08001077
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001078 return 0;
Dan Carpenter4c5ade42011-08-30 22:16:15 +03001079
1080free_mpp:
1081 mesh_table_free(tbl_mpp, true);
1082free_path:
1083 mesh_table_free(tbl_path, true);
1084 return ret;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001085}
1086
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001087void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001088{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001089 struct mesh_table *tbl;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001090 struct mesh_path *mpath;
1091 struct mpath_node *node;
1092 struct hlist_node *p;
1093 int i;
1094
Johannes Berg349eb8c2011-05-14 11:56:16 +02001095 rcu_read_lock();
1096 tbl = rcu_dereference(mesh_paths);
1097 for_each_mesh_entry(tbl, p, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001098 if (node->mpath->sdata != sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001099 continue;
1100 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001101 if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
1102 (!(mpath->flags & MESH_PATH_FIXED)) &&
Javier Cardonaf5e50cd2011-08-29 13:23:05 -07001103 time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE))
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +12001104 mesh_path_del(mpath->dst, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001105 }
Johannes Berg349eb8c2011-05-14 11:56:16 +02001106 rcu_read_unlock();
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001107}
1108
1109void mesh_pathtbl_unregister(void)
1110{
Johannes Berg349eb8c2011-05-14 11:56:16 +02001111 /* no need for locking during exit path */
Eric Dumazet33d480c2011-08-11 19:30:52 +00001112 mesh_table_free(rcu_dereference_protected(mesh_paths, 1), true);
1113 mesh_table_free(rcu_dereference_protected(mpp_paths, 1), true);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +01001114}