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
= ifmsh
->mshcfg
.dot11MeshHWMPRannInterval
;
701 ttl
= rann
->rann_ttl
;
703 ifmsh
->mshstats
.dropped_frames_ttl
++;
707 flags
= rann
->rann_flags
;
708 root_is_gate
= !!(flags
& RANN_FLAG_IS_GATE
);
709 orig_addr
= rann
->rann_addr
;
710 orig_sn
= rann
->rann_seq
;
711 hopcount
= rann
->rann_hopcount
;
713 metric
= rann
->rann_metric
;
715 /* Ignore our own RANNs */
716 if (memcmp(orig_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
719 mhwmp_dbg("received RANN from %pM (is_gate=%d)", orig_addr
,
723 mpath
= mesh_path_lookup(orig_addr
, sdata
);
725 mesh_path_add(orig_addr
, sdata
);
726 mpath
= mesh_path_lookup(orig_addr
, sdata
);
729 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
734 if ((!(mpath
->flags
& (MESH_PATH_ACTIVE
| MESH_PATH_RESOLVING
)) ||
735 time_after(jiffies
, mpath
->exp_time
- 1*HZ
)) &&
736 !(mpath
->flags
& MESH_PATH_FIXED
)) {
737 mhwmp_dbg("%s time to refresh root mpath %pM", sdata
->name
,
739 mesh_queue_preq(mpath
, PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
742 if (mpath
->sn
< orig_sn
) {
743 mesh_path_sel_frame_tx(MPATH_RANN
, flags
, orig_addr
,
744 cpu_to_le32(orig_sn
),
745 0, NULL
, 0, broadcast_addr
,
746 hopcount
, ttl
, cpu_to_le32(interval
),
747 cpu_to_le32(metric
+ mpath
->metric
),
752 mesh_path_add_gate(mpath
);
758 void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data
*sdata
,
759 struct ieee80211_mgmt
*mgmt
,
762 struct ieee802_11_elems elems
;
766 /* need action_code */
767 if (len
< IEEE80211_MIN_ACTION_SIZE
+ 1)
770 baselen
= (u8
*) mgmt
->u
.action
.u
.mesh_action
.variable
- (u8
*) mgmt
;
771 ieee802_11_parse_elems(mgmt
->u
.action
.u
.mesh_action
.variable
,
772 len
- baselen
, &elems
);
775 if (elems
.preq_len
!= 37)
776 /* Right now we support just 1 destination and no AE */
778 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.preq
,
781 hwmp_preq_frame_process(sdata
, mgmt
, elems
.preq
,
785 if (elems
.prep_len
!= 31)
786 /* Right now we support no AE */
788 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.prep
,
791 hwmp_prep_frame_process(sdata
, mgmt
, elems
.prep
,
795 if (elems
.perr_len
!= 15)
796 /* Right now we support only one destination per PERR */
798 hwmp_perr_frame_process(sdata
, mgmt
, elems
.perr
);
801 hwmp_rann_frame_process(sdata
, mgmt
, elems
.rann
);
805 * mesh_queue_preq - queue a PREQ to a given destination
807 * @mpath: mesh path to discover
808 * @flags: special attributes of the PREQ to be sent
810 * Locking: the function must be called from within a rcu read lock block.
813 static void mesh_queue_preq(struct mesh_path
*mpath
, u8 flags
)
815 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
816 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
817 struct mesh_preq_queue
*preq_node
;
819 preq_node
= kmalloc(sizeof(struct mesh_preq_queue
), GFP_ATOMIC
);
821 mhwmp_dbg("could not allocate PREQ node");
825 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
826 if (ifmsh
->preq_queue_len
== MAX_PREQ_QUEUE_LEN
) {
827 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
829 if (printk_ratelimit())
830 mhwmp_dbg("PREQ node queue full");
834 memcpy(preq_node
->dst
, mpath
->dst
, ETH_ALEN
);
835 preq_node
->flags
= flags
;
837 list_add_tail(&preq_node
->list
, &ifmsh
->preq_queue
.list
);
838 ++ifmsh
->preq_queue_len
;
839 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
841 if (time_after(jiffies
, ifmsh
->last_preq
+ min_preq_int_jiff(sdata
)))
842 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
844 else if (time_before(jiffies
, ifmsh
->last_preq
)) {
845 /* avoid long wait if did not send preqs for a long time
846 * and jiffies wrapped around
848 ifmsh
->last_preq
= jiffies
- min_preq_int_jiff(sdata
) - 1;
849 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
851 mod_timer(&ifmsh
->mesh_path_timer
, ifmsh
->last_preq
+
852 min_preq_int_jiff(sdata
));
856 * mesh_path_start_discovery - launch a path discovery from the PREQ queue
858 * @sdata: local mesh subif
860 void mesh_path_start_discovery(struct ieee80211_sub_if_data
*sdata
)
862 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
863 struct mesh_preq_queue
*preq_node
;
864 struct mesh_path
*mpath
;
865 u8 ttl
, target_flags
;
868 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
869 if (!ifmsh
->preq_queue_len
||
870 time_before(jiffies
, ifmsh
->last_preq
+
871 min_preq_int_jiff(sdata
))) {
872 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
876 preq_node
= list_first_entry(&ifmsh
->preq_queue
.list
,
877 struct mesh_preq_queue
, list
);
878 list_del(&preq_node
->list
);
879 --ifmsh
->preq_queue_len
;
880 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
883 mpath
= mesh_path_lookup(preq_node
->dst
, sdata
);
887 spin_lock_bh(&mpath
->state_lock
);
888 if (preq_node
->flags
& PREQ_Q_F_START
) {
889 if (mpath
->flags
& MESH_PATH_RESOLVING
) {
890 spin_unlock_bh(&mpath
->state_lock
);
893 mpath
->flags
&= ~MESH_PATH_RESOLVED
;
894 mpath
->flags
|= MESH_PATH_RESOLVING
;
895 mpath
->discovery_retries
= 0;
896 mpath
->discovery_timeout
= disc_timeout_jiff(sdata
);
898 } else if (!(mpath
->flags
& MESH_PATH_RESOLVING
) ||
899 mpath
->flags
& MESH_PATH_RESOLVED
) {
900 mpath
->flags
&= ~MESH_PATH_RESOLVING
;
901 spin_unlock_bh(&mpath
->state_lock
);
905 ifmsh
->last_preq
= jiffies
;
907 if (time_after(jiffies
, ifmsh
->last_sn_update
+
908 net_traversal_jiffies(sdata
)) ||
909 time_before(jiffies
, ifmsh
->last_sn_update
)) {
911 sdata
->u
.mesh
.last_sn_update
= jiffies
;
913 lifetime
= default_lifetime(sdata
);
914 ttl
= sdata
->u
.mesh
.mshcfg
.element_ttl
;
916 sdata
->u
.mesh
.mshstats
.dropped_frames_ttl
++;
917 spin_unlock_bh(&mpath
->state_lock
);
921 if (preq_node
->flags
& PREQ_Q_F_REFRESH
)
922 target_flags
= MP_F_DO
;
924 target_flags
= MP_F_RF
;
926 spin_unlock_bh(&mpath
->state_lock
);
927 mesh_path_sel_frame_tx(MPATH_PREQ
, 0, sdata
->vif
.addr
,
928 cpu_to_le32(ifmsh
->sn
), target_flags
, mpath
->dst
,
929 cpu_to_le32(mpath
->sn
), broadcast_addr
, 0,
930 ttl
, cpu_to_le32(lifetime
), 0,
931 cpu_to_le32(ifmsh
->preq_id
++), sdata
);
932 mod_timer(&mpath
->timer
, jiffies
+ mpath
->discovery_timeout
);
940 * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
942 * @skb: 802.11 frame to be sent
943 * @sdata: network subif the frame will be sent through
945 * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
946 * found, the function will start a path discovery and queue the frame so it is
947 * sent when the path is resolved. This means the caller must not free the skb
950 int mesh_nexthop_lookup(struct sk_buff
*skb
,
951 struct ieee80211_sub_if_data
*sdata
)
953 struct sk_buff
*skb_to_free
= NULL
;
954 struct mesh_path
*mpath
;
955 struct sta_info
*next_hop
;
956 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
957 u8
*target_addr
= hdr
->addr3
;
961 mpath
= mesh_path_lookup(target_addr
, sdata
);
964 mesh_path_add(target_addr
, sdata
);
965 mpath
= mesh_path_lookup(target_addr
, sdata
);
967 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
973 if (mpath
->flags
& MESH_PATH_ACTIVE
) {
974 if (time_after(jiffies
,
976 msecs_to_jiffies(sdata
->u
.mesh
.mshcfg
.path_refresh_time
)) &&
977 !memcmp(sdata
->vif
.addr
, hdr
->addr4
, ETH_ALEN
) &&
978 !(mpath
->flags
& MESH_PATH_RESOLVING
) &&
979 !(mpath
->flags
& MESH_PATH_FIXED
)) {
980 mesh_queue_preq(mpath
,
981 PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
983 next_hop
= rcu_dereference(mpath
->next_hop
);
985 memcpy(hdr
->addr1
, next_hop
->sta
.addr
, ETH_ALEN
);
989 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
990 if (!(mpath
->flags
& MESH_PATH_RESOLVING
)) {
991 /* Start discovery only if it is not running yet */
992 mesh_queue_preq(mpath
, PREQ_Q_F_START
);
995 if (skb_queue_len(&mpath
->frame_queue
) >=
996 MESH_FRAME_QUEUE_LEN
)
997 skb_to_free
= skb_dequeue(&mpath
->frame_queue
);
999 info
->flags
|= IEEE80211_TX_INTFL_NEED_TXPROCESSING
;
1000 skb_queue_tail(&mpath
->frame_queue
, skb
);
1002 mesh_path_discard_frame(skb_to_free
, sdata
);
1011 void mesh_path_timer(unsigned long data
)
1013 struct mesh_path
*mpath
= (void *) data
;
1014 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
1017 if (sdata
->local
->quiescing
)
1020 spin_lock_bh(&mpath
->state_lock
);
1021 if (mpath
->flags
& MESH_PATH_RESOLVED
||
1022 (!(mpath
->flags
& MESH_PATH_RESOLVING
))) {
1023 mpath
->flags
&= ~(MESH_PATH_RESOLVING
| MESH_PATH_RESOLVED
);
1024 spin_unlock_bh(&mpath
->state_lock
);
1025 } else if (mpath
->discovery_retries
< max_preq_retries(sdata
)) {
1026 ++mpath
->discovery_retries
;
1027 mpath
->discovery_timeout
*= 2;
1028 spin_unlock_bh(&mpath
->state_lock
);
1029 mesh_queue_preq(mpath
, 0);
1032 mpath
->exp_time
= jiffies
;
1033 spin_unlock_bh(&mpath
->state_lock
);
1034 if (!mpath
->is_gate
&& mesh_gate_num(sdata
) > 0) {
1035 ret
= mesh_path_send_to_gates(mpath
);
1037 mhwmp_dbg("no gate was reachable");
1039 mesh_path_flush_pending(mpath
);
1044 mesh_path_tx_root_frame(struct ieee80211_sub_if_data
*sdata
)
1046 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
1047 u32 interval
= ifmsh
->mshcfg
.dot11MeshHWMPRannInterval
;
1050 flags
= (ifmsh
->mshcfg
.dot11MeshGateAnnouncementProtocol
)
1051 ? RANN_FLAG_IS_GATE
: 0;
1052 mesh_path_sel_frame_tx(MPATH_RANN
, flags
, sdata
->vif
.addr
,
1053 cpu_to_le32(++ifmsh
->sn
),
1054 0, NULL
, 0, broadcast_addr
,
1055 0, sdata
->u
.mesh
.mshcfg
.element_ttl
,
1056 cpu_to_le32(interval
), 0, 0, sdata
);