aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLuis Carlos Cobo <luisca@cozybit.com>2008-02-23 09:17:15 -0500
committerJohn W. Linville <linville@tuxdriver.com>2008-03-06 15:30:42 -0500
commit050ac52cbe1f3de2fb0d06f02c7919ae1f691c9e (patch)
tree5fd902c087415eb1145b513b16c0f3ff0d0d8d8d
parenteb2b9311fd00a868e9bf85ab66e86b7dee1643e1 (diff)
mac80211: code for on-demand Hybrid Wireless Mesh Protocol
This file implements the on-demand Hybrid Wireless Mesh Protocol, at this moment using hop-count as the metric. When no mesh path exists for a given destination or the mesh path is not active, frames addressed to that destination will be queued and a Path Request frame will be sent. Queued frames will be sent when the path is resolved (usually after reception of a Path Response) or discarded if discovery times out. Path Requests will also be sent to refresh paths that are being used and are close to expiring. Path Errors are sent when a path discovery process triggered by the attempt to forward a frame originated in a different mesh point times out. Path Errors are also sent when a peer link is determined to be unreachable because of high error rates. Multiple destination support in Path Requests and Path Errors and precursors have not been implemented yet. Signed-off-by: Luis Carlos Cobo <luisca@cozybit.com> Signed-off-by: Johannes Berg <johannes@sipsolutions.net> Signed-off-by: John W. Linville <linville@tuxdriver.com>
Diffstat
-rw-r--r--net/mac80211/mesh_hwmp.c862
1 files changed, 862 insertions, 0 deletions
diff --git a/net/mac80211/mesh_hwmp.c b/net/mac80211/mesh_hwmp.c
new file mode 100644
index 000000000000..9a501aae48eb
--- /dev/null
+++ b/net/mac80211/mesh_hwmp.c
@@ -0,0 +1,862 @@
1/*
2 * Copyright (c) 2008 open80211s Ltd.
3 * 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 "mesh.h"
11
12#define IEEE80211_FC(type, stype) cpu_to_le16(type | stype)
13
14#define TEST_FRAME_LEN 8192
15#define MAX_METRIC 0xffffffff
16#define ARITH_SHIFT 8
17
18/* Number of frames buffered per destination for unresolved destinations */
19#define MESH_FRAME_QUEUE_LEN 10
20#define MAX_PREQ_QUEUE_LEN 64
21
22/* Destination only */
23#define MP_F_DO 0x1
24/* Reply and forward */
25#define MP_F_RF 0x2
26
27/* HWMP IE processing macros */
28#define AE_F (1<<6)
29#define AE_F_SET(x) (*x & AE_F)
30#define PREQ_IE_FLAGS(x) (*(x))
31#define PREQ_IE_HOPCOUNT(x) (*(x + 1))
32#define PREQ_IE_TTL(x) (*(x + 2))
33#define PREQ_IE_PREQ_ID(x) le32_to_cpu(*((u32 *) (x + 3)))
34#define PREQ_IE_ORIG_ADDR(x) (x + 7)
35#define PREQ_IE_ORIG_DSN(x) le32_to_cpu(*((u32 *) (x + 13)))
36#define PREQ_IE_LIFETIME(x) le32_to_cpu(*((u32 *) \
37 (AE_F_SET(x) ? x + 23 : x + 17)))
38#define PREQ_IE_METRIC(x) le32_to_cpu(*((u32 *) \
39 (AE_F_SET(x) ? x + 27 : x + 21)))
40#define PREQ_IE_DST_F(x) (*(AE_F_SET(x) ? x + 32 : x + 26))
41#define PREQ_IE_DST_ADDR(x) (AE_F_SET(x) ? x + 33 : x + 27)
42#define PREQ_IE_DST_DSN(x) le32_to_cpu(*((u32 *) \
43 (AE_F_SET(x) ? x + 39 : x + 33)))
44
45
46#define PREP_IE_FLAGS(x) PREQ_IE_FLAGS(x)
47#define PREP_IE_HOPCOUNT(x) PREQ_IE_HOPCOUNT(x)
48#define PREP_IE_TTL(x) PREQ_IE_TTL(x)
49#define PREP_IE_ORIG_ADDR(x) (x + 3)
50#define PREP_IE_ORIG_DSN(x) le32_to_cpu(*((u32 *) (x + 9)))
51#define PREP_IE_LIFETIME(x) le32_to_cpu(*((u32 *) \
52 (AE_F_SET(x) ? x + 19 : x + 13)))
53#define PREP_IE_METRIC(x) le32_to_cpu(*((u32 *) \
54 (AE_F_SET(x) ? x + 23 : x + 17)))
55#define PREP_IE_DST_ADDR(x) (AE_F_SET(x) ? x + 27 : x + 21)
56#define PREP_IE_DST_DSN(x) le32_to_cpu(*((u32 *) \
57 (AE_F_SET(x) ? x + 33 : x + 27)))
58
59#define PERR_IE_DST_ADDR(x) (x + 2)
60#define PERR_IE_DST_DSN(x) le32_to_cpu(*((u32 *) (x + 8)))
61
62#define TU_TO_EXP_TIME(x) (jiffies + msecs_to_jiffies(x * 1024 / 1000))
63#define MSEC_TO_TU(x) (x*1000/1024)
64#define DSN_GT(x, y) ((long) (y) - (long) (x) < 0)
65#define DSN_LT(x, y) ((long) (x) - (long) (y) < 0)
66
67#define net_traversal_jiffies(s) \
68 msecs_to_jiffies(s->u.sta.mshcfg.dot11MeshHWMPnetDiameterTraversalTime)
69#define default_lifetime(s) \
70 MSEC_TO_TU(s->u.sta.mshcfg.dot11MeshHWMPactivePathTimeout)
71#define min_preq_int_jiff(s) \
72 (msecs_to_jiffies(s->u.sta.mshcfg.dot11MeshHWMPpreqMinInterval))
73#define max_preq_retries(s) (s->u.sta.mshcfg.dot11MeshHWMPmaxPREQretries)
74#define disc_timeout_jiff(s) \
75 msecs_to_jiffies(sdata->u.sta.mshcfg.min_discovery_timeout)
76
77enum mpath_frame_type {
78 MPATH_PREQ = 0,
79 MPATH_PREP,
80 MPATH_PERR
81};
82
83static int mesh_path_sel_frame_tx(enum mpath_frame_type action, u8 flags,
84 u8 *orig_addr, __le32 orig_dsn, u8 dst_flags, u8 *dst,
85 __le32 dst_dsn, u8 *da, u8 hop_count, u8 ttl, __le32 lifetime,
86 __le32 metric, __le32 preq_id, struct net_device *dev)
87{
88 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
89 struct sk_buff *skb = dev_alloc_skb(local->hw.extra_tx_headroom + 400);
90 struct ieee80211_mgmt *mgmt;
91 u8 *pos;
92 int ie_len;
93
94 if (!skb)
95 return -1;
96 skb_reserve(skb, local->hw.extra_tx_headroom);
97 /* 25 is the size of the common mgmt part (24) plus the size of the
98 * common action part (1)
99 */
100 mgmt = (struct ieee80211_mgmt *)
101 skb_put(skb, 25 + sizeof(mgmt->u.action.u.mesh_action));
102 memset(mgmt, 0, 25 + sizeof(mgmt->u.action.u.mesh_action));
103 mgmt->frame_control = IEEE80211_FC(IEEE80211_FTYPE_MGMT,
104 IEEE80211_STYPE_ACTION);
105
106 memcpy(mgmt->da, da, ETH_ALEN);
107 memcpy(mgmt->sa, dev->dev_addr, ETH_ALEN);
108 /* BSSID is left zeroed, wildcard value */
109 mgmt->u.action.category = MESH_PATH_SEL_CATEGORY;
110 mgmt->u.action.u.mesh_action.action_code = action;
111
112 switch (action) {
113 case MPATH_PREQ:
114 ie_len = 37;
115 pos = skb_put(skb, 2 + ie_len);
116 *pos++ = WLAN_EID_PREQ;
117 break;
118 case MPATH_PREP:
119 ie_len = 31;
120 pos = skb_put(skb, 2 + ie_len);
121 *pos++ = WLAN_EID_PREP;
122 break;
123 default:
124 kfree(skb);
125 return -ENOTSUPP;
126 break;
127 }
128 *pos++ = ie_len;
129 *pos++ = flags;
130 *pos++ = hop_count;
131 *pos++ = ttl;
132 if (action == MPATH_PREQ) {
133 memcpy(pos, &preq_id, 4);
134 pos += 4;
135 }
136 memcpy(pos, orig_addr, ETH_ALEN);
137 pos += ETH_ALEN;
138 memcpy(pos, &orig_dsn, 4);
139 pos += 4;
140 memcpy(pos, &lifetime, 4);
141 pos += 4;
142 memcpy(pos, &metric, 4);
143 pos += 4;
144 if (action == MPATH_PREQ) {
145 /* destination count */
146 *pos++ = 1;
147 *pos++ = dst_flags;
148 }
149 memcpy(pos, dst, ETH_ALEN);
150 pos += ETH_ALEN;
151 memcpy(pos, &dst_dsn, 4);
152
153 ieee80211_sta_tx(dev, skb, 0);
154 return 0;
155}
156
157/**
158 * mesh_send_path error - Sends a PERR mesh management frame
159 *
160 * @dst: broken destination
161 * @dst_dsn: dsn of the broken destination
162 * @ra: node this frame is addressed to
163 */
164int mesh_path_error_tx(u8 *dst, __le32 dst_dsn, u8 *ra,
165 struct net_device *dev)
166{
167 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
168 struct sk_buff *skb = dev_alloc_skb(local->hw.extra_tx_headroom + 400);
169 struct ieee80211_mgmt *mgmt;
170 u8 *pos;
171 int ie_len;
172
173 if (!skb)
174 return -1;
175 skb_reserve(skb, local->hw.extra_tx_headroom);
176 /* 25 is the size of the common mgmt part (24) plus the size of the
177 * common action part (1)
178 */
179 mgmt = (struct ieee80211_mgmt *)
180 skb_put(skb, 25 + sizeof(mgmt->u.action.u.mesh_action));
181 memset(mgmt, 0, 25 + sizeof(mgmt->u.action.u.mesh_action));
182 mgmt->frame_control = IEEE80211_FC(IEEE80211_FTYPE_MGMT,
183 IEEE80211_STYPE_ACTION);
184
185 memcpy(mgmt->da, ra, ETH_ALEN);
186 memcpy(mgmt->sa, dev->dev_addr, ETH_ALEN);
187 /* BSSID is left zeroed, wildcard value */
188 mgmt->u.action.category = MESH_PATH_SEL_CATEGORY;
189 mgmt->u.action.u.mesh_action.action_code = MPATH_PERR;
190 ie_len = 12;
191 pos = skb_put(skb, 2 + ie_len);
192 *pos++ = WLAN_EID_PERR;
193 *pos++ = ie_len;
194 /* mode flags, reserved */
195 *pos++ = 0;
196 /* number of destinations */
197 *pos++ = 1;
198 memcpy(pos, dst, ETH_ALEN);
199 pos += ETH_ALEN;
200 memcpy(pos, &dst_dsn, 4);
201
202 ieee80211_sta_tx(dev, skb, 0);
203 return 0;
204}
205
206static u32 airtime_link_metric_get(struct ieee80211_local *local,
207 struct sta_info *sta)
208{
209 struct ieee80211_supported_band *sband;
210 /* This should be adjusted for each device */
211 int device_constant = 1 << ARITH_SHIFT;
212 int test_frame_len = TEST_FRAME_LEN << ARITH_SHIFT;
213 int s_unit = 1 << ARITH_SHIFT;
214 int rate, err;
215 u32 tx_time, estimated_retx;
216 u64 result;
217
218 sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
219
220 if (sta->fail_avg >= 100)
221 return MAX_METRIC;
222 err = (sta->fail_avg << ARITH_SHIFT) / 100;
223
224 /* bitrate is in units of 100 Kbps, while we need rate in units of
225 * 1Mbps. This will be corrected on tx_time computation.
226 */
227 rate = sband->bitrates[sta->txrate_idx].bitrate;
228 tx_time = (device_constant + 10 * test_frame_len / rate);
229 estimated_retx = ((1 << (2 * ARITH_SHIFT)) / (s_unit - err));
230 result = (tx_time * estimated_retx) >> (2 * ARITH_SHIFT) ;
231 return (u32)result;
232}
233
234/**
235 * hwmp_route_info_get - Update routing info to originator and transmitter
236 *
237 * @dev: local mesh interface
238 * @mgmt: mesh management frame
239 * @hwmp_ie: hwmp information element (PREP or PREQ)
240 *
241 * This function updates the path routing information to the originator and the
242 * transmitter of a HWMP PREQ or PREP fram.
243 *
244 * Returns: metric to frame originator or 0 if the frame should not be further
245 * processed
246 *
247 * Notes: this function is the only place (besides user-provided info) where
248 * path routing information is updated.
249 */
250static u32 hwmp_route_info_get(struct net_device *dev,
251 struct ieee80211_mgmt *mgmt,
252 u8 *hwmp_ie)
253{
254 struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
255 struct mesh_path *mpath;
256 struct sta_info *sta;
257 bool fresh_info;
258 u8 *orig_addr, *ta;
259 u32 orig_dsn, orig_metric;
260 unsigned long orig_lifetime, exp_time;
261 u32 last_hop_metric, new_metric;
262 bool process = true;
263 u8 action = mgmt->u.action.u.mesh_action.action_code;
264
265 rcu_read_lock();
266 sta = sta_info_get(local, mgmt->sa);
267 if (!sta)
268 return 0;
269
270 last_hop_metric = airtime_link_metric_get(local, sta);
271 /* Update and check originator routing info */
272 fresh_info = true;
273
274 switch (action) {
275 case MPATH_PREQ:
276 orig_addr = PREQ_IE_ORIG_ADDR(hwmp_ie);
277 orig_dsn = PREQ_IE_ORIG_DSN(hwmp_ie);
278 orig_lifetime = PREQ_IE_LIFETIME(hwmp_ie);
279 orig_metric = PREQ_IE_METRIC(hwmp_ie);
280 break;
281 case MPATH_PREP:
282 /* Originator here refers to the MP that was the destination in
283 * the Path Request. The draft refers to that MP as the
284 * destination address, even though usually it is the origin of
285 * the PREP frame. We divert from the nomenclature in the draft
286 * so that we can easily use a single function to gather path
287 * information from both PREQ and PREP frames.
288 */
289 orig_addr = PREP_IE_ORIG_ADDR(hwmp_ie);
290 orig_dsn = PREP_IE_ORIG_DSN(hwmp_ie);
291 orig_lifetime = PREP_IE_LIFETIME(hwmp_ie);
292 orig_metric = PREP_IE_METRIC(hwmp_ie);
293 break;
294 default:
295 sta_info_put(sta);
296 return 0;
297 }
298 new_metric = orig_metric + last_hop_metric;
299 if (new_metric < orig_metric)
300 new_metric = MAX_METRIC;
301 exp_time = TU_TO_EXP_TIME(orig_lifetime);
302
303 if (memcmp(orig_addr, dev->dev_addr, ETH_ALEN) == 0) {
304 /* This MP is the originator, we are not interested in this
305 * frame, except for updating transmitter's path info.
306 */
307 process = false;
308 fresh_info = false;
309 } else {
310 mpath = mesh_path_lookup(orig_addr, dev);
311 if (mpath) {
312 spin_lock_bh(&mpath->state_lock);
313 if (mpath->flags & MESH_PATH_FIXED)
314 fresh_info = false;
315 else if ((mpath->flags & MESH_PATH_ACTIVE) &&
316 (mpath->flags & MESH_PATH_DSN_VALID)) {
317 if (DSN_GT(mpath->dsn, orig_dsn) ||
318 (mpath->dsn == orig_dsn &&
319 action == MPATH_PREQ &&
320 new_metric > mpath->metric)) {
321 process = false;
322 fresh_info = false;
323 }
324 }
325 } else {
326 mesh_path_add(orig_addr, dev);
327 mpath = mesh_path_lookup(orig_addr, dev);
328 if (!mpath) {
329 rcu_read_unlock();
330 sta_info_put(sta);
331 return 0;
332 }
333 spin_lock_bh(&mpath->state_lock);
334 }
335
336 if (fresh_info) {
337 mesh_path_assign_nexthop(mpath, sta);
338 mpath->flags |= MESH_PATH_DSN_VALID;
339 mpath->metric = new_metric;
340 mpath->dsn = orig_dsn;
341 mpath->exp_time = time_after(mpath->exp_time, exp_time)
342 ? mpath->exp_time : exp_time;
343 mesh_path_activate(mpath);
344 spin_unlock_bh(&mpath->state_lock);
345 mesh_path_tx_pending(mpath);
346 /* draft says preq_id should be saved to, but there does
347 * not seem to be any use for it, skipping by now
348 */
349 } else
350 spin_unlock_bh(&mpath->state_lock);
351 }
352
353 /* Update and check transmitter routing info */
354 ta = mgmt->sa;
355 if (memcmp(orig_addr, ta, ETH_ALEN) == 0)
356 fresh_info = false;
357 else {
358 fresh_info = true;
359
360 mpath = mesh_path_lookup(ta, dev);
361 if (mpath) {
362 spin_lock_bh(&mpath->state_lock);
363 if ((mpath->flags & MESH_PATH_FIXED) ||
364 ((mpath->flags & MESH_PATH_ACTIVE) &&
365 (last_hop_metric > mpath->metric)))
366 fresh_info = false;
367 } else {
368 mesh_path_add(ta, dev);
369 mpath = mesh_path_lookup(ta, dev);
370 if (!mpath) {
371 rcu_read_unlock();
372 sta_info_put(sta);
373 return 0;
374 }
375 spin_lock_bh(&mpath->state_lock);
376 }
377
378 if (fresh_info) {
379 mesh_path_assign_nexthop(mpath, sta);
380 mpath->flags &= ~MESH_PATH_DSN_VALID;
381 mpath->metric = last_hop_metric;
382 mpath->exp_time = time_after(mpath->exp_time, exp_time)
383 ? mpath->exp_time : exp_time;
384 mesh_path_activate(mpath);
385 spin_unlock_bh(&mpath->state_lock);
386 mesh_path_tx_pending(mpath);
387 } else
388 spin_unlock_bh(&mpath->state_lock);
389 }
390
391 sta_info_put(sta);
392 rcu_read_unlock();
393
394 return process ? new_metric : 0;
395}
396
397static void hwmp_preq_frame_process(struct net_device *dev,
398 struct ieee80211_mgmt *mgmt,
399 u8 *preq_elem, u32 metric) {
400 struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
401 struct ieee80211_if_sta *ifsta = &sdata->u.sta;
402 struct mesh_path *mpath;
403 u8 *dst_addr, *orig_addr;
404 u8 dst_flags, ttl;
405 u32 orig_dsn, dst_dsn, lifetime;
406 bool reply = false;
407 bool forward = true;
408
409 /* Update destination DSN, if present */
410 dst_addr = PREQ_IE_DST_ADDR(preq_elem);
411 orig_addr = PREQ_IE_ORIG_ADDR(preq_elem);
412 dst_dsn = PREQ_IE_DST_DSN(preq_elem);
413 orig_dsn = PREQ_IE_ORIG_DSN(preq_elem);
414 dst_flags = PREQ_IE_DST_F(preq_elem);
415
416 if (memcmp(dst_addr, dev->dev_addr, ETH_ALEN) == 0) {
417 forward = false;
418 reply = true;
419 metric = 0;
420 if (time_after(jiffies, ifsta->last_dsn_update +
421 net_traversal_jiffies(sdata)) ||
422 time_before(jiffies, ifsta->last_dsn_update)) {
423 dst_dsn = ++ifsta->dsn;
424 ifsta->last_dsn_update = jiffies;
425 }
426 } else {
427 rcu_read_lock();
428 mpath = mesh_path_lookup(dst_addr, dev);
429 if (mpath) {
430 if ((!(mpath->flags & MESH_PATH_DSN_VALID)) ||
431 DSN_LT(mpath->dsn, dst_dsn)) {
432 mpath->dsn = dst_dsn;
433 mpath->flags &= MESH_PATH_DSN_VALID;
434 } else if ((!(dst_flags & MP_F_DO)) &&
435 (mpath->flags & MESH_PATH_ACTIVE)) {
436 reply = true;
437 metric = mpath->metric;
438 dst_dsn = mpath->dsn;
439 if (dst_flags & MP_F_RF)
440 dst_flags |= MP_F_DO;
441 else
442 forward = false;
443 }
444 }
445 rcu_read_unlock();
446 }
447
448 if (reply) {
449 lifetime = PREQ_IE_LIFETIME(preq_elem);
450 ttl = ifsta->mshcfg.dot11MeshTTL;
451 if (ttl != 0)
452 mesh_path_sel_frame_tx(MPATH_PREP, 0, dst_addr,
453 __cpu_to_le32(dst_dsn), 0, orig_addr,
454 __cpu_to_le32(orig_dsn), mgmt->sa, 0, ttl,
455 __cpu_to_le32(lifetime), __cpu_to_le32(metric),
456 0, dev);
457 else
458 ifsta->mshstats.dropped_frames_ttl++;
459 }
460
461 if (forward) {
462 u32 preq_id;
463 u8 hopcount, flags;
464
465 ttl = PREQ_IE_TTL(preq_elem);
466 lifetime = PREQ_IE_LIFETIME(preq_elem);
467 if (ttl <= 1) {
468 ifsta->mshstats.dropped_frames_ttl++;
469 return;
470 }
471 --ttl;
472 flags = PREQ_IE_FLAGS(preq_elem);
473 preq_id = PREQ_IE_PREQ_ID(preq_elem);
474 hopcount = PREQ_IE_HOPCOUNT(preq_elem) + 1;
475 mesh_path_sel_frame_tx(MPATH_PREQ, flags, orig_addr,
476 __cpu_to_le32(orig_dsn), dst_flags, dst_addr,
477 __cpu_to_le32(dst_dsn), dev->broadcast,
478 hopcount, ttl, __cpu_to_le32(lifetime),
479 __cpu_to_le32(metric), __cpu_to_le32(preq_id),
480 dev);
481 ifsta->mshstats.fwded_frames++;
482 }
483}
484
485
486static void hwmp_prep_frame_process(struct net_device *dev,
487 struct ieee80211_mgmt *mgmt,
488 u8 *prep_elem, u32 metric)
489{
490 struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
491 struct mesh_path *mpath;
492 u8 *dst_addr, *orig_addr;
493 u8 ttl, hopcount, flags;
494 u8 next_hop[ETH_ALEN];
495 u32 dst_dsn, orig_dsn, lifetime;
496
497 /* Note that we divert from the draft nomenclature and denominate
498 * destination to what the draft refers to as origininator. So in this
499 * function destnation refers to the final destination of the PREP,
500 * which corresponds with the originator of the PREQ which this PREP
501 * replies
502 */
503 dst_addr = PREP_IE_DST_ADDR(prep_elem);
504 if (memcmp(dst_addr, dev->dev_addr, ETH_ALEN) == 0)
505 /* destination, no forwarding required */
506 return;
507
508 ttl = PREP_IE_TTL(prep_elem);
509 if (ttl <= 1) {
510 sdata->u.sta.mshstats.dropped_frames_ttl++;
511 return;
512 }
513
514 rcu_read_lock();
515 mpath = mesh_path_lookup(dst_addr, dev);
516 if (mpath)
517 spin_lock_bh(&mpath->state_lock);
518 else
519 goto fail;
520 if (!(mpath->flags & MESH_PATH_ACTIVE)) {
521 spin_unlock_bh(&mpath->state_lock);
522 goto fail;
523 }
524 memcpy(next_hop, mpath->next_hop->addr, ETH_ALEN);
525 spin_unlock_bh(&mpath->state_lock);
526 --ttl;
527 flags = PREP_IE_FLAGS(prep_elem);
528 lifetime = PREP_IE_LIFETIME(prep_elem);
529 hopcount = PREP_IE_HOPCOUNT(prep_elem) + 1;
530 orig_addr = PREP_IE_ORIG_ADDR(prep_elem);
531 dst_dsn = PREP_IE_DST_DSN(prep_elem);
532 orig_dsn = PREP_IE_ORIG_DSN(prep_elem);
533
534 mesh_path_sel_frame_tx(MPATH_PREP, flags, orig_addr,
535 __cpu_to_le32(orig_dsn), 0, dst_addr,
536 __cpu_to_le32(dst_dsn), mpath->next_hop->addr, hopcount, ttl,
537 __cpu_to_le32(lifetime), __cpu_to_le32(metric),
538 0, dev);
539 rcu_read_unlock();
540 sdata->u.sta.mshstats.fwded_frames++;
541 return;
542
543fail:
544 rcu_read_unlock();
545 sdata->u.sta.mshstats.dropped_frames_no_route++;
546 return;
547}
548
549static void hwmp_perr_frame_process(struct net_device *dev,
550 struct ieee80211_mgmt *mgmt, u8 *perr_elem)
551{
552 struct mesh_path *mpath;
553 u8 *ta, *dst_addr;
554 u32 dst_dsn;
555
556 ta = mgmt->sa;
557 dst_addr = PERR_IE_DST_ADDR(perr_elem);
558 dst_dsn = PERR_IE_DST_DSN(perr_elem);
559 rcu_read_lock();
560 mpath = mesh_path_lookup(dst_addr, dev);
561 if (mpath) {
562 spin_lock_bh(&mpath->state_lock);
563 if (mpath->flags & MESH_PATH_ACTIVE &&
564 memcmp(ta, mpath->next_hop->addr, ETH_ALEN) == 0 &&
565 (!(mpath->flags & MESH_PATH_DSN_VALID) ||
566 DSN_GT(dst_dsn, mpath->dsn))) {
567 mpath->flags &= ~MESH_PATH_ACTIVE;
568 mpath->dsn = dst_dsn;
569 spin_unlock_bh(&mpath->state_lock);
570 mesh_path_error_tx(dst_addr, dst_dsn, dev->broadcast,
571 dev);
572 } else
573 spin_unlock_bh(&mpath->state_lock);
574 }
575 rcu_read_unlock();
576}
577
578
579
580void mesh_rx_path_sel_frame(struct net_device *dev,
581 struct ieee80211_mgmt *mgmt,
582 size_t len)
583{
584 struct ieee802_11_elems elems;
585 size_t baselen;
586 u32 last_hop_metric;
587
588 baselen = (u8 *) mgmt->u.action.u.mesh_action.variable - (u8 *) mgmt;
589 ieee802_11_parse_elems(mgmt->u.action.u.mesh_action.variable,
590 len - baselen, &elems);
591
592 switch (mgmt->u.action.u.mesh_action.action_code) {
593 case MPATH_PREQ:
594 if (!elems.preq || elems.preq_len != 37)
595 /* Right now we support just 1 destination and no AE */
596 return;
597 last_hop_metric = hwmp_route_info_get(dev, mgmt, elems.preq);
598 if (!last_hop_metric)
599 return;
600 hwmp_preq_frame_process(dev, mgmt, elems.preq, last_hop_metric);
601 break;
602 case MPATH_PREP:
603 if (!elems.prep || elems.prep_len != 31)
604 /* Right now we support no AE */
605 return;
606 last_hop_metric = hwmp_route_info_get(dev, mgmt, elems.prep);
607 if (!last_hop_metric)
608 return;
609 hwmp_prep_frame_process(dev, mgmt, elems.prep, last_hop_metric);
610 break;
611 case MPATH_PERR:
612 if (!elems.perr || elems.perr_len != 12)
613 /* Right now we support only one destination per PERR */
614 return;
615 hwmp_perr_frame_process(dev, mgmt, elems.perr);
616 default:
617 return;
618 }
619
620}
621
622/**
623 * mesh_queue_preq - queue a PREQ to a given destination
624 *
625 * @mpath: mesh path to discover
626 * @flags: special attributes of the PREQ to be sent
627 *
628 * Locking: the function must be called from within a rcu read lock block.
629 *
630 */
631static void mesh_queue_preq(struct mesh_path *mpath, u8 flags)
632{
633 struct ieee80211_sub_if_data *sdata =
634 IEEE80211_DEV_TO_SUB_IF(mpath->dev);
635 struct ieee80211_if_sta *ifsta = &sdata->u.sta;
636 struct mesh_preq_queue *preq_node;
637
638 preq_node = kmalloc(sizeof(struct mesh_preq_queue), GFP_KERNEL);
639 if (!preq_node) {
640 printk(KERN_DEBUG "Mesh HWMP: could not allocate PREQ node\n");
641 return;
642 }
643
644 spin_lock(&ifsta->mesh_preq_queue_lock);
645 if (ifsta->preq_queue_len == MAX_PREQ_QUEUE_LEN) {
646 spin_unlock(&ifsta->mesh_preq_queue_lock);
647 kfree(preq_node);
648 if (printk_ratelimit())
649 printk(KERN_DEBUG "Mesh HWMP: PREQ node queue full\n");
650 return;
651 }
652
653 memcpy(preq_node->dst, mpath->dst, ETH_ALEN);
654 preq_node->flags = flags;
655
656 list_add_tail(&preq_node->list, &ifsta->preq_queue.list);
657 ++ifsta->preq_queue_len;
658 spin_unlock(&ifsta->mesh_preq_queue_lock);
659
660 if (time_after(jiffies, ifsta->last_preq + min_preq_int_jiff(sdata)))
661 queue_work(sdata->local->hw.workqueue, &ifsta->work);
662
663 else if (time_before(jiffies, ifsta->last_preq)) {
664 /* avoid long wait if did not send preqs for a long time
665 * and jiffies wrapped around
666 */
667 ifsta->last_preq = jiffies - min_preq_int_jiff(sdata) - 1;
668 queue_work(sdata->local->hw.workqueue, &ifsta->work);
669 } else
670 mod_timer(&ifsta->mesh_path_timer, ifsta->last_preq +
671 min_preq_int_jiff(sdata));
672}
673
674/**
675 * mesh_path_start_discovery - launch a path discovery from the PREQ queue
676 *
677 * @dev: local mesh interface
678 */
679void mesh_path_start_discovery(struct net_device *dev)
680{
681 struct ieee80211_sub_if_data *sdata =
682 IEEE80211_DEV_TO_SUB_IF(dev);
683 struct ieee80211_if_sta *ifsta = &sdata->u.sta;
684 struct mesh_preq_queue *preq_node;
685 struct mesh_path *mpath;
686 u8 ttl, dst_flags;
687 u32 lifetime;
688
689 spin_lock(&ifsta->mesh_preq_queue_lock);
690 if (!ifsta->preq_queue_len ||
691 time_before(jiffies, ifsta->last_preq +
692 min_preq_int_jiff(sdata))) {
693 spin_unlock(&ifsta->mesh_preq_queue_lock);
694 return;
695 }
696
697 preq_node = list_first_entry(&ifsta->preq_queue.list,
698 struct mesh_preq_queue, list);
699 list_del(&preq_node->list);
700 --ifsta->preq_queue_len;
701 spin_unlock(&ifsta->mesh_preq_queue_lock);
702
703 rcu_read_lock();
704 mpath = mesh_path_lookup(preq_node->dst, dev);
705 if (!mpath)
706 goto enddiscovery;
707
708 spin_lock_bh(&mpath->state_lock);
709 if (preq_node->flags & PREQ_Q_F_START) {
710 if (mpath->flags & MESH_PATH_RESOLVING) {
711 spin_unlock_bh(&mpath->state_lock);
712 goto enddiscovery;
713 } else {
714 mpath->flags &= ~MESH_PATH_RESOLVED;
715 mpath->flags |= MESH_PATH_RESOLVING;
716 mpath->discovery_retries = 0;
717 mpath->discovery_timeout = disc_timeout_jiff(sdata);
718 }
719 } else if (!(mpath->flags & MESH_PATH_RESOLVING) ||
720 mpath->flags & MESH_PATH_RESOLVED) {
721 mpath->flags &= ~MESH_PATH_RESOLVING;
722 spin_unlock_bh(&mpath->state_lock);
723 goto enddiscovery;
724 }
725
726 ifsta->last_preq = jiffies;
727
728 if (time_after(jiffies, ifsta->last_dsn_update +
729 net_traversal_jiffies(sdata)) ||
730 time_before(jiffies, ifsta->last_dsn_update)) {
731 ++ifsta->dsn;
732 sdata->u.sta.last_dsn_update = jiffies;
733 }
734 lifetime = default_lifetime(sdata);
735 ttl = sdata->u.sta.mshcfg.dot11MeshTTL;
736 if (ttl == 0) {
737 sdata->u.sta.mshstats.dropped_frames_ttl++;
738 spin_unlock_bh(&mpath->state_lock);
739 goto enddiscovery;
740 }
741
742 if (preq_node->flags & PREQ_Q_F_REFRESH)
743 dst_flags = MP_F_DO;
744 else
745 dst_flags = MP_F_RF;
746
747 spin_unlock_bh(&mpath->state_lock);
748 mesh_path_sel_frame_tx(MPATH_PREQ, 0, dev->dev_addr,
749 __cpu_to_le32(ifsta->dsn), dst_flags, mpath->dst,
750 __cpu_to_le32(mpath->dsn), dev->broadcast, 0,
751 ttl, __cpu_to_le32(lifetime), 0,
752 __cpu_to_le32(ifsta->preq_id++), dev);
753 mod_timer(&mpath->timer, jiffies + mpath->discovery_timeout);
754
755enddiscovery:
756 rcu_read_unlock();
757 kfree(preq_node);
758}
759
760/**
761 * ieee80211s_lookup_nexthop - put the appropriate next hop on a mesh frame
762 *
763 * @next_hop: output argument for next hop address
764 * @skb: frame to be sent
765 * @dev: network device the frame will be sent through
766 *
767 * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
768 * found, the function will start a path discovery and queue the frame so it is
769 * sent when the path is resolved. This means the caller must not free the skb
770 * in this case.
771 */
772int mesh_nexthop_lookup(u8 *next_hop, struct sk_buff *skb,
773 struct net_device *dev)
774{
775 struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
776 struct sk_buff *skb_to_free = NULL;
777 struct mesh_path *mpath;
778 int err = 0;
779
780 rcu_read_lock();
781 mpath = mesh_path_lookup(skb->data, dev);
782
783 if (!mpath) {
784 mesh_path_add(skb->data, dev);
785 mpath = mesh_path_lookup(skb->data, dev);
786 if (!mpath) {
787 dev_kfree_skb(skb);
788 sdata->u.sta.mshstats.dropped_frames_no_route++;
789 err = -ENOSPC;
790 goto endlookup;
791 }
792 }
793
794 if (mpath->flags & MESH_PATH_ACTIVE) {
795 if (time_after(jiffies, mpath->exp_time -
796 msecs_to_jiffies(sdata->u.sta.mshcfg.path_refresh_time))
797 && skb->pkt_type != PACKET_OTHERHOST
798 && !(mpath->flags & MESH_PATH_RESOLVING)
799 && !(mpath->flags & MESH_PATH_FIXED)) {
800 mesh_queue_preq(mpath,
801 PREQ_Q_F_START | PREQ_Q_F_REFRESH);
802 }
803 memcpy(next_hop, mpath->next_hop->addr,
804 ETH_ALEN);
805 } else {
806 if (!(mpath->flags & MESH_PATH_RESOLVING)) {
807 /* Start discovery only if it is not running yet */
808 mesh_queue_preq(mpath, PREQ_Q_F_START);
809 }
810
811 if (skb_queue_len(&mpath->frame_queue) >=
812 MESH_FRAME_QUEUE_LEN) {
813 skb_to_free = mpath->frame_queue.next;
814 skb_unlink(skb_to_free, &mpath->frame_queue);
815 }
816
817 skb_queue_tail(&mpath->frame_queue, skb);
818 if (skb_to_free)
819 mesh_path_discard_frame(skb_to_free, dev);
820 err = -ENOENT;
821 }
822
823endlookup:
824 rcu_read_unlock();
825 return err;
826}
827
828void mesh_path_timer(unsigned long data)
829{
830 struct ieee80211_sub_if_data *sdata;
831 struct mesh_path *mpath;
832 bool delete = false;
833
834 rcu_read_lock();
835 mpath = (struct mesh_path *) data;
836 mpath = rcu_dereference(mpath);
837 if (!mpath)
838 goto endmpathtimer;
839 spin_lock_bh(&mpath->state_lock);
840 sdata = IEEE80211_DEV_TO_SUB_IF(mpath->dev);
841 if (mpath->flags & MESH_PATH_DELETE) {
842 mpath->flags = 0;
843 delete = true;
844 } else if (mpath->flags & MESH_PATH_RESOLVED ||
845 (!(mpath->flags & MESH_PATH_RESOLVING)))
846 mpath->flags &= ~(MESH_PATH_RESOLVING | MESH_PATH_RESOLVED);
847 else if (mpath->discovery_retries < max_preq_retries(sdata)) {
848 ++mpath->discovery_retries;
849 mpath->discovery_timeout *= 2;
850 mesh_queue_preq(mpath, 0);
851 } else {
852 mpath->flags = 0;
853 mpath->exp_time = jiffies;
854 mesh_path_flush_pending(mpath);
855 }
856
857 spin_unlock_bh(&mpath->state_lock);
858endmpathtimer:
859 rcu_read_unlock();
860 if (delete)
861 mesh_path_del(mpath->dst, mpath->dev);
862}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-12 04:54:27 -0500