blob: 349e466cf08b06825a45d5923dae2c167fa0d82f [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>
17#include "ieee80211_i.h"
18#include "mesh.h"
19
20/* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */
21#define INIT_PATHS_SIZE_ORDER 2
22
23/* Keep the mean chain length below this constant */
24#define MEAN_CHAIN_LEN 2
25
26#define MPATH_EXPIRED(mpath) ((mpath->flags & MESH_PATH_ACTIVE) && \
27 time_after(jiffies, mpath->exp_time) && \
28 !(mpath->flags & MESH_PATH_FIXED))
29
30struct mpath_node {
31 struct hlist_node list;
32 struct rcu_head rcu;
33 /* This indirection allows two different tables to point to the same
34 * mesh_path structure, useful when resizing
35 */
36 struct mesh_path *mpath;
37};
38
39static struct mesh_table *mesh_paths;
YanBo79617de2008-09-22 13:30:32 +080040static struct mesh_table *mpp_paths; /* Store paths for MPP&MAP */
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +010041
Johannes Bergf5ea9122009-08-07 16:17:38 +020042int mesh_paths_generation;
Javier Cardona18889232009-08-10 12:15:52 -070043static void __mesh_table_free(struct mesh_table *tbl)
44{
45 kfree(tbl->hash_buckets);
46 kfree(tbl->hashwlock);
47 kfree(tbl);
48}
49
50void mesh_table_free(struct mesh_table *tbl, bool free_leafs)
51{
52 struct hlist_head *mesh_hash;
53 struct hlist_node *p, *q;
54 int i;
55
56 mesh_hash = tbl->hash_buckets;
57 for (i = 0; i <= tbl->hash_mask; i++) {
58 spin_lock(&tbl->hashwlock[i]);
59 hlist_for_each_safe(p, q, &mesh_hash[i]) {
60 tbl->free_node(p, free_leafs);
61 atomic_dec(&tbl->entries);
62 }
63 spin_unlock(&tbl->hashwlock[i]);
64 }
65 __mesh_table_free(tbl);
66}
67
68static struct mesh_table *mesh_table_grow(struct mesh_table *tbl)
69{
70 struct mesh_table *newtbl;
71 struct hlist_head *oldhash;
72 struct hlist_node *p, *q;
73 int i;
74
75 if (atomic_read(&tbl->entries)
76 < tbl->mean_chain_len * (tbl->hash_mask + 1))
77 goto endgrow;
78
79 newtbl = mesh_table_alloc(tbl->size_order + 1);
80 if (!newtbl)
81 goto endgrow;
82
83 newtbl->free_node = tbl->free_node;
84 newtbl->mean_chain_len = tbl->mean_chain_len;
85 newtbl->copy_node = tbl->copy_node;
86 atomic_set(&newtbl->entries, atomic_read(&tbl->entries));
87
88 oldhash = tbl->hash_buckets;
89 for (i = 0; i <= tbl->hash_mask; i++)
90 hlist_for_each(p, &oldhash[i])
91 if (tbl->copy_node(p, newtbl) < 0)
92 goto errcopy;
93
94 return newtbl;
95
96errcopy:
97 for (i = 0; i <= newtbl->hash_mask; i++) {
98 hlist_for_each_safe(p, q, &newtbl->hash_buckets[i])
99 tbl->free_node(p, 0);
100 }
101 __mesh_table_free(newtbl);
102endgrow:
103 return NULL;
104}
105
Johannes Bergf5ea9122009-08-07 16:17:38 +0200106
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100107/* This lock will have the grow table function as writer and add / delete nodes
108 * as readers. When reading the table (i.e. doing lookups) we are well protected
109 * by RCU
110 */
111static DEFINE_RWLOCK(pathtbl_resize_lock);
112
113/**
114 *
115 * mesh_path_assign_nexthop - update mesh path next hop
116 *
117 * @mpath: mesh path to update
118 * @sta: next hop to assign
119 *
120 * Locking: mpath->state_lock must be held when calling this function
121 */
122void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta)
123{
Javier Cardona10c836d2009-07-09 14:42:16 -0700124 struct sk_buff *skb;
125 struct ieee80211_hdr *hdr;
126 struct sk_buff_head tmpq;
127 unsigned long flags;
128
Johannes Bergd0709a62008-02-25 16:27:46 +0100129 rcu_assign_pointer(mpath->next_hop, sta);
Javier Cardona10c836d2009-07-09 14:42:16 -0700130
131 __skb_queue_head_init(&tmpq);
132
133 spin_lock_irqsave(&mpath->frame_queue.lock, flags);
134
135 while ((skb = __skb_dequeue(&mpath->frame_queue)) != NULL) {
136 hdr = (struct ieee80211_hdr *) skb->data;
137 memcpy(hdr->addr1, sta->sta.addr, ETH_ALEN);
138 __skb_queue_tail(&tmpq, skb);
139 }
140
141 skb_queue_splice(&tmpq, &mpath->frame_queue);
142 spin_unlock_irqrestore(&mpath->frame_queue.lock, flags);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100143}
144
145
146/**
147 * mesh_path_lookup - look up a path in the mesh path table
148 * @dst: hardware address (ETH_ALEN length) of destination
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200149 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100150 *
151 * Returns: pointer to the mesh path structure, or NULL if not found
152 *
153 * Locking: must be called within a read rcu section.
154 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200155struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100156{
157 struct mesh_path *mpath;
158 struct hlist_node *n;
159 struct hlist_head *bucket;
160 struct mesh_table *tbl;
161 struct mpath_node *node;
162
163 tbl = rcu_dereference(mesh_paths);
164
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200165 bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100166 hlist_for_each_entry_rcu(node, n, bucket, list) {
167 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200168 if (mpath->sdata == sdata &&
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100169 memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
170 if (MPATH_EXPIRED(mpath)) {
171 spin_lock_bh(&mpath->state_lock);
172 if (MPATH_EXPIRED(mpath))
173 mpath->flags &= ~MESH_PATH_ACTIVE;
174 spin_unlock_bh(&mpath->state_lock);
175 }
176 return mpath;
177 }
178 }
179 return NULL;
180}
181
YanBo79617de2008-09-22 13:30:32 +0800182struct mesh_path *mpp_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
183{
184 struct mesh_path *mpath;
185 struct hlist_node *n;
186 struct hlist_head *bucket;
187 struct mesh_table *tbl;
188 struct mpath_node *node;
189
190 tbl = rcu_dereference(mpp_paths);
191
192 bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
193 hlist_for_each_entry_rcu(node, n, bucket, list) {
194 mpath = node->mpath;
195 if (mpath->sdata == sdata &&
196 memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
197 if (MPATH_EXPIRED(mpath)) {
198 spin_lock_bh(&mpath->state_lock);
199 if (MPATH_EXPIRED(mpath))
200 mpath->flags &= ~MESH_PATH_ACTIVE;
201 spin_unlock_bh(&mpath->state_lock);
202 }
203 return mpath;
204 }
205 }
206 return NULL;
207}
208
209
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100210/**
211 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
212 * @idx: index
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200213 * @sdata: local subif, or NULL for all entries
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100214 *
215 * Returns: pointer to the mesh path structure, or NULL if not found.
216 *
217 * Locking: must be called within a read rcu section.
218 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200219struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100220{
221 struct mpath_node *node;
222 struct hlist_node *p;
223 int i;
224 int j = 0;
225
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800226 for_each_mesh_entry(mesh_paths, p, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200227 if (sdata && node->mpath->sdata != sdata)
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800228 continue;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100229 if (j++ == idx) {
230 if (MPATH_EXPIRED(node->mpath)) {
231 spin_lock_bh(&node->mpath->state_lock);
232 if (MPATH_EXPIRED(node->mpath))
233 node->mpath->flags &= ~MESH_PATH_ACTIVE;
234 spin_unlock_bh(&node->mpath->state_lock);
235 }
236 return node->mpath;
237 }
Luis Carlos Cobo2a8ca292008-02-29 17:51:25 -0800238 }
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100239
240 return NULL;
241}
242
243/**
244 * mesh_path_add - allocate and add a new path to the mesh path table
245 * @addr: destination address of the path (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200246 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100247 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200248 * Returns: 0 on success
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100249 *
250 * State: the initial state of the new path is set to 0
251 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200252int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100253{
Javier Cardona18889232009-08-10 12:15:52 -0700254 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
255 struct ieee80211_local *local = sdata->local;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100256 struct mesh_path *mpath, *new_mpath;
257 struct mpath_node *node, *new_node;
258 struct hlist_head *bucket;
259 struct hlist_node *n;
260 int grow = 0;
261 int err = 0;
262 u32 hash_idx;
263
Johannes Berg47846c92009-11-25 17:46:19 +0100264 if (memcmp(dst, sdata->vif.addr, ETH_ALEN) == 0)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100265 /* never add ourselves as neighbours */
266 return -ENOTSUPP;
267
268 if (is_multicast_ether_addr(dst))
269 return -ENOTSUPP;
270
Johannes Berg472dbc42008-09-11 00:01:49 +0200271 if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100272 return -ENOSPC;
273
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400274 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700275 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400276 if (!new_mpath)
277 goto err_path_alloc;
278
Javier Cardona18889232009-08-10 12:15:52 -0700279 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400280 if (!new_node)
281 goto err_node_alloc;
Pavel Emelyanovf84e71a2008-05-06 18:46:36 +0400282
283 read_lock(&pathtbl_resize_lock);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100284 memcpy(new_mpath->dst, dst, ETH_ALEN);
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200285 new_mpath->sdata = sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100286 new_mpath->flags = 0;
287 skb_queue_head_init(&new_mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100288 new_node->mpath = new_mpath;
289 new_mpath->timer.data = (unsigned long) new_mpath;
290 new_mpath->timer.function = mesh_path_timer;
291 new_mpath->exp_time = jiffies;
292 spin_lock_init(&new_mpath->state_lock);
293 init_timer(&new_mpath->timer);
294
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200295 hash_idx = mesh_table_hash(dst, sdata, mesh_paths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100296 bucket = &mesh_paths->hash_buckets[hash_idx];
297
298 spin_lock(&mesh_paths->hashwlock[hash_idx]);
299
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400300 err = -EEXIST;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100301 hlist_for_each_entry(node, n, bucket, list) {
302 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200303 if (mpath->sdata == sdata && memcmp(dst, mpath->dst, ETH_ALEN) == 0)
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400304 goto err_exists;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100305 }
306
307 hlist_add_head_rcu(&new_node->list, bucket);
308 if (atomic_inc_return(&mesh_paths->entries) >=
309 mesh_paths->mean_chain_len * (mesh_paths->hash_mask + 1))
310 grow = 1;
311
Johannes Bergf5ea9122009-08-07 16:17:38 +0200312 mesh_paths_generation++;
313
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100314 spin_unlock(&mesh_paths->hashwlock[hash_idx]);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100315 read_unlock(&pathtbl_resize_lock);
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400316 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700317 set_bit(MESH_WORK_GROW_MPATH_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200318 ieee80211_queue_work(&local->hw, &sdata->work);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100319 }
Pavel Emelyanov402d7752008-05-06 18:53:43 +0400320 return 0;
321
322err_exists:
323 spin_unlock(&mesh_paths->hashwlock[hash_idx]);
324 read_unlock(&pathtbl_resize_lock);
325 kfree(new_node);
326err_node_alloc:
327 kfree(new_mpath);
328err_path_alloc:
Johannes Berg472dbc42008-09-11 00:01:49 +0200329 atomic_dec(&sdata->u.mesh.mpaths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100330 return err;
331}
332
Javier Cardona18889232009-08-10 12:15:52 -0700333void mesh_mpath_table_grow(void)
334{
335 struct mesh_table *oldtbl, *newtbl;
336
337 write_lock(&pathtbl_resize_lock);
338 oldtbl = mesh_paths;
339 newtbl = mesh_table_grow(mesh_paths);
340 if (!newtbl) {
341 write_unlock(&pathtbl_resize_lock);
342 return;
343 }
344 rcu_assign_pointer(mesh_paths, newtbl);
345 write_unlock(&pathtbl_resize_lock);
346
347 synchronize_rcu();
348 mesh_table_free(oldtbl, false);
349}
350
351void mesh_mpp_table_grow(void)
352{
353 struct mesh_table *oldtbl, *newtbl;
354
355 write_lock(&pathtbl_resize_lock);
356 oldtbl = mpp_paths;
357 newtbl = mesh_table_grow(mpp_paths);
358 if (!newtbl) {
359 write_unlock(&pathtbl_resize_lock);
360 return;
361 }
362 rcu_assign_pointer(mpp_paths, newtbl);
363 write_unlock(&pathtbl_resize_lock);
364
365 synchronize_rcu();
366 mesh_table_free(oldtbl, false);
367}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100368
YanBo79617de2008-09-22 13:30:32 +0800369int mpp_path_add(u8 *dst, u8 *mpp, struct ieee80211_sub_if_data *sdata)
370{
Javier Cardona18889232009-08-10 12:15:52 -0700371 struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
372 struct ieee80211_local *local = sdata->local;
YanBo79617de2008-09-22 13:30:32 +0800373 struct mesh_path *mpath, *new_mpath;
374 struct mpath_node *node, *new_node;
375 struct hlist_head *bucket;
376 struct hlist_node *n;
377 int grow = 0;
378 int err = 0;
379 u32 hash_idx;
380
Johannes Berg47846c92009-11-25 17:46:19 +0100381 if (memcmp(dst, sdata->vif.addr, ETH_ALEN) == 0)
YanBo79617de2008-09-22 13:30:32 +0800382 /* never add ourselves as neighbours */
383 return -ENOTSUPP;
384
385 if (is_multicast_ether_addr(dst))
386 return -ENOTSUPP;
387
388 err = -ENOMEM;
Javier Cardona18889232009-08-10 12:15:52 -0700389 new_mpath = kzalloc(sizeof(struct mesh_path), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800390 if (!new_mpath)
391 goto err_path_alloc;
392
Javier Cardona18889232009-08-10 12:15:52 -0700393 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
YanBo79617de2008-09-22 13:30:32 +0800394 if (!new_node)
395 goto err_node_alloc;
396
397 read_lock(&pathtbl_resize_lock);
398 memcpy(new_mpath->dst, dst, ETH_ALEN);
399 memcpy(new_mpath->mpp, mpp, ETH_ALEN);
400 new_mpath->sdata = sdata;
401 new_mpath->flags = 0;
402 skb_queue_head_init(&new_mpath->frame_queue);
403 new_node->mpath = new_mpath;
404 new_mpath->exp_time = jiffies;
405 spin_lock_init(&new_mpath->state_lock);
406
407 hash_idx = mesh_table_hash(dst, sdata, mpp_paths);
408 bucket = &mpp_paths->hash_buckets[hash_idx];
409
410 spin_lock(&mpp_paths->hashwlock[hash_idx]);
411
412 err = -EEXIST;
413 hlist_for_each_entry(node, n, bucket, list) {
414 mpath = node->mpath;
415 if (mpath->sdata == sdata && memcmp(dst, mpath->dst, ETH_ALEN) == 0)
416 goto err_exists;
417 }
418
419 hlist_add_head_rcu(&new_node->list, bucket);
420 if (atomic_inc_return(&mpp_paths->entries) >=
421 mpp_paths->mean_chain_len * (mpp_paths->hash_mask + 1))
422 grow = 1;
423
424 spin_unlock(&mpp_paths->hashwlock[hash_idx]);
425 read_unlock(&pathtbl_resize_lock);
426 if (grow) {
Javier Cardona18889232009-08-10 12:15:52 -0700427 set_bit(MESH_WORK_GROW_MPP_TABLE, &ifmsh->wrkq_flags);
Johannes Berg64592c82010-06-10 10:21:31 +0200428 ieee80211_queue_work(&local->hw, &sdata->work);
YanBo79617de2008-09-22 13:30:32 +0800429 }
430 return 0;
431
432err_exists:
433 spin_unlock(&mpp_paths->hashwlock[hash_idx]);
434 read_unlock(&pathtbl_resize_lock);
435 kfree(new_node);
436err_node_alloc:
437 kfree(new_mpath);
438err_path_alloc:
439 return err;
440}
441
442
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100443/**
444 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
445 *
446 * @sta: broken peer link
447 *
448 * This function must be called from the rate control algorithm if enough
449 * delivery errors suggest that a peer link is no longer usable.
450 */
451void mesh_plink_broken(struct sta_info *sta)
452{
Johannes Berg15ff6362009-11-17 13:34:04 +0100453 static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100454 struct mesh_path *mpath;
455 struct mpath_node *node;
456 struct hlist_node *p;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200457 struct ieee80211_sub_if_data *sdata = sta->sdata;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100458 int i;
459
460 rcu_read_lock();
461 for_each_mesh_entry(mesh_paths, p, node, i) {
462 mpath = node->mpath;
463 spin_lock_bh(&mpath->state_lock);
464 if (mpath->next_hop == sta &&
465 mpath->flags & MESH_PATH_ACTIVE &&
466 !(mpath->flags & MESH_PATH_FIXED)) {
467 mpath->flags &= ~MESH_PATH_ACTIVE;
Rui Paulod19b3bf2009-11-09 23:46:55 +0000468 ++mpath->sn;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100469 spin_unlock_bh(&mpath->state_lock);
Rui Paulod611f062009-11-09 23:46:50 +0000470 mesh_path_error_tx(MESH_TTL, mpath->dst,
Rui Paulod19b3bf2009-11-09 23:46:55 +0000471 cpu_to_le32(mpath->sn),
Rui Paulo9f130842009-11-19 15:49:10 +0000472 cpu_to_le16(PERR_RCODE_DEST_UNREACH),
Johannes Berg15ff6362009-11-17 13:34:04 +0100473 bcast, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100474 } else
475 spin_unlock_bh(&mpath->state_lock);
476 }
477 rcu_read_unlock();
478}
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100479
480/**
481 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
482 *
483 * @sta - mesh peer to match
484 *
Luis Carlos Cobob4e08ea2008-02-29 15:46:08 -0800485 * RCU notes: this function is called when a mesh plink transitions from
486 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
487 * allows path creation. This will happen before the sta can be freed (because
Johannes Bergd0709a62008-02-25 16:27:46 +0100488 * sta_info_destroy() calls this) so any reader in a rcu read block will be
489 * protected against the plink disappearing.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100490 */
491void mesh_path_flush_by_nexthop(struct sta_info *sta)
492{
493 struct mesh_path *mpath;
494 struct mpath_node *node;
495 struct hlist_node *p;
496 int i;
497
498 for_each_mesh_entry(mesh_paths, p, node, i) {
499 mpath = node->mpath;
500 if (mpath->next_hop == sta)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200501 mesh_path_del(mpath->dst, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100502 }
503}
504
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200505void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100506{
507 struct mesh_path *mpath;
508 struct mpath_node *node;
509 struct hlist_node *p;
510 int i;
511
512 for_each_mesh_entry(mesh_paths, p, node, i) {
513 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200514 if (mpath->sdata == sdata)
515 mesh_path_del(mpath->dst, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100516 }
517}
518
519static void mesh_path_node_reclaim(struct rcu_head *rp)
520{
521 struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200522 struct ieee80211_sub_if_data *sdata = node->mpath->sdata;
Johannes Bergd0709a62008-02-25 16:27:46 +0100523
Luis Carlos Cobo89a1ad62008-02-29 14:49:37 -0800524 del_timer_sync(&node->mpath->timer);
Johannes Berg472dbc42008-09-11 00:01:49 +0200525 atomic_dec(&sdata->u.mesh.mpaths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100526 kfree(node->mpath);
527 kfree(node);
528}
529
530/**
531 * mesh_path_del - delete a mesh path from the table
532 *
533 * @addr: dst address (ETH_ALEN length)
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200534 * @sdata: local subif
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100535 *
André Goddard Rosaaf901ca2009-11-14 13:09:05 -0200536 * Returns: 0 if successful
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100537 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200538int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100539{
540 struct mesh_path *mpath;
541 struct mpath_node *node;
542 struct hlist_head *bucket;
543 struct hlist_node *n;
544 int hash_idx;
545 int err = 0;
546
547 read_lock(&pathtbl_resize_lock);
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200548 hash_idx = mesh_table_hash(addr, sdata, mesh_paths);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100549 bucket = &mesh_paths->hash_buckets[hash_idx];
550
551 spin_lock(&mesh_paths->hashwlock[hash_idx]);
552 hlist_for_each_entry(node, n, bucket, list) {
553 mpath = node->mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200554 if (mpath->sdata == sdata &&
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100555 memcmp(addr, mpath->dst, ETH_ALEN) == 0) {
556 spin_lock_bh(&mpath->state_lock);
Luis Carlos Cobocfa22c72008-02-29 15:04:13 -0800557 mpath->flags |= MESH_PATH_RESOLVING;
558 hlist_del_rcu(&node->list);
559 call_rcu(&node->rcu, mesh_path_node_reclaim);
560 atomic_dec(&mesh_paths->entries);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100561 spin_unlock_bh(&mpath->state_lock);
562 goto enddel;
563 }
564 }
565
566 err = -ENXIO;
567enddel:
Johannes Bergf5ea9122009-08-07 16:17:38 +0200568 mesh_paths_generation++;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100569 spin_unlock(&mesh_paths->hashwlock[hash_idx]);
570 read_unlock(&pathtbl_resize_lock);
571 return err;
572}
573
574/**
575 * mesh_path_tx_pending - sends pending frames in a mesh path queue
576 *
577 * @mpath: mesh path to activate
578 *
579 * Locking: the state_lock of the mpath structure must NOT be held when calling
580 * this function.
581 */
582void mesh_path_tx_pending(struct mesh_path *mpath)
583{
Javier Cardona249b4052009-07-07 10:55:03 -0700584 if (mpath->flags & MESH_PATH_ACTIVE)
585 ieee80211_add_pending_skbs(mpath->sdata->local,
586 &mpath->frame_queue);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100587}
588
589/**
590 * mesh_path_discard_frame - discard a frame whose path could not be resolved
591 *
592 * @skb: frame to discard
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200593 * @sdata: network subif the frame was to be sent through
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100594 *
Javier Cardona35946a52009-07-13 17:00:10 -0700595 * If the frame was being forwarded from another MP, a PERR frame will be sent
596 * to the precursor. The precursor's address (i.e. the previous hop) was saved
597 * in addr1 of the frame-to-be-forwarded, and would only be overwritten once
598 * the destination is successfully resolved.
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100599 *
600 * Locking: the function must me called within a rcu_read_lock region
601 */
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200602void mesh_path_discard_frame(struct sk_buff *skb,
603 struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100604{
Luis Carlos Coboe32f85f2008-08-05 19:34:52 +0200605 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100606 struct mesh_path *mpath;
Rui Paulod19b3bf2009-11-09 23:46:55 +0000607 u32 sn = 0;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100608
Johannes Berg47846c92009-11-25 17:46:19 +0100609 if (memcmp(hdr->addr4, sdata->vif.addr, ETH_ALEN) != 0) {
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100610 u8 *ra, *da;
611
Luis Carlos Coboe32f85f2008-08-05 19:34:52 +0200612 da = hdr->addr3;
Javier Cardona35946a52009-07-13 17:00:10 -0700613 ra = hdr->addr1;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200614 mpath = mesh_path_lookup(da, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100615 if (mpath)
Rui Paulod19b3bf2009-11-09 23:46:55 +0000616 sn = ++mpath->sn;
617 mesh_path_error_tx(MESH_TTL, skb->data, cpu_to_le32(sn),
Rui Paulo9f130842009-11-19 15:49:10 +0000618 cpu_to_le16(PERR_RCODE_NO_ROUTE), ra, sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100619 }
620
621 kfree_skb(skb);
Johannes Berg472dbc42008-09-11 00:01:49 +0200622 sdata->u.mesh.mshstats.dropped_frames_no_route++;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100623}
624
625/**
626 * mesh_path_flush_pending - free the pending queue of a mesh path
627 *
628 * @mpath: mesh path whose queue has to be freed
629 *
630 * Locking: the function must me called withing a rcu_read_lock region
631 */
632void mesh_path_flush_pending(struct mesh_path *mpath)
633{
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100634 struct sk_buff *skb;
635
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100636 while ((skb = skb_dequeue(&mpath->frame_queue)) &&
637 (mpath->flags & MESH_PATH_ACTIVE))
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200638 mesh_path_discard_frame(skb, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100639}
640
641/**
642 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
643 *
644 * @mpath: the mesh path to modify
645 * @next_hop: the next hop to force
646 *
647 * Locking: this function must be called holding mpath->state_lock
648 */
649void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop)
650{
651 spin_lock_bh(&mpath->state_lock);
652 mesh_path_assign_nexthop(mpath, next_hop);
Rui Paulod19b3bf2009-11-09 23:46:55 +0000653 mpath->sn = 0xffff;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100654 mpath->metric = 0;
655 mpath->hop_count = 0;
656 mpath->exp_time = 0;
657 mpath->flags |= MESH_PATH_FIXED;
658 mesh_path_activate(mpath);
659 spin_unlock_bh(&mpath->state_lock);
660 mesh_path_tx_pending(mpath);
661}
662
663static void mesh_path_node_free(struct hlist_node *p, bool free_leafs)
664{
665 struct mesh_path *mpath;
666 struct mpath_node *node = hlist_entry(p, struct mpath_node, list);
667 mpath = node->mpath;
668 hlist_del_rcu(p);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100669 if (free_leafs)
670 kfree(mpath);
671 kfree(node);
672}
673
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +0400674static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100675{
676 struct mesh_path *mpath;
677 struct mpath_node *node, *new_node;
678 u32 hash_idx;
679
Pavel Emelyanov8566dc32008-05-07 19:51:51 +0400680 new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
Pavel Emelyanov00242c42008-05-07 19:48:14 +0400681 if (new_node == NULL)
682 return -ENOMEM;
683
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100684 node = hlist_entry(p, struct mpath_node, list);
685 mpath = node->mpath;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100686 new_node->mpath = mpath;
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200687 hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100688 hlist_add_head(&new_node->list,
689 &newtbl->hash_buckets[hash_idx]);
Pavel Emelyanov4caf86c2008-05-07 19:47:01 +0400690 return 0;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100691}
692
693int mesh_pathtbl_init(void)
694{
695 mesh_paths = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
YanBo79617de2008-09-22 13:30:32 +0800696 if (!mesh_paths)
697 return -ENOMEM;
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100698 mesh_paths->free_node = &mesh_path_node_free;
699 mesh_paths->copy_node = &mesh_path_node_copy;
700 mesh_paths->mean_chain_len = MEAN_CHAIN_LEN;
YanBo79617de2008-09-22 13:30:32 +0800701
702 mpp_paths = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
703 if (!mpp_paths) {
704 mesh_table_free(mesh_paths, true);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100705 return -ENOMEM;
YanBo79617de2008-09-22 13:30:32 +0800706 }
707 mpp_paths->free_node = &mesh_path_node_free;
708 mpp_paths->copy_node = &mesh_path_node_copy;
709 mpp_paths->mean_chain_len = MEAN_CHAIN_LEN;
710
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100711 return 0;
712}
713
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200714void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100715{
716 struct mesh_path *mpath;
717 struct mpath_node *node;
718 struct hlist_node *p;
719 int i;
720
721 read_lock(&pathtbl_resize_lock);
722 for_each_mesh_entry(mesh_paths, p, node, i) {
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200723 if (node->mpath->sdata != sdata)
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100724 continue;
725 mpath = node->mpath;
726 spin_lock_bh(&mpath->state_lock);
727 if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
728 (!(mpath->flags & MESH_PATH_FIXED)) &&
729 time_after(jiffies,
730 mpath->exp_time + MESH_PATH_EXPIRE)) {
731 spin_unlock_bh(&mpath->state_lock);
Jasper Bryant-Greenef698d852008-08-03 12:04:37 +1200732 mesh_path_del(mpath->dst, mpath->sdata);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100733 } else
734 spin_unlock_bh(&mpath->state_lock);
735 }
736 read_unlock(&pathtbl_resize_lock);
737}
738
739void mesh_pathtbl_unregister(void)
740{
741 mesh_table_free(mesh_paths, true);
YanBo79617de2008-09-22 13:30:32 +0800742 mesh_table_free(mpp_paths, true);
Luis Carlos Coboeb2b9312008-02-23 15:17:14 +0100743}