2 * Copyright (c) 2008, 2009 open80211s Ltd.
3 * Author: Luis Carlos Cobo <luisca@cozybit.com>
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.
10 #include <linux/slab.h>
13 #ifdef CONFIG_MAC80211_VERBOSE_MHWMP_DEBUG
14 #define mhwmp_dbg(fmt, args...) \
15 printk(KERN_DEBUG "Mesh HWMP (%s): " fmt "\n", sdata->name, ##args)
17 #define mhwmp_dbg(fmt, args...) do { (void)(0); } while (0)
20 #define TEST_FRAME_LEN 8192
21 #define MAX_METRIC 0xffffffff
24 /* Number of frames buffered per destination for unresolved destinations */
25 #define MESH_FRAME_QUEUE_LEN 10
26 #define MAX_PREQ_QUEUE_LEN 64
28 /* Destination only */
30 /* Reply and forward */
32 /* Unknown Sequence Number */
34 /* Reason code Present */
35 #define MP_F_RCODE 0x02
37 static void mesh_queue_preq(struct mesh_path
*, u8
);
39 static inline u32
u32_field_get(u8
*preq_elem
, int offset
, bool ae
)
43 return get_unaligned_le32(preq_elem
+ offset
);
46 static inline u32
u16_field_get(u8
*preq_elem
, int offset
, bool ae
)
50 return get_unaligned_le16(preq_elem
+ offset
);
53 /* HWMP IE processing macros */
55 #define AE_F_SET(x) (*x & AE_F)
56 #define PREQ_IE_FLAGS(x) (*(x))
57 #define PREQ_IE_HOPCOUNT(x) (*(x + 1))
58 #define PREQ_IE_TTL(x) (*(x + 2))
59 #define PREQ_IE_PREQ_ID(x) u32_field_get(x, 3, 0)
60 #define PREQ_IE_ORIG_ADDR(x) (x + 7)
61 #define PREQ_IE_ORIG_SN(x) u32_field_get(x, 13, 0)
62 #define PREQ_IE_LIFETIME(x) u32_field_get(x, 17, AE_F_SET(x))
63 #define PREQ_IE_METRIC(x) u32_field_get(x, 21, AE_F_SET(x))
64 #define PREQ_IE_TARGET_F(x) (*(AE_F_SET(x) ? x + 32 : x + 26))
65 #define PREQ_IE_TARGET_ADDR(x) (AE_F_SET(x) ? x + 33 : x + 27)
66 #define PREQ_IE_TARGET_SN(x) u32_field_get(x, 33, AE_F_SET(x))
69 #define PREP_IE_FLAGS(x) PREQ_IE_FLAGS(x)
70 #define PREP_IE_HOPCOUNT(x) PREQ_IE_HOPCOUNT(x)
71 #define PREP_IE_TTL(x) PREQ_IE_TTL(x)
72 #define PREP_IE_ORIG_ADDR(x) (AE_F_SET(x) ? x + 27 : x + 21)
73 #define PREP_IE_ORIG_SN(x) u32_field_get(x, 27, AE_F_SET(x))
74 #define PREP_IE_LIFETIME(x) u32_field_get(x, 13, AE_F_SET(x))
75 #define PREP_IE_METRIC(x) u32_field_get(x, 17, AE_F_SET(x))
76 #define PREP_IE_TARGET_ADDR(x) (x + 3)
77 #define PREP_IE_TARGET_SN(x) u32_field_get(x, 9, 0)
79 #define PERR_IE_TTL(x) (*(x))
80 #define PERR_IE_TARGET_FLAGS(x) (*(x + 2))
81 #define PERR_IE_TARGET_ADDR(x) (x + 3)
82 #define PERR_IE_TARGET_SN(x) u32_field_get(x, 9, 0)
83 #define PERR_IE_TARGET_RCODE(x) u16_field_get(x, 13, 0)
85 #define MSEC_TO_TU(x) (x*1000/1024)
86 #define SN_GT(x, y) ((long) (y) - (long) (x) < 0)
87 #define SN_LT(x, y) ((long) (x) - (long) (y) < 0)
89 #define net_traversal_jiffies(s) \
90 msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPnetDiameterTraversalTime)
91 #define default_lifetime(s) \
92 MSEC_TO_TU(s->u.mesh.mshcfg.dot11MeshHWMPactivePathTimeout)
93 #define min_preq_int_jiff(s) \
94 (msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPpreqMinInterval))
95 #define max_preq_retries(s) (s->u.mesh.mshcfg.dot11MeshHWMPmaxPREQretries)
96 #define disc_timeout_jiff(s) \
97 msecs_to_jiffies(sdata->u.mesh.mshcfg.min_discovery_timeout)
99 enum mpath_frame_type
{
106 static const u8 broadcast_addr
[ETH_ALEN
] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
108 static int mesh_path_sel_frame_tx(enum mpath_frame_type action
, u8 flags
,
109 u8
*orig_addr
, __le32 orig_sn
, u8 target_flags
, u8
*target
,
110 __le32 target_sn
, const u8
*da
, u8 hop_count
, u8 ttl
,
111 __le32 lifetime
, __le32 metric
, __le32 preq_id
,
112 struct ieee80211_sub_if_data
*sdata
)
114 struct ieee80211_local
*local
= sdata
->local
;
115 struct sk_buff
*skb
= dev_alloc_skb(local
->hw
.extra_tx_headroom
+ 400);
116 struct ieee80211_mgmt
*mgmt
;
122 skb_reserve(skb
, local
->hw
.extra_tx_headroom
);
123 /* 25 is the size of the common mgmt part (24) plus the size of the
124 * common action part (1)
126 mgmt
= (struct ieee80211_mgmt
*)
127 skb_put(skb
, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
128 memset(mgmt
, 0, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
129 mgmt
->frame_control
= cpu_to_le16(IEEE80211_FTYPE_MGMT
|
130 IEEE80211_STYPE_ACTION
);
132 memcpy(mgmt
->da
, da
, ETH_ALEN
);
133 memcpy(mgmt
->sa
, sdata
->vif
.addr
, ETH_ALEN
);
135 memcpy(mgmt
->bssid
, sdata
->vif
.addr
, ETH_ALEN
);
136 mgmt
->u
.action
.category
= WLAN_CATEGORY_MESH_ACTION
;
137 mgmt
->u
.action
.u
.mesh_action
.action_code
=
138 WLAN_MESH_ACTION_HWMP_PATH_SELECTION
;
142 mhwmp_dbg("sending PREQ to %pM", target
);
144 pos
= skb_put(skb
, 2 + ie_len
);
145 *pos
++ = WLAN_EID_PREQ
;
148 mhwmp_dbg("sending PREP to %pM", target
);
150 pos
= skb_put(skb
, 2 + ie_len
);
151 *pos
++ = WLAN_EID_PREP
;
154 mhwmp_dbg("sending RANN from %pM", orig_addr
);
155 ie_len
= sizeof(struct ieee80211_rann_ie
);
156 pos
= skb_put(skb
, 2 + ie_len
);
157 *pos
++ = WLAN_EID_RANN
;
168 if (action
== MPATH_PREP
) {
169 memcpy(pos
, target
, ETH_ALEN
);
171 memcpy(pos
, &target_sn
, 4);
174 if (action
== MPATH_PREQ
) {
175 memcpy(pos
, &preq_id
, 4);
178 memcpy(pos
, orig_addr
, ETH_ALEN
);
180 memcpy(pos
, &orig_sn
, 4);
183 memcpy(pos
, &lifetime
, 4); /* interval for RANN */
185 memcpy(pos
, &metric
, 4);
187 if (action
== MPATH_PREQ
) {
188 *pos
++ = 1; /* destination count */
189 *pos
++ = target_flags
;
190 memcpy(pos
, target
, ETH_ALEN
);
192 memcpy(pos
, &target_sn
, 4);
194 } else if (action
== MPATH_PREP
) {
195 memcpy(pos
, orig_addr
, ETH_ALEN
);
197 memcpy(pos
, &orig_sn
, 4);
201 ieee80211_tx_skb(sdata
, skb
);
206 * mesh_send_path error - Sends a PERR mesh management frame
208 * @target: broken destination
209 * @target_sn: SN of the broken destination
210 * @target_rcode: reason code for this PERR
211 * @ra: node this frame is addressed to
213 int mesh_path_error_tx(u8 ttl
, u8
*target
, __le32 target_sn
,
214 __le16 target_rcode
, const u8
*ra
,
215 struct ieee80211_sub_if_data
*sdata
)
217 struct ieee80211_local
*local
= sdata
->local
;
218 struct sk_buff
*skb
= dev_alloc_skb(local
->hw
.extra_tx_headroom
+ 400);
219 struct ieee80211_mgmt
*mgmt
;
225 skb_reserve(skb
, local
->hw
.extra_tx_headroom
);
226 /* 25 is the size of the common mgmt part (24) plus the size of the
227 * common action part (1)
229 mgmt
= (struct ieee80211_mgmt
*)
230 skb_put(skb
, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
231 memset(mgmt
, 0, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
232 mgmt
->frame_control
= cpu_to_le16(IEEE80211_FTYPE_MGMT
|
233 IEEE80211_STYPE_ACTION
);
235 memcpy(mgmt
->da
, ra
, ETH_ALEN
);
236 memcpy(mgmt
->sa
, sdata
->vif
.addr
, ETH_ALEN
);
238 memcpy(mgmt
->bssid
, sdata
->vif
.addr
, ETH_ALEN
);
239 mgmt
->u
.action
.category
= WLAN_CATEGORY_MESH_ACTION
;
240 mgmt
->u
.action
.u
.mesh_action
.action_code
=
241 WLAN_MESH_ACTION_HWMP_PATH_SELECTION
;
243 pos
= skb_put(skb
, 2 + ie_len
);
244 *pos
++ = WLAN_EID_PERR
;
248 /* number of destinations */
251 * flags bit, bit 1 is unset if we know the sequence number and
252 * bit 2 is set if we have a reason code
260 memcpy(pos
, target
, ETH_ALEN
);
262 memcpy(pos
, &target_sn
, 4);
264 memcpy(pos
, &target_rcode
, 2);
266 ieee80211_tx_skb(sdata
, skb
);
270 void ieee80211s_update_metric(struct ieee80211_local
*local
,
271 struct sta_info
*stainfo
, struct sk_buff
*skb
)
273 struct ieee80211_tx_info
*txinfo
= IEEE80211_SKB_CB(skb
);
274 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
277 if (!ieee80211_is_data(hdr
->frame_control
))
280 failed
= !(txinfo
->flags
& IEEE80211_TX_STAT_ACK
);
282 /* moving average, scaled to 100 */
283 stainfo
->fail_avg
= ((80 * stainfo
->fail_avg
+ 5) / 100 + 20 * failed
);
284 if (stainfo
->fail_avg
> 95)
285 mesh_plink_broken(stainfo
);
288 static u32
airtime_link_metric_get(struct ieee80211_local
*local
,
289 struct sta_info
*sta
)
291 struct ieee80211_supported_band
*sband
;
292 /* This should be adjusted for each device */
293 int device_constant
= 1 << ARITH_SHIFT
;
294 int test_frame_len
= TEST_FRAME_LEN
<< ARITH_SHIFT
;
295 int s_unit
= 1 << ARITH_SHIFT
;
297 u32 tx_time
, estimated_retx
;
300 sband
= local
->hw
.wiphy
->bands
[local
->hw
.conf
.channel
->band
];
302 if (sta
->fail_avg
>= 100)
305 if (sta
->last_tx_rate
.flags
& IEEE80211_TX_RC_MCS
)
308 err
= (sta
->fail_avg
<< ARITH_SHIFT
) / 100;
310 /* bitrate is in units of 100 Kbps, while we need rate in units of
311 * 1Mbps. This will be corrected on tx_time computation.
313 rate
= sband
->bitrates
[sta
->last_tx_rate
.idx
].bitrate
;
314 tx_time
= (device_constant
+ 10 * test_frame_len
/ rate
);
315 estimated_retx
= ((1 << (2 * ARITH_SHIFT
)) / (s_unit
- err
));
316 result
= (tx_time
* estimated_retx
) >> (2 * ARITH_SHIFT
) ;
321 * hwmp_route_info_get - Update routing info to originator and transmitter
323 * @sdata: local mesh subif
324 * @mgmt: mesh management frame
325 * @hwmp_ie: hwmp information element (PREP or PREQ)
327 * This function updates the path routing information to the originator and the
328 * transmitter of a HWMP PREQ or PREP frame.
330 * Returns: metric to frame originator or 0 if the frame should not be further
333 * Notes: this function is the only place (besides user-provided info) where
334 * path routing information is updated.
336 static u32
hwmp_route_info_get(struct ieee80211_sub_if_data
*sdata
,
337 struct ieee80211_mgmt
*mgmt
,
338 u8
*hwmp_ie
, enum mpath_frame_type action
)
340 struct ieee80211_local
*local
= sdata
->local
;
341 struct mesh_path
*mpath
;
342 struct sta_info
*sta
;
345 u32 orig_sn
, orig_metric
;
346 unsigned long orig_lifetime
, exp_time
;
347 u32 last_hop_metric
, new_metric
;
351 sta
= sta_info_get(sdata
, mgmt
->sa
);
357 last_hop_metric
= airtime_link_metric_get(local
, sta
);
358 /* Update and check originator routing info */
363 orig_addr
= PREQ_IE_ORIG_ADDR(hwmp_ie
);
364 orig_sn
= PREQ_IE_ORIG_SN(hwmp_ie
);
365 orig_lifetime
= PREQ_IE_LIFETIME(hwmp_ie
);
366 orig_metric
= PREQ_IE_METRIC(hwmp_ie
);
369 /* Originator here refers to the MP that was the destination in
370 * the Path Request. The draft refers to that MP as the
371 * destination address, even though usually it is the origin of
372 * the PREP frame. We divert from the nomenclature in the draft
373 * so that we can easily use a single function to gather path
374 * information from both PREQ and PREP frames.
376 orig_addr
= PREP_IE_ORIG_ADDR(hwmp_ie
);
377 orig_sn
= PREP_IE_ORIG_SN(hwmp_ie
);
378 orig_lifetime
= PREP_IE_LIFETIME(hwmp_ie
);
379 orig_metric
= PREP_IE_METRIC(hwmp_ie
);
385 new_metric
= orig_metric
+ last_hop_metric
;
386 if (new_metric
< orig_metric
)
387 new_metric
= MAX_METRIC
;
388 exp_time
= TU_TO_EXP_TIME(orig_lifetime
);
390 if (memcmp(orig_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0) {
391 /* This MP is the originator, we are not interested in this
392 * frame, except for updating transmitter's path info.
397 mpath
= mesh_path_lookup(orig_addr
, sdata
);
399 spin_lock_bh(&mpath
->state_lock
);
400 if (mpath
->flags
& MESH_PATH_FIXED
)
402 else if ((mpath
->flags
& MESH_PATH_ACTIVE
) &&
403 (mpath
->flags
& MESH_PATH_SN_VALID
)) {
404 if (SN_GT(mpath
->sn
, orig_sn
) ||
405 (mpath
->sn
== orig_sn
&&
406 new_metric
>= mpath
->metric
)) {
412 mesh_path_add(orig_addr
, sdata
);
413 mpath
= mesh_path_lookup(orig_addr
, sdata
);
418 spin_lock_bh(&mpath
->state_lock
);
422 mesh_path_assign_nexthop(mpath
, sta
);
423 mpath
->flags
|= MESH_PATH_SN_VALID
;
424 mpath
->metric
= new_metric
;
426 mpath
->exp_time
= time_after(mpath
->exp_time
, exp_time
)
427 ? mpath
->exp_time
: exp_time
;
428 mesh_path_activate(mpath
);
429 spin_unlock_bh(&mpath
->state_lock
);
430 mesh_path_tx_pending(mpath
);
431 /* draft says preq_id should be saved to, but there does
432 * not seem to be any use for it, skipping by now
435 spin_unlock_bh(&mpath
->state_lock
);
438 /* Update and check transmitter routing info */
440 if (memcmp(orig_addr
, ta
, ETH_ALEN
) == 0)
445 mpath
= mesh_path_lookup(ta
, sdata
);
447 spin_lock_bh(&mpath
->state_lock
);
448 if ((mpath
->flags
& MESH_PATH_FIXED
) ||
449 ((mpath
->flags
& MESH_PATH_ACTIVE
) &&
450 (last_hop_metric
> mpath
->metric
)))
453 mesh_path_add(ta
, sdata
);
454 mpath
= mesh_path_lookup(ta
, sdata
);
459 spin_lock_bh(&mpath
->state_lock
);
463 mesh_path_assign_nexthop(mpath
, sta
);
464 mpath
->metric
= last_hop_metric
;
465 mpath
->exp_time
= time_after(mpath
->exp_time
, exp_time
)
466 ? mpath
->exp_time
: exp_time
;
467 mesh_path_activate(mpath
);
468 spin_unlock_bh(&mpath
->state_lock
);
469 mesh_path_tx_pending(mpath
);
471 spin_unlock_bh(&mpath
->state_lock
);
476 return process
? new_metric
: 0;
479 static void hwmp_preq_frame_process(struct ieee80211_sub_if_data
*sdata
,
480 struct ieee80211_mgmt
*mgmt
,
481 u8
*preq_elem
, u32 metric
)
483 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
484 struct mesh_path
*mpath
;
485 u8
*target_addr
, *orig_addr
;
486 u8 target_flags
, ttl
;
487 u32 orig_sn
, target_sn
, lifetime
;
491 /* Update target SN, if present */
492 target_addr
= PREQ_IE_TARGET_ADDR(preq_elem
);
493 orig_addr
= PREQ_IE_ORIG_ADDR(preq_elem
);
494 target_sn
= PREQ_IE_TARGET_SN(preq_elem
);
495 orig_sn
= PREQ_IE_ORIG_SN(preq_elem
);
496 target_flags
= PREQ_IE_TARGET_F(preq_elem
);
498 mhwmp_dbg("received PREQ from %pM", orig_addr
);
500 if (memcmp(target_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0) {
501 mhwmp_dbg("PREQ is for us");
505 if (time_after(jiffies
, ifmsh
->last_sn_update
+
506 net_traversal_jiffies(sdata
)) ||
507 time_before(jiffies
, ifmsh
->last_sn_update
)) {
508 target_sn
= ++ifmsh
->sn
;
509 ifmsh
->last_sn_update
= jiffies
;
513 mpath
= mesh_path_lookup(target_addr
, sdata
);
515 if ((!(mpath
->flags
& MESH_PATH_SN_VALID
)) ||
516 SN_LT(mpath
->sn
, target_sn
)) {
517 mpath
->sn
= target_sn
;
518 mpath
->flags
|= MESH_PATH_SN_VALID
;
519 } else if ((!(target_flags
& MP_F_DO
)) &&
520 (mpath
->flags
& MESH_PATH_ACTIVE
)) {
522 metric
= mpath
->metric
;
523 target_sn
= mpath
->sn
;
524 if (target_flags
& MP_F_RF
)
525 target_flags
|= MP_F_DO
;
534 lifetime
= PREQ_IE_LIFETIME(preq_elem
);
535 ttl
= ifmsh
->mshcfg
.element_ttl
;
537 mhwmp_dbg("replying to the PREQ");
538 mesh_path_sel_frame_tx(MPATH_PREP
, 0, target_addr
,
539 cpu_to_le32(target_sn
), 0, orig_addr
,
540 cpu_to_le32(orig_sn
), mgmt
->sa
, 0, ttl
,
541 cpu_to_le32(lifetime
), cpu_to_le32(metric
),
544 ifmsh
->mshstats
.dropped_frames_ttl
++;
551 ttl
= PREQ_IE_TTL(preq_elem
);
552 lifetime
= PREQ_IE_LIFETIME(preq_elem
);
554 ifmsh
->mshstats
.dropped_frames_ttl
++;
557 mhwmp_dbg("forwarding the PREQ from %pM", orig_addr
);
559 flags
= PREQ_IE_FLAGS(preq_elem
);
560 preq_id
= PREQ_IE_PREQ_ID(preq_elem
);
561 hopcount
= PREQ_IE_HOPCOUNT(preq_elem
) + 1;
562 mesh_path_sel_frame_tx(MPATH_PREQ
, flags
, orig_addr
,
563 cpu_to_le32(orig_sn
), target_flags
, target_addr
,
564 cpu_to_le32(target_sn
), broadcast_addr
,
565 hopcount
, ttl
, cpu_to_le32(lifetime
),
566 cpu_to_le32(metric
), cpu_to_le32(preq_id
),
568 ifmsh
->mshstats
.fwded_mcast
++;
569 ifmsh
->mshstats
.fwded_frames
++;
574 static inline struct sta_info
*
575 next_hop_deref_protected(struct mesh_path
*mpath
)
577 return rcu_dereference_protected(mpath
->next_hop
,
578 lockdep_is_held(&mpath
->state_lock
));
582 static void hwmp_prep_frame_process(struct ieee80211_sub_if_data
*sdata
,
583 struct ieee80211_mgmt
*mgmt
,
584 u8
*prep_elem
, u32 metric
)
586 struct mesh_path
*mpath
;
587 u8
*target_addr
, *orig_addr
;
588 u8 ttl
, hopcount
, flags
;
589 u8 next_hop
[ETH_ALEN
];
590 u32 target_sn
, orig_sn
, lifetime
;
592 mhwmp_dbg("received PREP from %pM", PREP_IE_ORIG_ADDR(prep_elem
));
594 /* Note that we divert from the draft nomenclature and denominate
595 * destination to what the draft refers to as origininator. So in this
596 * function destnation refers to the final destination of the PREP,
597 * which corresponds with the originator of the PREQ which this PREP
600 target_addr
= PREP_IE_TARGET_ADDR(prep_elem
);
601 if (memcmp(target_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
602 /* destination, no forwarding required */
605 ttl
= PREP_IE_TTL(prep_elem
);
607 sdata
->u
.mesh
.mshstats
.dropped_frames_ttl
++;
612 mpath
= mesh_path_lookup(target_addr
, sdata
);
614 spin_lock_bh(&mpath
->state_lock
);
617 if (!(mpath
->flags
& MESH_PATH_ACTIVE
)) {
618 spin_unlock_bh(&mpath
->state_lock
);
621 memcpy(next_hop
, next_hop_deref_protected(mpath
)->sta
.addr
, ETH_ALEN
);
622 spin_unlock_bh(&mpath
->state_lock
);
624 flags
= PREP_IE_FLAGS(prep_elem
);
625 lifetime
= PREP_IE_LIFETIME(prep_elem
);
626 hopcount
= PREP_IE_HOPCOUNT(prep_elem
) + 1;
627 orig_addr
= PREP_IE_ORIG_ADDR(prep_elem
);
628 target_sn
= PREP_IE_TARGET_SN(prep_elem
);
629 orig_sn
= PREP_IE_ORIG_SN(prep_elem
);
631 mesh_path_sel_frame_tx(MPATH_PREP
, flags
, orig_addr
,
632 cpu_to_le32(orig_sn
), 0, target_addr
,
633 cpu_to_le32(target_sn
), next_hop
, hopcount
,
634 ttl
, cpu_to_le32(lifetime
), cpu_to_le32(metric
),
638 sdata
->u
.mesh
.mshstats
.fwded_unicast
++;
639 sdata
->u
.mesh
.mshstats
.fwded_frames
++;
644 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
647 static void hwmp_perr_frame_process(struct ieee80211_sub_if_data
*sdata
,
648 struct ieee80211_mgmt
*mgmt
, u8
*perr_elem
)
650 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
651 struct mesh_path
*mpath
;
653 u8
*ta
, *target_addr
;
658 ttl
= PERR_IE_TTL(perr_elem
);
660 ifmsh
->mshstats
.dropped_frames_ttl
++;
664 target_addr
= PERR_IE_TARGET_ADDR(perr_elem
);
665 target_sn
= PERR_IE_TARGET_SN(perr_elem
);
666 target_rcode
= PERR_IE_TARGET_RCODE(perr_elem
);
669 mpath
= mesh_path_lookup(target_addr
, sdata
);
671 spin_lock_bh(&mpath
->state_lock
);
672 if (mpath
->flags
& MESH_PATH_ACTIVE
&&
673 memcmp(ta
, next_hop_deref_protected(mpath
)->sta
.addr
,
675 (!(mpath
->flags
& MESH_PATH_SN_VALID
) ||
676 SN_GT(target_sn
, mpath
->sn
))) {
677 mpath
->flags
&= ~MESH_PATH_ACTIVE
;
678 mpath
->sn
= target_sn
;
679 spin_unlock_bh(&mpath
->state_lock
);
680 mesh_path_error_tx(ttl
, target_addr
, cpu_to_le32(target_sn
),
681 cpu_to_le16(target_rcode
),
682 broadcast_addr
, sdata
);
684 spin_unlock_bh(&mpath
->state_lock
);
689 static void hwmp_rann_frame_process(struct ieee80211_sub_if_data
*sdata
,
690 struct ieee80211_mgmt
*mgmt
,
691 struct ieee80211_rann_ie
*rann
)
693 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
694 struct mesh_path
*mpath
;
695 u8 ttl
, flags
, hopcount
;
698 u32 interval
= cpu_to_le32(IEEE80211_MESH_RANN_INTERVAL
);
700 ttl
= rann
->rann_ttl
;
702 ifmsh
->mshstats
.dropped_frames_ttl
++;
706 flags
= rann
->rann_flags
;
707 orig_addr
= rann
->rann_addr
;
708 orig_sn
= rann
->rann_seq
;
709 hopcount
= rann
->rann_hopcount
;
711 metric
= rann
->rann_metric
;
712 mhwmp_dbg("received RANN from %pM\n", orig_addr
);
715 mpath
= mesh_path_lookup(orig_addr
, sdata
);
717 mesh_path_add(orig_addr
, sdata
);
718 mpath
= mesh_path_lookup(orig_addr
, sdata
);
721 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
724 mesh_queue_preq(mpath
,
725 PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
727 if (mpath
->sn
< orig_sn
) {
728 mesh_path_sel_frame_tx(MPATH_RANN
, flags
, orig_addr
,
729 cpu_to_le32(orig_sn
),
730 0, NULL
, 0, broadcast_addr
,
731 hopcount
, ttl
, interval
,
732 cpu_to_le32(metric
+ mpath
->metric
),
740 void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data
*sdata
,
741 struct ieee80211_mgmt
*mgmt
,
744 struct ieee802_11_elems elems
;
748 /* need action_code */
749 if (len
< IEEE80211_MIN_ACTION_SIZE
+ 1)
752 baselen
= (u8
*) mgmt
->u
.action
.u
.mesh_action
.variable
- (u8
*) mgmt
;
753 ieee802_11_parse_elems(mgmt
->u
.action
.u
.mesh_action
.variable
,
754 len
- baselen
, &elems
);
757 if (elems
.preq_len
!= 37)
758 /* Right now we support just 1 destination and no AE */
760 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.preq
,
763 hwmp_preq_frame_process(sdata
, mgmt
, elems
.preq
,
767 if (elems
.prep_len
!= 31)
768 /* Right now we support no AE */
770 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.prep
,
773 hwmp_prep_frame_process(sdata
, mgmt
, elems
.prep
,
777 if (elems
.perr_len
!= 15)
778 /* Right now we support only one destination per PERR */
780 hwmp_perr_frame_process(sdata
, mgmt
, elems
.perr
);
783 hwmp_rann_frame_process(sdata
, mgmt
, elems
.rann
);
787 * mesh_queue_preq - queue a PREQ to a given destination
789 * @mpath: mesh path to discover
790 * @flags: special attributes of the PREQ to be sent
792 * Locking: the function must be called from within a rcu read lock block.
795 static void mesh_queue_preq(struct mesh_path
*mpath
, u8 flags
)
797 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
798 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
799 struct mesh_preq_queue
*preq_node
;
801 preq_node
= kmalloc(sizeof(struct mesh_preq_queue
), GFP_ATOMIC
);
803 mhwmp_dbg("could not allocate PREQ node");
807 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
808 if (ifmsh
->preq_queue_len
== MAX_PREQ_QUEUE_LEN
) {
809 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
811 if (printk_ratelimit())
812 mhwmp_dbg("PREQ node queue full");
816 memcpy(preq_node
->dst
, mpath
->dst
, ETH_ALEN
);
817 preq_node
->flags
= flags
;
819 list_add_tail(&preq_node
->list
, &ifmsh
->preq_queue
.list
);
820 ++ifmsh
->preq_queue_len
;
821 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
823 if (time_after(jiffies
, ifmsh
->last_preq
+ min_preq_int_jiff(sdata
)))
824 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
826 else if (time_before(jiffies
, ifmsh
->last_preq
)) {
827 /* avoid long wait if did not send preqs for a long time
828 * and jiffies wrapped around
830 ifmsh
->last_preq
= jiffies
- min_preq_int_jiff(sdata
) - 1;
831 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
833 mod_timer(&ifmsh
->mesh_path_timer
, ifmsh
->last_preq
+
834 min_preq_int_jiff(sdata
));
838 * mesh_path_start_discovery - launch a path discovery from the PREQ queue
840 * @sdata: local mesh subif
842 void mesh_path_start_discovery(struct ieee80211_sub_if_data
*sdata
)
844 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
845 struct mesh_preq_queue
*preq_node
;
846 struct mesh_path
*mpath
;
847 u8 ttl
, target_flags
;
850 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
851 if (!ifmsh
->preq_queue_len
||
852 time_before(jiffies
, ifmsh
->last_preq
+
853 min_preq_int_jiff(sdata
))) {
854 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
858 preq_node
= list_first_entry(&ifmsh
->preq_queue
.list
,
859 struct mesh_preq_queue
, list
);
860 list_del(&preq_node
->list
);
861 --ifmsh
->preq_queue_len
;
862 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
865 mpath
= mesh_path_lookup(preq_node
->dst
, sdata
);
869 spin_lock_bh(&mpath
->state_lock
);
870 if (preq_node
->flags
& PREQ_Q_F_START
) {
871 if (mpath
->flags
& MESH_PATH_RESOLVING
) {
872 spin_unlock_bh(&mpath
->state_lock
);
875 mpath
->flags
&= ~MESH_PATH_RESOLVED
;
876 mpath
->flags
|= MESH_PATH_RESOLVING
;
877 mpath
->discovery_retries
= 0;
878 mpath
->discovery_timeout
= disc_timeout_jiff(sdata
);
880 } else if (!(mpath
->flags
& MESH_PATH_RESOLVING
) ||
881 mpath
->flags
& MESH_PATH_RESOLVED
) {
882 mpath
->flags
&= ~MESH_PATH_RESOLVING
;
883 spin_unlock_bh(&mpath
->state_lock
);
887 ifmsh
->last_preq
= jiffies
;
889 if (time_after(jiffies
, ifmsh
->last_sn_update
+
890 net_traversal_jiffies(sdata
)) ||
891 time_before(jiffies
, ifmsh
->last_sn_update
)) {
893 sdata
->u
.mesh
.last_sn_update
= jiffies
;
895 lifetime
= default_lifetime(sdata
);
896 ttl
= sdata
->u
.mesh
.mshcfg
.element_ttl
;
898 sdata
->u
.mesh
.mshstats
.dropped_frames_ttl
++;
899 spin_unlock_bh(&mpath
->state_lock
);
903 if (preq_node
->flags
& PREQ_Q_F_REFRESH
)
904 target_flags
= MP_F_DO
;
906 target_flags
= MP_F_RF
;
908 spin_unlock_bh(&mpath
->state_lock
);
909 mesh_path_sel_frame_tx(MPATH_PREQ
, 0, sdata
->vif
.addr
,
910 cpu_to_le32(ifmsh
->sn
), target_flags
, mpath
->dst
,
911 cpu_to_le32(mpath
->sn
), broadcast_addr
, 0,
912 ttl
, cpu_to_le32(lifetime
), 0,
913 cpu_to_le32(ifmsh
->preq_id
++), sdata
);
914 mod_timer(&mpath
->timer
, jiffies
+ mpath
->discovery_timeout
);
922 * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
924 * @skb: 802.11 frame to be sent
925 * @sdata: network subif the frame will be sent through
927 * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
928 * found, the function will start a path discovery and queue the frame so it is
929 * sent when the path is resolved. This means the caller must not free the skb
932 int mesh_nexthop_lookup(struct sk_buff
*skb
,
933 struct ieee80211_sub_if_data
*sdata
)
935 struct sk_buff
*skb_to_free
= NULL
;
936 struct mesh_path
*mpath
;
937 struct sta_info
*next_hop
;
938 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
939 u8
*target_addr
= hdr
->addr3
;
943 mpath
= mesh_path_lookup(target_addr
, sdata
);
946 mesh_path_add(target_addr
, sdata
);
947 mpath
= mesh_path_lookup(target_addr
, sdata
);
949 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
955 if (mpath
->flags
& MESH_PATH_ACTIVE
) {
956 if (time_after(jiffies
,
958 msecs_to_jiffies(sdata
->u
.mesh
.mshcfg
.path_refresh_time
)) &&
959 !memcmp(sdata
->vif
.addr
, hdr
->addr4
, ETH_ALEN
) &&
960 !(mpath
->flags
& MESH_PATH_RESOLVING
) &&
961 !(mpath
->flags
& MESH_PATH_FIXED
)) {
962 mesh_queue_preq(mpath
,
963 PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
965 next_hop
= rcu_dereference(mpath
->next_hop
);
967 memcpy(hdr
->addr1
, next_hop
->sta
.addr
, ETH_ALEN
);
971 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
972 if (!(mpath
->flags
& MESH_PATH_RESOLVING
)) {
973 /* Start discovery only if it is not running yet */
974 mesh_queue_preq(mpath
, PREQ_Q_F_START
);
977 if (skb_queue_len(&mpath
->frame_queue
) >=
978 MESH_FRAME_QUEUE_LEN
)
979 skb_to_free
= skb_dequeue(&mpath
->frame_queue
);
981 info
->flags
|= IEEE80211_TX_INTFL_NEED_TXPROCESSING
;
982 skb_queue_tail(&mpath
->frame_queue
, skb
);
984 mesh_path_discard_frame(skb_to_free
, sdata
);
993 void mesh_path_timer(unsigned long data
)
995 struct mesh_path
*mpath
= (void *) data
;
996 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
998 if (sdata
->local
->quiescing
)
1001 spin_lock_bh(&mpath
->state_lock
);
1002 if (mpath
->flags
& MESH_PATH_RESOLVED
||
1003 (!(mpath
->flags
& MESH_PATH_RESOLVING
)))
1004 mpath
->flags
&= ~(MESH_PATH_RESOLVING
| MESH_PATH_RESOLVED
);
1005 else if (mpath
->discovery_retries
< max_preq_retries(sdata
)) {
1006 ++mpath
->discovery_retries
;
1007 mpath
->discovery_timeout
*= 2;
1008 mesh_queue_preq(mpath
, 0);
1011 mpath
->exp_time
= jiffies
;
1012 mesh_path_flush_pending(mpath
);
1015 spin_unlock_bh(&mpath
->state_lock
);
1019 mesh_path_tx_root_frame(struct ieee80211_sub_if_data
*sdata
)
1021 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
1022 u32 interval
= cpu_to_le32(IEEE80211_MESH_RANN_INTERVAL
);
1024 mesh_path_sel_frame_tx(MPATH_RANN
, 0, sdata
->vif
.addr
,
1025 cpu_to_le32(++ifmsh
->sn
),
1026 0, NULL
, 0, broadcast_addr
,
1027 0, sdata
->u
.mesh
.mshcfg
.element_ttl
,
1028 interval
, 0, 0, sdata
);