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>
14 #ifdef CONFIG_MAC80211_VERBOSE_MHWMP_DEBUG
15 #define mhwmp_dbg(fmt, args...) \
16 printk(KERN_DEBUG "Mesh HWMP (%s): " fmt "\n", sdata->name, ##args)
18 #define mhwmp_dbg(fmt, args...) do { (void)(0); } while (0)
21 #define TEST_FRAME_LEN 8192
22 #define MAX_METRIC 0xffffffff
25 /* Number of frames buffered per destination for unresolved destinations */
26 #define MESH_FRAME_QUEUE_LEN 10
27 #define MAX_PREQ_QUEUE_LEN 64
29 /* Destination only */
31 /* Reply and forward */
33 /* Unknown Sequence Number */
35 /* Reason code Present */
36 #define MP_F_RCODE 0x02
38 static void mesh_queue_preq(struct mesh_path
*, u8
);
40 static inline u32
u32_field_get(u8
*preq_elem
, int offset
, bool ae
)
44 return get_unaligned_le32(preq_elem
+ offset
);
47 static inline u32
u16_field_get(u8
*preq_elem
, int offset
, bool ae
)
51 return get_unaligned_le16(preq_elem
+ offset
);
54 /* HWMP IE processing macros */
56 #define AE_F_SET(x) (*x & AE_F)
57 #define PREQ_IE_FLAGS(x) (*(x))
58 #define PREQ_IE_HOPCOUNT(x) (*(x + 1))
59 #define PREQ_IE_TTL(x) (*(x + 2))
60 #define PREQ_IE_PREQ_ID(x) u32_field_get(x, 3, 0)
61 #define PREQ_IE_ORIG_ADDR(x) (x + 7)
62 #define PREQ_IE_ORIG_SN(x) u32_field_get(x, 13, 0)
63 #define PREQ_IE_LIFETIME(x) u32_field_get(x, 17, AE_F_SET(x))
64 #define PREQ_IE_METRIC(x) u32_field_get(x, 21, AE_F_SET(x))
65 #define PREQ_IE_TARGET_F(x) (*(AE_F_SET(x) ? x + 32 : x + 26))
66 #define PREQ_IE_TARGET_ADDR(x) (AE_F_SET(x) ? x + 33 : x + 27)
67 #define PREQ_IE_TARGET_SN(x) u32_field_get(x, 33, AE_F_SET(x))
70 #define PREP_IE_FLAGS(x) PREQ_IE_FLAGS(x)
71 #define PREP_IE_HOPCOUNT(x) PREQ_IE_HOPCOUNT(x)
72 #define PREP_IE_TTL(x) PREQ_IE_TTL(x)
73 #define PREP_IE_ORIG_ADDR(x) (AE_F_SET(x) ? x + 27 : x + 21)
74 #define PREP_IE_ORIG_SN(x) u32_field_get(x, 27, AE_F_SET(x))
75 #define PREP_IE_LIFETIME(x) u32_field_get(x, 13, AE_F_SET(x))
76 #define PREP_IE_METRIC(x) u32_field_get(x, 17, AE_F_SET(x))
77 #define PREP_IE_TARGET_ADDR(x) (x + 3)
78 #define PREP_IE_TARGET_SN(x) u32_field_get(x, 9, 0)
80 #define PERR_IE_TTL(x) (*(x))
81 #define PERR_IE_TARGET_FLAGS(x) (*(x + 2))
82 #define PERR_IE_TARGET_ADDR(x) (x + 3)
83 #define PERR_IE_TARGET_SN(x) u32_field_get(x, 9, 0)
84 #define PERR_IE_TARGET_RCODE(x) u16_field_get(x, 13, 0)
86 #define MSEC_TO_TU(x) (x*1000/1024)
87 #define SN_GT(x, y) ((long) (y) - (long) (x) < 0)
88 #define SN_LT(x, y) ((long) (x) - (long) (y) < 0)
90 #define net_traversal_jiffies(s) \
91 msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPnetDiameterTraversalTime)
92 #define default_lifetime(s) \
93 MSEC_TO_TU(s->u.mesh.mshcfg.dot11MeshHWMPactivePathTimeout)
94 #define min_preq_int_jiff(s) \
95 (msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPpreqMinInterval))
96 #define max_preq_retries(s) (s->u.mesh.mshcfg.dot11MeshHWMPmaxPREQretries)
97 #define disc_timeout_jiff(s) \
98 msecs_to_jiffies(sdata->u.mesh.mshcfg.min_discovery_timeout)
100 enum mpath_frame_type
{
107 static const u8 broadcast_addr
[ETH_ALEN
] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
109 static int mesh_path_sel_frame_tx(enum mpath_frame_type action
, u8 flags
,
110 u8
*orig_addr
, __le32 orig_sn
, u8 target_flags
, u8
*target
,
111 __le32 target_sn
, const u8
*da
, u8 hop_count
, u8 ttl
,
112 __le32 lifetime
, __le32 metric
, __le32 preq_id
,
113 struct ieee80211_sub_if_data
*sdata
)
115 struct ieee80211_local
*local
= sdata
->local
;
116 struct sk_buff
*skb
= dev_alloc_skb(local
->hw
.extra_tx_headroom
+ 400);
117 struct ieee80211_mgmt
*mgmt
;
123 skb_reserve(skb
, local
->hw
.extra_tx_headroom
);
124 /* 25 is the size of the common mgmt part (24) plus the size of the
125 * common action part (1)
127 mgmt
= (struct ieee80211_mgmt
*)
128 skb_put(skb
, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
129 memset(mgmt
, 0, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
130 mgmt
->frame_control
= cpu_to_le16(IEEE80211_FTYPE_MGMT
|
131 IEEE80211_STYPE_ACTION
);
133 memcpy(mgmt
->da
, da
, ETH_ALEN
);
134 memcpy(mgmt
->sa
, sdata
->vif
.addr
, ETH_ALEN
);
136 memcpy(mgmt
->bssid
, sdata
->vif
.addr
, ETH_ALEN
);
137 mgmt
->u
.action
.category
= WLAN_CATEGORY_MESH_ACTION
;
138 mgmt
->u
.action
.u
.mesh_action
.action_code
=
139 WLAN_MESH_ACTION_HWMP_PATH_SELECTION
;
143 mhwmp_dbg("sending PREQ to %pM", target
);
145 pos
= skb_put(skb
, 2 + ie_len
);
146 *pos
++ = WLAN_EID_PREQ
;
149 mhwmp_dbg("sending PREP to %pM", target
);
151 pos
= skb_put(skb
, 2 + ie_len
);
152 *pos
++ = WLAN_EID_PREP
;
155 mhwmp_dbg("sending RANN from %pM", orig_addr
);
156 ie_len
= sizeof(struct ieee80211_rann_ie
);
157 pos
= skb_put(skb
, 2 + ie_len
);
158 *pos
++ = WLAN_EID_RANN
;
169 if (action
== MPATH_PREP
) {
170 memcpy(pos
, target
, ETH_ALEN
);
172 memcpy(pos
, &target_sn
, 4);
175 if (action
== MPATH_PREQ
) {
176 memcpy(pos
, &preq_id
, 4);
179 memcpy(pos
, orig_addr
, ETH_ALEN
);
181 memcpy(pos
, &orig_sn
, 4);
184 memcpy(pos
, &lifetime
, 4); /* interval for RANN */
186 memcpy(pos
, &metric
, 4);
188 if (action
== MPATH_PREQ
) {
189 *pos
++ = 1; /* destination count */
190 *pos
++ = target_flags
;
191 memcpy(pos
, target
, ETH_ALEN
);
193 memcpy(pos
, &target_sn
, 4);
195 } else if (action
== MPATH_PREP
) {
196 memcpy(pos
, orig_addr
, ETH_ALEN
);
198 memcpy(pos
, &orig_sn
, 4);
202 ieee80211_tx_skb(sdata
, skb
);
207 /* Headroom is not adjusted. Caller should ensure that skb has sufficient
208 * headroom in case the frame is encrypted. */
209 static void prepare_frame_for_deferred_tx(struct ieee80211_sub_if_data
*sdata
,
212 struct ieee80211_local
*local
= sdata
->local
;
213 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
215 skb_set_mac_header(skb
, 0);
216 skb_set_network_header(skb
, 0);
217 skb_set_transport_header(skb
, 0);
219 /* Send all internal mgmt frames on VO. Accordingly set TID to 7. */
220 skb_set_queue_mapping(skb
, IEEE80211_AC_VO
);
223 info
->control
.vif
= &sdata
->vif
;
224 ieee80211_set_qos_hdr(local
, skb
);
228 * mesh_send_path error - Sends a PERR mesh management frame
230 * @target: broken destination
231 * @target_sn: SN of the broken destination
232 * @target_rcode: reason code for this PERR
233 * @ra: node this frame is addressed to
235 * Note: This function may be called with driver locks taken that the driver
236 * also acquires in the TX path. To avoid a deadlock we don't transmit the
237 * frame directly but add it to the pending queue instead.
239 int mesh_path_error_tx(u8 ttl
, u8
*target
, __le32 target_sn
,
240 __le16 target_rcode
, const u8
*ra
,
241 struct ieee80211_sub_if_data
*sdata
)
243 struct ieee80211_local
*local
= sdata
->local
;
244 struct sk_buff
*skb
= dev_alloc_skb(local
->hw
.extra_tx_headroom
+ 400);
245 struct ieee80211_mgmt
*mgmt
;
251 skb_reserve(skb
, local
->tx_headroom
+ local
->hw
.extra_tx_headroom
);
252 /* 25 is the size of the common mgmt part (24) plus the size of the
253 * common action part (1)
255 mgmt
= (struct ieee80211_mgmt
*)
256 skb_put(skb
, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
257 memset(mgmt
, 0, 25 + sizeof(mgmt
->u
.action
.u
.mesh_action
));
258 mgmt
->frame_control
= cpu_to_le16(IEEE80211_FTYPE_MGMT
|
259 IEEE80211_STYPE_ACTION
);
261 memcpy(mgmt
->da
, ra
, ETH_ALEN
);
262 memcpy(mgmt
->sa
, sdata
->vif
.addr
, ETH_ALEN
);
264 memcpy(mgmt
->bssid
, sdata
->vif
.addr
, ETH_ALEN
);
265 mgmt
->u
.action
.category
= WLAN_CATEGORY_MESH_ACTION
;
266 mgmt
->u
.action
.u
.mesh_action
.action_code
=
267 WLAN_MESH_ACTION_HWMP_PATH_SELECTION
;
269 pos
= skb_put(skb
, 2 + ie_len
);
270 *pos
++ = WLAN_EID_PERR
;
274 /* number of destinations */
277 * flags bit, bit 1 is unset if we know the sequence number and
278 * bit 2 is set if we have a reason code
286 memcpy(pos
, target
, ETH_ALEN
);
288 memcpy(pos
, &target_sn
, 4);
290 memcpy(pos
, &target_rcode
, 2);
292 /* see note in function header */
293 prepare_frame_for_deferred_tx(sdata
, skb
);
294 ieee80211_add_pending_skb(local
, skb
);
298 void ieee80211s_update_metric(struct ieee80211_local
*local
,
299 struct sta_info
*stainfo
, struct sk_buff
*skb
)
301 struct ieee80211_tx_info
*txinfo
= IEEE80211_SKB_CB(skb
);
302 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
305 if (!ieee80211_is_data(hdr
->frame_control
))
308 failed
= !(txinfo
->flags
& IEEE80211_TX_STAT_ACK
);
310 /* moving average, scaled to 100 */
311 stainfo
->fail_avg
= ((80 * stainfo
->fail_avg
+ 5) / 100 + 20 * failed
);
312 if (stainfo
->fail_avg
> 95)
313 mesh_plink_broken(stainfo
);
316 static u32
airtime_link_metric_get(struct ieee80211_local
*local
,
317 struct sta_info
*sta
)
319 struct ieee80211_supported_band
*sband
;
320 /* This should be adjusted for each device */
321 int device_constant
= 1 << ARITH_SHIFT
;
322 int test_frame_len
= TEST_FRAME_LEN
<< ARITH_SHIFT
;
323 int s_unit
= 1 << ARITH_SHIFT
;
325 u32 tx_time
, estimated_retx
;
328 sband
= local
->hw
.wiphy
->bands
[local
->hw
.conf
.channel
->band
];
330 if (sta
->fail_avg
>= 100)
333 if (sta
->last_tx_rate
.flags
& IEEE80211_TX_RC_MCS
)
336 err
= (sta
->fail_avg
<< ARITH_SHIFT
) / 100;
338 /* bitrate is in units of 100 Kbps, while we need rate in units of
339 * 1Mbps. This will be corrected on tx_time computation.
341 rate
= sband
->bitrates
[sta
->last_tx_rate
.idx
].bitrate
;
342 tx_time
= (device_constant
+ 10 * test_frame_len
/ rate
);
343 estimated_retx
= ((1 << (2 * ARITH_SHIFT
)) / (s_unit
- err
));
344 result
= (tx_time
* estimated_retx
) >> (2 * ARITH_SHIFT
) ;
349 * hwmp_route_info_get - Update routing info to originator and transmitter
351 * @sdata: local mesh subif
352 * @mgmt: mesh management frame
353 * @hwmp_ie: hwmp information element (PREP or PREQ)
355 * This function updates the path routing information to the originator and the
356 * transmitter of a HWMP PREQ or PREP frame.
358 * Returns: metric to frame originator or 0 if the frame should not be further
361 * Notes: this function is the only place (besides user-provided info) where
362 * path routing information is updated.
364 static u32
hwmp_route_info_get(struct ieee80211_sub_if_data
*sdata
,
365 struct ieee80211_mgmt
*mgmt
,
366 u8
*hwmp_ie
, enum mpath_frame_type action
)
368 struct ieee80211_local
*local
= sdata
->local
;
369 struct mesh_path
*mpath
;
370 struct sta_info
*sta
;
373 u32 orig_sn
, orig_metric
;
374 unsigned long orig_lifetime
, exp_time
;
375 u32 last_hop_metric
, new_metric
;
379 sta
= sta_info_get(sdata
, mgmt
->sa
);
385 last_hop_metric
= airtime_link_metric_get(local
, sta
);
386 /* Update and check originator routing info */
391 orig_addr
= PREQ_IE_ORIG_ADDR(hwmp_ie
);
392 orig_sn
= PREQ_IE_ORIG_SN(hwmp_ie
);
393 orig_lifetime
= PREQ_IE_LIFETIME(hwmp_ie
);
394 orig_metric
= PREQ_IE_METRIC(hwmp_ie
);
397 /* Originator here refers to the MP that was the destination in
398 * the Path Request. The draft refers to that MP as the
399 * destination address, even though usually it is the origin of
400 * the PREP frame. We divert from the nomenclature in the draft
401 * so that we can easily use a single function to gather path
402 * information from both PREQ and PREP frames.
404 orig_addr
= PREP_IE_ORIG_ADDR(hwmp_ie
);
405 orig_sn
= PREP_IE_ORIG_SN(hwmp_ie
);
406 orig_lifetime
= PREP_IE_LIFETIME(hwmp_ie
);
407 orig_metric
= PREP_IE_METRIC(hwmp_ie
);
413 new_metric
= orig_metric
+ last_hop_metric
;
414 if (new_metric
< orig_metric
)
415 new_metric
= MAX_METRIC
;
416 exp_time
= TU_TO_EXP_TIME(orig_lifetime
);
418 if (memcmp(orig_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0) {
419 /* This MP is the originator, we are not interested in this
420 * frame, except for updating transmitter's path info.
425 mpath
= mesh_path_lookup(orig_addr
, sdata
);
427 spin_lock_bh(&mpath
->state_lock
);
428 if (mpath
->flags
& MESH_PATH_FIXED
)
430 else if ((mpath
->flags
& MESH_PATH_ACTIVE
) &&
431 (mpath
->flags
& MESH_PATH_SN_VALID
)) {
432 if (SN_GT(mpath
->sn
, orig_sn
) ||
433 (mpath
->sn
== orig_sn
&&
434 new_metric
>= mpath
->metric
)) {
440 mesh_path_add(orig_addr
, sdata
);
441 mpath
= mesh_path_lookup(orig_addr
, sdata
);
446 spin_lock_bh(&mpath
->state_lock
);
450 mesh_path_assign_nexthop(mpath
, sta
);
451 mpath
->flags
|= MESH_PATH_SN_VALID
;
452 mpath
->metric
= new_metric
;
454 mpath
->exp_time
= time_after(mpath
->exp_time
, exp_time
)
455 ? mpath
->exp_time
: exp_time
;
456 mesh_path_activate(mpath
);
457 spin_unlock_bh(&mpath
->state_lock
);
458 mesh_path_tx_pending(mpath
);
459 /* draft says preq_id should be saved to, but there does
460 * not seem to be any use for it, skipping by now
463 spin_unlock_bh(&mpath
->state_lock
);
466 /* Update and check transmitter routing info */
468 if (memcmp(orig_addr
, ta
, ETH_ALEN
) == 0)
473 mpath
= mesh_path_lookup(ta
, sdata
);
475 spin_lock_bh(&mpath
->state_lock
);
476 if ((mpath
->flags
& MESH_PATH_FIXED
) ||
477 ((mpath
->flags
& MESH_PATH_ACTIVE
) &&
478 (last_hop_metric
> mpath
->metric
)))
481 mesh_path_add(ta
, sdata
);
482 mpath
= mesh_path_lookup(ta
, sdata
);
487 spin_lock_bh(&mpath
->state_lock
);
491 mesh_path_assign_nexthop(mpath
, sta
);
492 mpath
->metric
= last_hop_metric
;
493 mpath
->exp_time
= time_after(mpath
->exp_time
, exp_time
)
494 ? mpath
->exp_time
: exp_time
;
495 mesh_path_activate(mpath
);
496 spin_unlock_bh(&mpath
->state_lock
);
497 mesh_path_tx_pending(mpath
);
499 spin_unlock_bh(&mpath
->state_lock
);
504 return process
? new_metric
: 0;
507 static void hwmp_preq_frame_process(struct ieee80211_sub_if_data
*sdata
,
508 struct ieee80211_mgmt
*mgmt
,
509 u8
*preq_elem
, u32 metric
)
511 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
512 struct mesh_path
*mpath
;
513 u8
*target_addr
, *orig_addr
;
514 u8 target_flags
, ttl
;
515 u32 orig_sn
, target_sn
, lifetime
;
519 /* Update target SN, if present */
520 target_addr
= PREQ_IE_TARGET_ADDR(preq_elem
);
521 orig_addr
= PREQ_IE_ORIG_ADDR(preq_elem
);
522 target_sn
= PREQ_IE_TARGET_SN(preq_elem
);
523 orig_sn
= PREQ_IE_ORIG_SN(preq_elem
);
524 target_flags
= PREQ_IE_TARGET_F(preq_elem
);
526 mhwmp_dbg("received PREQ from %pM", orig_addr
);
528 if (memcmp(target_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0) {
529 mhwmp_dbg("PREQ is for us");
533 if (time_after(jiffies
, ifmsh
->last_sn_update
+
534 net_traversal_jiffies(sdata
)) ||
535 time_before(jiffies
, ifmsh
->last_sn_update
)) {
536 target_sn
= ++ifmsh
->sn
;
537 ifmsh
->last_sn_update
= jiffies
;
541 mpath
= mesh_path_lookup(target_addr
, sdata
);
543 if ((!(mpath
->flags
& MESH_PATH_SN_VALID
)) ||
544 SN_LT(mpath
->sn
, target_sn
)) {
545 mpath
->sn
= target_sn
;
546 mpath
->flags
|= MESH_PATH_SN_VALID
;
547 } else if ((!(target_flags
& MP_F_DO
)) &&
548 (mpath
->flags
& MESH_PATH_ACTIVE
)) {
550 metric
= mpath
->metric
;
551 target_sn
= mpath
->sn
;
552 if (target_flags
& MP_F_RF
)
553 target_flags
|= MP_F_DO
;
562 lifetime
= PREQ_IE_LIFETIME(preq_elem
);
563 ttl
= ifmsh
->mshcfg
.element_ttl
;
565 mhwmp_dbg("replying to the PREQ");
566 mesh_path_sel_frame_tx(MPATH_PREP
, 0, target_addr
,
567 cpu_to_le32(target_sn
), 0, orig_addr
,
568 cpu_to_le32(orig_sn
), mgmt
->sa
, 0, ttl
,
569 cpu_to_le32(lifetime
), cpu_to_le32(metric
),
572 ifmsh
->mshstats
.dropped_frames_ttl
++;
579 ttl
= PREQ_IE_TTL(preq_elem
);
580 lifetime
= PREQ_IE_LIFETIME(preq_elem
);
582 ifmsh
->mshstats
.dropped_frames_ttl
++;
585 mhwmp_dbg("forwarding the PREQ from %pM", orig_addr
);
587 flags
= PREQ_IE_FLAGS(preq_elem
);
588 preq_id
= PREQ_IE_PREQ_ID(preq_elem
);
589 hopcount
= PREQ_IE_HOPCOUNT(preq_elem
) + 1;
590 mesh_path_sel_frame_tx(MPATH_PREQ
, flags
, orig_addr
,
591 cpu_to_le32(orig_sn
), target_flags
, target_addr
,
592 cpu_to_le32(target_sn
), broadcast_addr
,
593 hopcount
, ttl
, cpu_to_le32(lifetime
),
594 cpu_to_le32(metric
), cpu_to_le32(preq_id
),
596 ifmsh
->mshstats
.fwded_mcast
++;
597 ifmsh
->mshstats
.fwded_frames
++;
602 static inline struct sta_info
*
603 next_hop_deref_protected(struct mesh_path
*mpath
)
605 return rcu_dereference_protected(mpath
->next_hop
,
606 lockdep_is_held(&mpath
->state_lock
));
610 static void hwmp_prep_frame_process(struct ieee80211_sub_if_data
*sdata
,
611 struct ieee80211_mgmt
*mgmt
,
612 u8
*prep_elem
, u32 metric
)
614 struct mesh_path
*mpath
;
615 u8
*target_addr
, *orig_addr
;
616 u8 ttl
, hopcount
, flags
;
617 u8 next_hop
[ETH_ALEN
];
618 u32 target_sn
, orig_sn
, lifetime
;
620 mhwmp_dbg("received PREP from %pM", PREP_IE_ORIG_ADDR(prep_elem
));
622 /* Note that we divert from the draft nomenclature and denominate
623 * destination to what the draft refers to as origininator. So in this
624 * function destnation refers to the final destination of the PREP,
625 * which corresponds with the originator of the PREQ which this PREP
628 target_addr
= PREP_IE_TARGET_ADDR(prep_elem
);
629 if (memcmp(target_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
630 /* destination, no forwarding required */
633 ttl
= PREP_IE_TTL(prep_elem
);
635 sdata
->u
.mesh
.mshstats
.dropped_frames_ttl
++;
640 mpath
= mesh_path_lookup(target_addr
, sdata
);
642 spin_lock_bh(&mpath
->state_lock
);
645 if (!(mpath
->flags
& MESH_PATH_ACTIVE
)) {
646 spin_unlock_bh(&mpath
->state_lock
);
649 memcpy(next_hop
, next_hop_deref_protected(mpath
)->sta
.addr
, ETH_ALEN
);
650 spin_unlock_bh(&mpath
->state_lock
);
652 flags
= PREP_IE_FLAGS(prep_elem
);
653 lifetime
= PREP_IE_LIFETIME(prep_elem
);
654 hopcount
= PREP_IE_HOPCOUNT(prep_elem
) + 1;
655 orig_addr
= PREP_IE_ORIG_ADDR(prep_elem
);
656 target_sn
= PREP_IE_TARGET_SN(prep_elem
);
657 orig_sn
= PREP_IE_ORIG_SN(prep_elem
);
659 mesh_path_sel_frame_tx(MPATH_PREP
, flags
, orig_addr
,
660 cpu_to_le32(orig_sn
), 0, target_addr
,
661 cpu_to_le32(target_sn
), next_hop
, hopcount
,
662 ttl
, cpu_to_le32(lifetime
), cpu_to_le32(metric
),
666 sdata
->u
.mesh
.mshstats
.fwded_unicast
++;
667 sdata
->u
.mesh
.mshstats
.fwded_frames
++;
672 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
675 static void hwmp_perr_frame_process(struct ieee80211_sub_if_data
*sdata
,
676 struct ieee80211_mgmt
*mgmt
, u8
*perr_elem
)
678 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
679 struct mesh_path
*mpath
;
681 u8
*ta
, *target_addr
;
686 ttl
= PERR_IE_TTL(perr_elem
);
688 ifmsh
->mshstats
.dropped_frames_ttl
++;
692 target_addr
= PERR_IE_TARGET_ADDR(perr_elem
);
693 target_sn
= PERR_IE_TARGET_SN(perr_elem
);
694 target_rcode
= PERR_IE_TARGET_RCODE(perr_elem
);
697 mpath
= mesh_path_lookup(target_addr
, sdata
);
699 spin_lock_bh(&mpath
->state_lock
);
700 if (mpath
->flags
& MESH_PATH_ACTIVE
&&
701 memcmp(ta
, next_hop_deref_protected(mpath
)->sta
.addr
,
703 (!(mpath
->flags
& MESH_PATH_SN_VALID
) ||
704 SN_GT(target_sn
, mpath
->sn
))) {
705 mpath
->flags
&= ~MESH_PATH_ACTIVE
;
706 mpath
->sn
= target_sn
;
707 spin_unlock_bh(&mpath
->state_lock
);
708 mesh_path_error_tx(ttl
, target_addr
, cpu_to_le32(target_sn
),
709 cpu_to_le16(target_rcode
),
710 broadcast_addr
, sdata
);
712 spin_unlock_bh(&mpath
->state_lock
);
717 static void hwmp_rann_frame_process(struct ieee80211_sub_if_data
*sdata
,
718 struct ieee80211_mgmt
*mgmt
,
719 struct ieee80211_rann_ie
*rann
)
721 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
722 struct mesh_path
*mpath
;
723 u8 ttl
, flags
, hopcount
;
726 u32 interval
= ifmsh
->mshcfg
.dot11MeshHWMPRannInterval
;
729 ttl
= rann
->rann_ttl
;
731 ifmsh
->mshstats
.dropped_frames_ttl
++;
735 flags
= rann
->rann_flags
;
736 root_is_gate
= !!(flags
& RANN_FLAG_IS_GATE
);
737 orig_addr
= rann
->rann_addr
;
738 orig_sn
= rann
->rann_seq
;
739 hopcount
= rann
->rann_hopcount
;
741 metric
= rann
->rann_metric
;
743 /* Ignore our own RANNs */
744 if (memcmp(orig_addr
, sdata
->vif
.addr
, ETH_ALEN
) == 0)
747 mhwmp_dbg("received RANN from %pM (is_gate=%d)", orig_addr
,
751 mpath
= mesh_path_lookup(orig_addr
, sdata
);
753 mesh_path_add(orig_addr
, sdata
);
754 mpath
= mesh_path_lookup(orig_addr
, sdata
);
757 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
762 if ((!(mpath
->flags
& (MESH_PATH_ACTIVE
| MESH_PATH_RESOLVING
)) ||
763 time_after(jiffies
, mpath
->exp_time
- 1*HZ
)) &&
764 !(mpath
->flags
& MESH_PATH_FIXED
)) {
765 mhwmp_dbg("%s time to refresh root mpath %pM", sdata
->name
,
767 mesh_queue_preq(mpath
, PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
770 if (mpath
->sn
< orig_sn
) {
771 mesh_path_sel_frame_tx(MPATH_RANN
, flags
, orig_addr
,
772 cpu_to_le32(orig_sn
),
773 0, NULL
, 0, broadcast_addr
,
774 hopcount
, ttl
, cpu_to_le32(interval
),
775 cpu_to_le32(metric
+ mpath
->metric
),
780 mesh_path_add_gate(mpath
);
786 void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data
*sdata
,
787 struct ieee80211_mgmt
*mgmt
,
790 struct ieee802_11_elems elems
;
794 /* need action_code */
795 if (len
< IEEE80211_MIN_ACTION_SIZE
+ 1)
798 baselen
= (u8
*) mgmt
->u
.action
.u
.mesh_action
.variable
- (u8
*) mgmt
;
799 ieee802_11_parse_elems(mgmt
->u
.action
.u
.mesh_action
.variable
,
800 len
- baselen
, &elems
);
803 if (elems
.preq_len
!= 37)
804 /* Right now we support just 1 destination and no AE */
806 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.preq
,
809 hwmp_preq_frame_process(sdata
, mgmt
, elems
.preq
,
813 if (elems
.prep_len
!= 31)
814 /* Right now we support no AE */
816 last_hop_metric
= hwmp_route_info_get(sdata
, mgmt
, elems
.prep
,
819 hwmp_prep_frame_process(sdata
, mgmt
, elems
.prep
,
823 if (elems
.perr_len
!= 15)
824 /* Right now we support only one destination per PERR */
826 hwmp_perr_frame_process(sdata
, mgmt
, elems
.perr
);
829 hwmp_rann_frame_process(sdata
, mgmt
, elems
.rann
);
833 * mesh_queue_preq - queue a PREQ to a given destination
835 * @mpath: mesh path to discover
836 * @flags: special attributes of the PREQ to be sent
838 * Locking: the function must be called from within a rcu read lock block.
841 static void mesh_queue_preq(struct mesh_path
*mpath
, u8 flags
)
843 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
844 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
845 struct mesh_preq_queue
*preq_node
;
847 preq_node
= kmalloc(sizeof(struct mesh_preq_queue
), GFP_ATOMIC
);
849 mhwmp_dbg("could not allocate PREQ node");
853 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
854 if (ifmsh
->preq_queue_len
== MAX_PREQ_QUEUE_LEN
) {
855 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
857 if (printk_ratelimit())
858 mhwmp_dbg("PREQ node queue full");
862 memcpy(preq_node
->dst
, mpath
->dst
, ETH_ALEN
);
863 preq_node
->flags
= flags
;
865 list_add_tail(&preq_node
->list
, &ifmsh
->preq_queue
.list
);
866 ++ifmsh
->preq_queue_len
;
867 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
869 if (time_after(jiffies
, ifmsh
->last_preq
+ min_preq_int_jiff(sdata
)))
870 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
872 else if (time_before(jiffies
, ifmsh
->last_preq
)) {
873 /* avoid long wait if did not send preqs for a long time
874 * and jiffies wrapped around
876 ifmsh
->last_preq
= jiffies
- min_preq_int_jiff(sdata
) - 1;
877 ieee80211_queue_work(&sdata
->local
->hw
, &sdata
->work
);
879 mod_timer(&ifmsh
->mesh_path_timer
, ifmsh
->last_preq
+
880 min_preq_int_jiff(sdata
));
884 * mesh_path_start_discovery - launch a path discovery from the PREQ queue
886 * @sdata: local mesh subif
888 void mesh_path_start_discovery(struct ieee80211_sub_if_data
*sdata
)
890 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
891 struct mesh_preq_queue
*preq_node
;
892 struct mesh_path
*mpath
;
893 u8 ttl
, target_flags
;
896 spin_lock_bh(&ifmsh
->mesh_preq_queue_lock
);
897 if (!ifmsh
->preq_queue_len
||
898 time_before(jiffies
, ifmsh
->last_preq
+
899 min_preq_int_jiff(sdata
))) {
900 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
904 preq_node
= list_first_entry(&ifmsh
->preq_queue
.list
,
905 struct mesh_preq_queue
, list
);
906 list_del(&preq_node
->list
);
907 --ifmsh
->preq_queue_len
;
908 spin_unlock_bh(&ifmsh
->mesh_preq_queue_lock
);
911 mpath
= mesh_path_lookup(preq_node
->dst
, sdata
);
915 spin_lock_bh(&mpath
->state_lock
);
916 if (preq_node
->flags
& PREQ_Q_F_START
) {
917 if (mpath
->flags
& MESH_PATH_RESOLVING
) {
918 spin_unlock_bh(&mpath
->state_lock
);
921 mpath
->flags
&= ~MESH_PATH_RESOLVED
;
922 mpath
->flags
|= MESH_PATH_RESOLVING
;
923 mpath
->discovery_retries
= 0;
924 mpath
->discovery_timeout
= disc_timeout_jiff(sdata
);
926 } else if (!(mpath
->flags
& MESH_PATH_RESOLVING
) ||
927 mpath
->flags
& MESH_PATH_RESOLVED
) {
928 mpath
->flags
&= ~MESH_PATH_RESOLVING
;
929 spin_unlock_bh(&mpath
->state_lock
);
933 ifmsh
->last_preq
= jiffies
;
935 if (time_after(jiffies
, ifmsh
->last_sn_update
+
936 net_traversal_jiffies(sdata
)) ||
937 time_before(jiffies
, ifmsh
->last_sn_update
)) {
939 sdata
->u
.mesh
.last_sn_update
= jiffies
;
941 lifetime
= default_lifetime(sdata
);
942 ttl
= sdata
->u
.mesh
.mshcfg
.element_ttl
;
944 sdata
->u
.mesh
.mshstats
.dropped_frames_ttl
++;
945 spin_unlock_bh(&mpath
->state_lock
);
949 if (preq_node
->flags
& PREQ_Q_F_REFRESH
)
950 target_flags
= MP_F_DO
;
952 target_flags
= MP_F_RF
;
954 spin_unlock_bh(&mpath
->state_lock
);
955 mesh_path_sel_frame_tx(MPATH_PREQ
, 0, sdata
->vif
.addr
,
956 cpu_to_le32(ifmsh
->sn
), target_flags
, mpath
->dst
,
957 cpu_to_le32(mpath
->sn
), broadcast_addr
, 0,
958 ttl
, cpu_to_le32(lifetime
), 0,
959 cpu_to_le32(ifmsh
->preq_id
++), sdata
);
960 mod_timer(&mpath
->timer
, jiffies
+ mpath
->discovery_timeout
);
968 * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
970 * @skb: 802.11 frame to be sent
971 * @sdata: network subif the frame will be sent through
973 * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
974 * found, the function will start a path discovery and queue the frame so it is
975 * sent when the path is resolved. This means the caller must not free the skb
978 int mesh_nexthop_lookup(struct sk_buff
*skb
,
979 struct ieee80211_sub_if_data
*sdata
)
981 struct sk_buff
*skb_to_free
= NULL
;
982 struct mesh_path
*mpath
;
983 struct sta_info
*next_hop
;
984 struct ieee80211_hdr
*hdr
= (struct ieee80211_hdr
*) skb
->data
;
985 u8
*target_addr
= hdr
->addr3
;
989 mpath
= mesh_path_lookup(target_addr
, sdata
);
992 mesh_path_add(target_addr
, sdata
);
993 mpath
= mesh_path_lookup(target_addr
, sdata
);
995 sdata
->u
.mesh
.mshstats
.dropped_frames_no_route
++;
1001 if (mpath
->flags
& MESH_PATH_ACTIVE
) {
1002 if (time_after(jiffies
,
1004 msecs_to_jiffies(sdata
->u
.mesh
.mshcfg
.path_refresh_time
)) &&
1005 !memcmp(sdata
->vif
.addr
, hdr
->addr4
, ETH_ALEN
) &&
1006 !(mpath
->flags
& MESH_PATH_RESOLVING
) &&
1007 !(mpath
->flags
& MESH_PATH_FIXED
)) {
1008 mesh_queue_preq(mpath
,
1009 PREQ_Q_F_START
| PREQ_Q_F_REFRESH
);
1011 next_hop
= rcu_dereference(mpath
->next_hop
);
1013 memcpy(hdr
->addr1
, next_hop
->sta
.addr
, ETH_ALEN
);
1017 struct ieee80211_tx_info
*info
= IEEE80211_SKB_CB(skb
);
1018 if (!(mpath
->flags
& MESH_PATH_RESOLVING
)) {
1019 /* Start discovery only if it is not running yet */
1020 mesh_queue_preq(mpath
, PREQ_Q_F_START
);
1023 if (skb_queue_len(&mpath
->frame_queue
) >=
1024 MESH_FRAME_QUEUE_LEN
)
1025 skb_to_free
= skb_dequeue(&mpath
->frame_queue
);
1027 info
->flags
|= IEEE80211_TX_INTFL_NEED_TXPROCESSING
;
1028 skb_queue_tail(&mpath
->frame_queue
, skb
);
1030 mesh_path_discard_frame(skb_to_free
, sdata
);
1039 void mesh_path_timer(unsigned long data
)
1041 struct mesh_path
*mpath
= (void *) data
;
1042 struct ieee80211_sub_if_data
*sdata
= mpath
->sdata
;
1045 if (sdata
->local
->quiescing
)
1048 spin_lock_bh(&mpath
->state_lock
);
1049 if (mpath
->flags
& MESH_PATH_RESOLVED
||
1050 (!(mpath
->flags
& MESH_PATH_RESOLVING
))) {
1051 mpath
->flags
&= ~(MESH_PATH_RESOLVING
| MESH_PATH_RESOLVED
);
1052 spin_unlock_bh(&mpath
->state_lock
);
1053 } else if (mpath
->discovery_retries
< max_preq_retries(sdata
)) {
1054 ++mpath
->discovery_retries
;
1055 mpath
->discovery_timeout
*= 2;
1056 spin_unlock_bh(&mpath
->state_lock
);
1057 mesh_queue_preq(mpath
, 0);
1060 mpath
->exp_time
= jiffies
;
1061 spin_unlock_bh(&mpath
->state_lock
);
1062 if (!mpath
->is_gate
&& mesh_gate_num(sdata
) > 0) {
1063 ret
= mesh_path_send_to_gates(mpath
);
1065 mhwmp_dbg("no gate was reachable");
1067 mesh_path_flush_pending(mpath
);
1072 mesh_path_tx_root_frame(struct ieee80211_sub_if_data
*sdata
)
1074 struct ieee80211_if_mesh
*ifmsh
= &sdata
->u
.mesh
;
1075 u32 interval
= ifmsh
->mshcfg
.dot11MeshHWMPRannInterval
;
1078 flags
= (ifmsh
->mshcfg
.dot11MeshGateAnnouncementProtocol
)
1079 ? RANN_FLAG_IS_GATE
: 0;
1080 mesh_path_sel_frame_tx(MPATH_RANN
, flags
, sdata
->vif
.addr
,
1081 cpu_to_le32(++ifmsh
->sn
),
1082 0, NULL
, 0, broadcast_addr
,
1083 0, sdata
->u
.mesh
.mshcfg
.element_ttl
,
1084 cpu_to_le32(interval
), 0, 0, sdata
);