net/mac80211/mesh_hwmp.c

   1 /*
   2  * Copyright (c) 2008, 2009 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 <linux/slab.h>
  11 #include <linux/etherdevice.h>
  12 #include <asm/unaligned.h>
  13 #include "wme.h"
  14 #include "mesh.h"
  15
  16 #define TEST_FRAME_LEN  8192
  17 #define MAX_METRIC      0xffffffff
  18 #define ARITH_SHIFT     8
  19
  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 /* Unknown Sequence Number */
  27 #define MP_F_USN    0x01
  28 /* Reason code Present */
  29 #define MP_F_RCODE  0x02
  30
  31 static void mesh_queue_preq(struct mesh_path *, u8);
  32
  33 static inline u32 u32_field_get(const u8 *preq_elem, int offset, bool ae)
  34 {
  35         if (ae)
  36                 offset += 6;
  37         return get_unaligned_le32(preq_elem + offset);
  38 }
  39
  40 static inline u32 u16_field_get(const u8 *preq_elem, int offset, bool ae)
  41 {
  42         if (ae)
  43                 offset += 6;
  44         return get_unaligned_le16(preq_elem + offset);
  45 }
  46
  47 /* HWMP IE processing macros */
  48 #define AE_F                    (1<<6)
  49 #define AE_F_SET(x)             (*x & AE_F)
  50 #define PREQ_IE_FLAGS(x)        (*(x))
  51 #define PREQ_IE_HOPCOUNT(x)     (*(x + 1))
  52 #define PREQ_IE_TTL(x)          (*(x + 2))
  53 #define PREQ_IE_PREQ_ID(x)      u32_field_get(x, 3, 0)
  54 #define PREQ_IE_ORIG_ADDR(x)    (x + 7)
  55 #define PREQ_IE_ORIG_SN(x)      u32_field_get(x, 13, 0)
  56 #define PREQ_IE_LIFETIME(x)     u32_field_get(x, 17, AE_F_SET(x))
  57 #define PREQ_IE_METRIC(x)       u32_field_get(x, 21, AE_F_SET(x))
  58 #define PREQ_IE_TARGET_F(x)     (*(AE_F_SET(x) ? x + 32 : x + 26))
  59 #define PREQ_IE_TARGET_ADDR(x)  (AE_F_SET(x) ? x + 33 : x + 27)
  60 #define PREQ_IE_TARGET_SN(x)    u32_field_get(x, 33, AE_F_SET(x))
  61
  62
  63 #define PREP_IE_FLAGS(x)        PREQ_IE_FLAGS(x)
  64 #define PREP_IE_HOPCOUNT(x)     PREQ_IE_HOPCOUNT(x)
  65 #define PREP_IE_TTL(x)          PREQ_IE_TTL(x)
  66 #define PREP_IE_ORIG_ADDR(x)    (AE_F_SET(x) ? x + 27 : x + 21)
  67 #define PREP_IE_ORIG_SN(x)      u32_field_get(x, 27, AE_F_SET(x))
  68 #define PREP_IE_LIFETIME(x)     u32_field_get(x, 13, AE_F_SET(x))
  69 #define PREP_IE_METRIC(x)       u32_field_get(x, 17, AE_F_SET(x))
  70 #define PREP_IE_TARGET_ADDR(x)  (x + 3)
  71 #define PREP_IE_TARGET_SN(x)    u32_field_get(x, 9, 0)
  72
  73 #define PERR_IE_TTL(x)          (*(x))
  74 #define PERR_IE_TARGET_FLAGS(x) (*(x + 2))
  75 #define PERR_IE_TARGET_ADDR(x)  (x + 3)
  76 #define PERR_IE_TARGET_SN(x)    u32_field_get(x, 9, 0)
  77 #define PERR_IE_TARGET_RCODE(x) u16_field_get(x, 13, 0)
  78
  79 #define MSEC_TO_TU(x) (x*1000/1024)
  80 #define SN_GT(x, y) ((s32)(y - x) < 0)
  81 #define SN_LT(x, y) ((s32)(x - y) < 0)
  82
  83 #define net_traversal_jiffies(s) \
  84         msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPnetDiameterTraversalTime)
  85 #define default_lifetime(s) \
  86         MSEC_TO_TU(s->u.mesh.mshcfg.dot11MeshHWMPactivePathTimeout)
  87 #define min_preq_int_jiff(s) \
  88         (msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPpreqMinInterval))
  89 #define max_preq_retries(s) (s->u.mesh.mshcfg.dot11MeshHWMPmaxPREQretries)
  90 #define disc_timeout_jiff(s) \
  91         msecs_to_jiffies(sdata->u.mesh.mshcfg.min_discovery_timeout)
  92 #define root_path_confirmation_jiffies(s) \
  93         msecs_to_jiffies(sdata->u.mesh.mshcfg.dot11MeshHWMPconfirmationInterval)
  94
  95 enum mpath_frame_type {
  96         MPATH_PREQ = 0,
  97         MPATH_PREP,
  98         MPATH_PERR,
  99         MPATH_RANN
 100 };
 101
 102 static const u8 broadcast_addr[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
 103
 104 static int mesh_path_sel_frame_tx(enum mpath_frame_type action, u8 flags,
 105                                   const u8 *orig_addr, __le32 orig_sn,
 106                                   u8 target_flags, const u8 *target,
 107                                   __le32 target_sn, const u8 *da,
 108                                   u8 hop_count, u8 ttl,
 109                                   __le32 lifetime, __le32 metric,
 110                                   __le32 preq_id,
 111                                   struct ieee80211_sub_if_data *sdata)
 112 {
 113         struct ieee80211_local *local = sdata->local;
 114         struct sk_buff *skb;
 115         struct ieee80211_mgmt *mgmt;
 116         u8 *pos, ie_len;
 117         int hdr_len = offsetof(struct ieee80211_mgmt, u.action.u.mesh_action) +
 118                       sizeof(mgmt->u.action.u.mesh_action);
 119
 120         skb = dev_alloc_skb(local->tx_headroom +
 121                             hdr_len +
 122                             2 + 37); /* max HWMP IE */
 123         if (!skb)
 124                 return -1;
 125         skb_reserve(skb, local->tx_headroom);
 126         mgmt = (struct ieee80211_mgmt *) skb_put(skb, hdr_len);
 127         memset(mgmt, 0, hdr_len);
 128         mgmt->frame_control = cpu_to_le16(IEEE80211_FTYPE_MGMT |
 129                                           IEEE80211_STYPE_ACTION);
 130
 131         memcpy(mgmt->da, da, ETH_ALEN);
 132         memcpy(mgmt->sa, sdata->vif.addr, ETH_ALEN);
 133         /* BSSID == SA */
 134         memcpy(mgmt->bssid, sdata->vif.addr, ETH_ALEN);
 135         mgmt->u.action.category = WLAN_CATEGORY_MESH_ACTION;
 136         mgmt->u.action.u.mesh_action.action_code =
 137                                         WLAN_MESH_ACTION_HWMP_PATH_SELECTION;
 138
 139         switch (action) {
 140         case MPATH_PREQ:
 141                 mhwmp_dbg(sdata, "sending PREQ to %pM\n", target);
 142                 ie_len = 37;
 143                 pos = skb_put(skb, 2 + ie_len);
 144                 *pos++ = WLAN_EID_PREQ;
 145                 break;
 146         case MPATH_PREP:
 147                 mhwmp_dbg(sdata, "sending PREP to %pM\n", orig_addr);
 148                 ie_len = 31;
 149                 pos = skb_put(skb, 2 + ie_len);
 150                 *pos++ = WLAN_EID_PREP;
 151                 break;
 152         case MPATH_RANN:
 153                 mhwmp_dbg(sdata, "sending RANN from %pM\n", orig_addr);
 154                 ie_len = sizeof(struct ieee80211_rann_ie);
 155                 pos = skb_put(skb, 2 + ie_len);
 156                 *pos++ = WLAN_EID_RANN;
 157                 break;
 158         default:
 159                 kfree_skb(skb);
 160                 return -ENOTSUPP;
 161                 break;
 162         }
 163         *pos++ = ie_len;
 164         *pos++ = flags;
 165         *pos++ = hop_count;
 166         *pos++ = ttl;
 167         if (action == MPATH_PREP) {
 168                 memcpy(pos, target, ETH_ALEN);
 169                 pos += ETH_ALEN;
 170                 memcpy(pos, &target_sn, 4);
 171                 pos += 4;
 172         } else {
 173                 if (action == MPATH_PREQ) {
 174                         memcpy(pos, &preq_id, 4);
 175                         pos += 4;
 176                 }
 177                 memcpy(pos, orig_addr, ETH_ALEN);
 178                 pos += ETH_ALEN;
 179                 memcpy(pos, &orig_sn, 4);
 180                 pos += 4;
 181         }
 182         memcpy(pos, &lifetime, 4);      /* interval for RANN */
 183         pos += 4;
 184         memcpy(pos, &metric, 4);
 185         pos += 4;
 186         if (action == MPATH_PREQ) {
 187                 *pos++ = 1; /* destination count */
 188                 *pos++ = target_flags;
 189                 memcpy(pos, target, ETH_ALEN);
 190                 pos += ETH_ALEN;
 191                 memcpy(pos, &target_sn, 4);
 192                 pos += 4;
 193         } else if (action == MPATH_PREP) {
 194                 memcpy(pos, orig_addr, ETH_ALEN);
 195                 pos += ETH_ALEN;
 196                 memcpy(pos, &orig_sn, 4);
 197                 pos += 4;
 198         }
 199
 200         ieee80211_tx_skb(sdata, skb);
 201         return 0;
 202 }
 203
 204
 205 /*  Headroom is not adjusted.  Caller should ensure that skb has sufficient
 206  *  headroom in case the frame is encrypted. */
 207 static void prepare_frame_for_deferred_tx(struct ieee80211_sub_if_data *sdata,
 208                 struct sk_buff *skb)
 209 {
 210         struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
 211         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
 212
 213         skb_set_mac_header(skb, 0);
 214         skb_set_network_header(skb, 0);
 215         skb_set_transport_header(skb, 0);
 216
 217         /* Send all internal mgmt frames on VO. Accordingly set TID to 7. */
 218         skb_set_queue_mapping(skb, IEEE80211_AC_VO);
 219         skb->priority = 7;
 220
 221         info->control.vif = &sdata->vif;
 222         info->flags |= IEEE80211_TX_INTFL_NEED_TXPROCESSING;
 223         ieee80211_set_qos_hdr(sdata, skb);
 224         ieee80211_mps_set_frame_flags(sdata, NULL, hdr);
 225 }
 226
 227 /**
 228  * mesh_path_error_tx - Sends a PERR mesh management frame
 229  *
 230  * @ttl: allowed remaining hops
 231  * @target: broken destination
 232  * @target_sn: SN of the broken destination
 233  * @target_rcode: reason code for this PERR
 234  * @ra: node this frame is addressed to
 235  * @sdata: local mesh subif
 236  *
 237  * Note: This function may be called with driver locks taken that the driver
 238  * also acquires in the TX path.  To avoid a deadlock we don't transmit the
 239  * frame directly but add it to the pending queue instead.
 240  */
 241 int mesh_path_error_tx(struct ieee80211_sub_if_data *sdata,
 242                        u8 ttl, const u8 *target, __le32 target_sn,
 243                        __le16 target_rcode, const u8 *ra)
 244 {
 245         struct ieee80211_local *local = sdata->local;
 246         struct sk_buff *skb;
 247         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 248         struct ieee80211_mgmt *mgmt;
 249         u8 *pos, ie_len;
 250         int hdr_len = offsetof(struct ieee80211_mgmt, u.action.u.mesh_action) +
 251                       sizeof(mgmt->u.action.u.mesh_action);
 252
 253         if (time_before(jiffies, ifmsh->next_perr))
 254                 return -EAGAIN;
 255
 256         skb = dev_alloc_skb(local->tx_headroom +
 257                             IEEE80211_ENCRYPT_HEADROOM +
 258                             IEEE80211_ENCRYPT_TAILROOM +
 259                             hdr_len +
 260                             2 + 15 /* PERR IE */);
 261         if (!skb)
 262                 return -1;
 263         skb_reserve(skb, local->tx_headroom + IEEE80211_ENCRYPT_HEADROOM);
 264         mgmt = (struct ieee80211_mgmt *) skb_put(skb, hdr_len);
 265         memset(mgmt, 0, hdr_len);
 266         mgmt->frame_control = cpu_to_le16(IEEE80211_FTYPE_MGMT |
 267                                           IEEE80211_STYPE_ACTION);
 268
 269         memcpy(mgmt->da, ra, ETH_ALEN);
 270         memcpy(mgmt->sa, sdata->vif.addr, ETH_ALEN);
 271         /* BSSID == SA */
 272         memcpy(mgmt->bssid, sdata->vif.addr, ETH_ALEN);
 273         mgmt->u.action.category = WLAN_CATEGORY_MESH_ACTION;
 274         mgmt->u.action.u.mesh_action.action_code =
 275                                         WLAN_MESH_ACTION_HWMP_PATH_SELECTION;
 276         ie_len = 15;
 277         pos = skb_put(skb, 2 + ie_len);
 278         *pos++ = WLAN_EID_PERR;
 279         *pos++ = ie_len;
 280         /* ttl */
 281         *pos++ = ttl;
 282         /* number of destinations */
 283         *pos++ = 1;
 284         /*
 285          * flags bit, bit 1 is unset if we know the sequence number and
 286          * bit 2 is set if we have a reason code
 287          */
 288         *pos = 0;
 289         if (!target_sn)
 290                 *pos |= MP_F_USN;
 291         if (target_rcode)
 292                 *pos |= MP_F_RCODE;
 293         pos++;
 294         memcpy(pos, target, ETH_ALEN);
 295         pos += ETH_ALEN;
 296         memcpy(pos, &target_sn, 4);
 297         pos += 4;
 298         memcpy(pos, &target_rcode, 2);
 299
 300         /* see note in function header */
 301         prepare_frame_for_deferred_tx(sdata, skb);
 302         ifmsh->next_perr = TU_TO_EXP_TIME(
 303                                    ifmsh->mshcfg.dot11MeshHWMPperrMinInterval);
 304         ieee80211_add_pending_skb(local, skb);
 305         return 0;
 306 }
 307
 308 void ieee80211s_update_metric(struct ieee80211_local *local,
 309                 struct sta_info *sta, struct sk_buff *skb)
 310 {
 311         struct ieee80211_tx_info *txinfo = IEEE80211_SKB_CB(skb);
 312         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
 313         int failed;
 314
 315         if (!ieee80211_is_data(hdr->frame_control))
 316                 return;
 317
 318         failed = !(txinfo->flags & IEEE80211_TX_STAT_ACK);
 319
 320         /* moving average, scaled to 100 */
 321         sta->fail_avg = ((80 * sta->fail_avg + 5) / 100 + 20 * failed);
 322         if (sta->fail_avg > 95)
 323                 mesh_plink_broken(sta);
 324 }
 325
 326 static u32 airtime_link_metric_get(struct ieee80211_local *local,
 327                                    struct sta_info *sta)
 328 {
 329         struct rate_info rinfo;
 330         /* This should be adjusted for each device */
 331         int device_constant = 1 << ARITH_SHIFT;
 332         int test_frame_len = TEST_FRAME_LEN << ARITH_SHIFT;
 333         int s_unit = 1 << ARITH_SHIFT;
 334         int rate, err;
 335         u32 tx_time, estimated_retx;
 336         u64 result;
 337
 338         if (sta->fail_avg >= 100)
 339                 return MAX_METRIC;
 340
 341         sta_set_rate_info_tx(sta, &sta->last_tx_rate, &rinfo);
 342         rate = cfg80211_calculate_bitrate(&rinfo);
 343         if (WARN_ON(!rate))
 344                 return MAX_METRIC;
 345
 346         err = (sta->fail_avg << ARITH_SHIFT) / 100;
 347
 348         /* bitrate is in units of 100 Kbps, while we need rate in units of
 349          * 1Mbps. This will be corrected on tx_time computation.
 350          */
 351         tx_time = (device_constant + 10 * test_frame_len / rate);
 352         estimated_retx = ((1 << (2 * ARITH_SHIFT)) / (s_unit - err));
 353         result = (tx_time * estimated_retx) >> (2 * ARITH_SHIFT) ;
 354         return (u32)result;
 355 }
 356
 357 /**
 358  * hwmp_route_info_get - Update routing info to originator and transmitter
 359  *
 360  * @sdata: local mesh subif
 361  * @mgmt: mesh management frame
 362  * @hwmp_ie: hwmp information element (PREP or PREQ)
 363  * @action: type of hwmp ie
 364  *
 365  * This function updates the path routing information to the originator and the
 366  * transmitter of a HWMP PREQ or PREP frame.
 367  *
 368  * Returns: metric to frame originator or 0 if the frame should not be further
 369  * processed
 370  *
 371  * Notes: this function is the only place (besides user-provided info) where
 372  * path routing information is updated.
 373  */
 374 static u32 hwmp_route_info_get(struct ieee80211_sub_if_data *sdata,
 375                                struct ieee80211_mgmt *mgmt,
 376                                const u8 *hwmp_ie, enum mpath_frame_type action)
 377 {
 378         struct ieee80211_local *local = sdata->local;
 379         struct mesh_path *mpath;
 380         struct sta_info *sta;
 381         bool fresh_info;
 382         const u8 *orig_addr, *ta;
 383         u32 orig_sn, orig_metric;
 384         unsigned long orig_lifetime, exp_time;
 385         u32 last_hop_metric, new_metric;
 386         bool process = true;
 387
 388         rcu_read_lock();
 389         sta = sta_info_get(sdata, mgmt->sa);
 390         if (!sta) {
 391                 rcu_read_unlock();
 392                 return 0;
 393         }
 394
 395         last_hop_metric = airtime_link_metric_get(local, sta);
 396         /* Update and check originator routing info */
 397         fresh_info = true;
 398
 399         switch (action) {
 400         case MPATH_PREQ:
 401                 orig_addr = PREQ_IE_ORIG_ADDR(hwmp_ie);
 402                 orig_sn = PREQ_IE_ORIG_SN(hwmp_ie);
 403                 orig_lifetime = PREQ_IE_LIFETIME(hwmp_ie);
 404                 orig_metric = PREQ_IE_METRIC(hwmp_ie);
 405                 break;
 406         case MPATH_PREP:
 407                 /* Originator here refers to the MP that was the target in the
 408                  * Path Request. We divert from the nomenclature in the draft
 409                  * so that we can easily use a single function to gather path
 410                  * information from both PREQ and PREP frames.
 411                  */
 412                 orig_addr = PREP_IE_TARGET_ADDR(hwmp_ie);
 413                 orig_sn = PREP_IE_TARGET_SN(hwmp_ie);
 414                 orig_lifetime = PREP_IE_LIFETIME(hwmp_ie);
 415                 orig_metric = PREP_IE_METRIC(hwmp_ie);
 416                 break;
 417         default:
 418                 rcu_read_unlock();
 419                 return 0;
 420         }
 421         new_metric = orig_metric + last_hop_metric;
 422         if (new_metric < orig_metric)
 423                 new_metric = MAX_METRIC;
 424         exp_time = TU_TO_EXP_TIME(orig_lifetime);
 425
 426         if (ether_addr_equal(orig_addr, sdata->vif.addr)) {
 427                 /* This MP is the originator, we are not interested in this
 428                  * frame, except for updating transmitter's path info.
 429                  */
 430                 process = false;
 431                 fresh_info = false;
 432         } else {
 433                 mpath = mesh_path_lookup(sdata, orig_addr);
 434                 if (mpath) {
 435                         spin_lock_bh(&mpath->state_lock);
 436                         if (mpath->flags & MESH_PATH_FIXED)
 437                                 fresh_info = false;
 438                         else if ((mpath->flags & MESH_PATH_ACTIVE) &&
 439                             (mpath->flags & MESH_PATH_SN_VALID)) {
 440                                 if (SN_GT(mpath->sn, orig_sn) ||
 441                                     (mpath->sn == orig_sn &&
 442                                      new_metric >= mpath->metric)) {
 443                                         process = false;
 444                                         fresh_info = false;
 445                                 }
 446                         }
 447                 } else {
 448                         mpath = mesh_path_add(sdata, orig_addr);
 449                         if (IS_ERR(mpath)) {
 450                                 rcu_read_unlock();
 451                                 return 0;
 452                         }
 453                         spin_lock_bh(&mpath->state_lock);
 454                 }
 455
 456                 if (fresh_info) {
 457                         mesh_path_assign_nexthop(mpath, sta);
 458                         mpath->flags |= MESH_PATH_SN_VALID;
 459                         mpath->metric = new_metric;
 460                         mpath->sn = orig_sn;
 461                         mpath->exp_time = time_after(mpath->exp_time, exp_time)
 462                                           ?  mpath->exp_time : exp_time;
 463                         mesh_path_activate(mpath);
 464                         spin_unlock_bh(&mpath->state_lock);
 465                         mesh_path_tx_pending(mpath);
 466                         /* draft says preq_id should be saved to, but there does
 467                          * not seem to be any use for it, skipping by now
 468                          */
 469                 } else
 470                         spin_unlock_bh(&mpath->state_lock);
 471         }
 472
 473         /* Update and check transmitter routing info */
 474         ta = mgmt->sa;
 475         if (ether_addr_equal(orig_addr, ta))
 476                 fresh_info = false;
 477         else {
 478                 fresh_info = true;
 479
 480                 mpath = mesh_path_lookup(sdata, ta);
 481                 if (mpath) {
 482                         spin_lock_bh(&mpath->state_lock);
 483                         if ((mpath->flags & MESH_PATH_FIXED) ||
 484                                 ((mpath->flags & MESH_PATH_ACTIVE) &&
 485                                         (last_hop_metric > mpath->metric)))
 486                                 fresh_info = false;
 487                 } else {
 488                         mpath = mesh_path_add(sdata, ta);
 489                         if (IS_ERR(mpath)) {
 490                                 rcu_read_unlock();
 491                                 return 0;
 492                         }
 493                         spin_lock_bh(&mpath->state_lock);
 494                 }
 495
 496                 if (fresh_info) {
 497                         mesh_path_assign_nexthop(mpath, sta);
 498                         mpath->metric = last_hop_metric;
 499                         mpath->exp_time = time_after(mpath->exp_time, exp_time)
 500                                           ?  mpath->exp_time : exp_time;
 501                         mesh_path_activate(mpath);
 502                         spin_unlock_bh(&mpath->state_lock);
 503                         mesh_path_tx_pending(mpath);
 504                 } else
 505                         spin_unlock_bh(&mpath->state_lock);
 506         }
 507
 508         rcu_read_unlock();
 509
 510         return process ? new_metric : 0;
 511 }
 512
 513 static void hwmp_preq_frame_process(struct ieee80211_sub_if_data *sdata,
 514                                     struct ieee80211_mgmt *mgmt,
 515                                     const u8 *preq_elem, u32 metric)
 516 {
 517         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 518         struct mesh_path *mpath = NULL;
 519         const u8 *target_addr, *orig_addr;
 520         const u8 *da;
 521         u8 target_flags, ttl, flags;
 522         u32 orig_sn, target_sn, lifetime, orig_metric;
 523         bool reply = false;
 524         bool forward = true;
 525         bool root_is_gate;
 526
 527         /* Update target SN, if present */
 528         target_addr = PREQ_IE_TARGET_ADDR(preq_elem);
 529         orig_addr = PREQ_IE_ORIG_ADDR(preq_elem);
 530         target_sn = PREQ_IE_TARGET_SN(preq_elem);
 531         orig_sn = PREQ_IE_ORIG_SN(preq_elem);
 532         target_flags = PREQ_IE_TARGET_F(preq_elem);
 533         orig_metric = metric;
 534         /* Proactive PREQ gate announcements */
 535         flags = PREQ_IE_FLAGS(preq_elem);
 536         root_is_gate = !!(flags & RANN_FLAG_IS_GATE);
 537
 538         mhwmp_dbg(sdata, "received PREQ from %pM\n", orig_addr);
 539
 540         if (ether_addr_equal(target_addr, sdata->vif.addr)) {
 541                 mhwmp_dbg(sdata, "PREQ is for us\n");
 542                 forward = false;
 543                 reply = true;
 544                 metric = 0;
 545                 if (time_after(jiffies, ifmsh->last_sn_update +
 546                                         net_traversal_jiffies(sdata)) ||
 547                     time_before(jiffies, ifmsh->last_sn_update)) {
 548                         target_sn = ++ifmsh->sn;
 549                         ifmsh->last_sn_update = jiffies;
 550                 }
 551         } else if (is_broadcast_ether_addr(target_addr) &&
 552                    (target_flags & IEEE80211_PREQ_TO_FLAG)) {
 553                 rcu_read_lock();
 554                 mpath = mesh_path_lookup(sdata, orig_addr);
 555                 if (mpath) {
 556                         if (flags & IEEE80211_PREQ_PROACTIVE_PREP_FLAG) {
 557                                 reply = true;
 558                                 target_addr = sdata->vif.addr;
 559                                 target_sn = ++ifmsh->sn;
 560                                 metric = 0;
 561                                 ifmsh->last_sn_update = jiffies;
 562                         }
 563                         if (root_is_gate)
 564                                 mesh_path_add_gate(mpath);
 565                 }
 566                 rcu_read_unlock();
 567         } else {
 568                 rcu_read_lock();
 569                 mpath = mesh_path_lookup(sdata, target_addr);
 570                 if (mpath) {
 571                         if ((!(mpath->flags & MESH_PATH_SN_VALID)) ||
 572                                         SN_LT(mpath->sn, target_sn)) {
 573                                 mpath->sn = target_sn;
 574                                 mpath->flags |= MESH_PATH_SN_VALID;
 575                         } else if ((!(target_flags & MP_F_DO)) &&
 576                                         (mpath->flags & MESH_PATH_ACTIVE)) {
 577                                 reply = true;
 578                                 metric = mpath->metric;
 579                                 target_sn = mpath->sn;
 580                                 if (target_flags & MP_F_RF)
 581                                         target_flags |= MP_F_DO;
 582                                 else
 583                                         forward = false;
 584                         }
 585                 }
 586                 rcu_read_unlock();
 587         }
 588
 589         if (reply) {
 590                 lifetime = PREQ_IE_LIFETIME(preq_elem);
 591                 ttl = ifmsh->mshcfg.element_ttl;
 592                 if (ttl != 0) {
 593                         mhwmp_dbg(sdata, "replying to the PREQ\n");
 594                         mesh_path_sel_frame_tx(MPATH_PREP, 0, orig_addr,
 595                                 cpu_to_le32(orig_sn), 0, target_addr,
 596                                 cpu_to_le32(target_sn), mgmt->sa, 0, ttl,
 597                                 cpu_to_le32(lifetime), cpu_to_le32(metric),
 598                                 0, sdata);
 599                 } else {
 600                         ifmsh->mshstats.dropped_frames_ttl++;
 601                 }
 602         }
 603
 604         if (forward && ifmsh->mshcfg.dot11MeshForwarding) {
 605                 u32 preq_id;
 606                 u8 hopcount;
 607
 608                 ttl = PREQ_IE_TTL(preq_elem);
 609                 lifetime = PREQ_IE_LIFETIME(preq_elem);
 610                 if (ttl <= 1) {
 611                         ifmsh->mshstats.dropped_frames_ttl++;
 612                         return;
 613                 }
 614                 mhwmp_dbg(sdata, "forwarding the PREQ from %pM\n", orig_addr);
 615                 --ttl;
 616                 preq_id = PREQ_IE_PREQ_ID(preq_elem);
 617                 hopcount = PREQ_IE_HOPCOUNT(preq_elem) + 1;
 618                 da = (mpath && mpath->is_root) ?
 619                         mpath->rann_snd_addr : broadcast_addr;
 620
 621                 if (flags & IEEE80211_PREQ_PROACTIVE_PREP_FLAG) {
 622                         target_addr = PREQ_IE_TARGET_ADDR(preq_elem);
 623                         target_sn = PREQ_IE_TARGET_SN(preq_elem);
 624                         metric = orig_metric;
 625                 }
 626
 627                 mesh_path_sel_frame_tx(MPATH_PREQ, flags, orig_addr,
 628                                 cpu_to_le32(orig_sn), target_flags, target_addr,
 629                                 cpu_to_le32(target_sn), da,
 630                                 hopcount, ttl, cpu_to_le32(lifetime),
 631                                 cpu_to_le32(metric), cpu_to_le32(preq_id),
 632                                 sdata);
 633                 if (!is_multicast_ether_addr(da))
 634                         ifmsh->mshstats.fwded_unicast++;
 635                 else
 636                         ifmsh->mshstats.fwded_mcast++;
 637                 ifmsh->mshstats.fwded_frames++;
 638         }
 639 }
 640
 641
 642 static inline struct sta_info *
 643 next_hop_deref_protected(struct mesh_path *mpath)
 644 {
 645         return rcu_dereference_protected(mpath->next_hop,
 646                                          lockdep_is_held(&mpath->state_lock));
 647 }
 648
 649
 650 static void hwmp_prep_frame_process(struct ieee80211_sub_if_data *sdata,
 651                                     struct ieee80211_mgmt *mgmt,
 652                                     const u8 *prep_elem, u32 metric)
 653 {
 654         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 655         struct mesh_path *mpath;
 656         const u8 *target_addr, *orig_addr;
 657         u8 ttl, hopcount, flags;
 658         u8 next_hop[ETH_ALEN];
 659         u32 target_sn, orig_sn, lifetime;
 660
 661         mhwmp_dbg(sdata, "received PREP from %pM\n",
 662                   PREP_IE_TARGET_ADDR(prep_elem));
 663
 664         orig_addr = PREP_IE_ORIG_ADDR(prep_elem);
 665         if (ether_addr_equal(orig_addr, sdata->vif.addr))
 666                 /* destination, no forwarding required */
 667                 return;
 668
 669         if (!ifmsh->mshcfg.dot11MeshForwarding)
 670                 return;
 671
 672         ttl = PREP_IE_TTL(prep_elem);
 673         if (ttl <= 1) {
 674                 sdata->u.mesh.mshstats.dropped_frames_ttl++;
 675                 return;
 676         }
 677
 678         rcu_read_lock();
 679         mpath = mesh_path_lookup(sdata, orig_addr);
 680         if (mpath)
 681                 spin_lock_bh(&mpath->state_lock);
 682         else
 683                 goto fail;
 684         if (!(mpath->flags & MESH_PATH_ACTIVE)) {
 685                 spin_unlock_bh(&mpath->state_lock);
 686                 goto fail;
 687         }
 688         memcpy(next_hop, next_hop_deref_protected(mpath)->sta.addr, ETH_ALEN);
 689         spin_unlock_bh(&mpath->state_lock);
 690         --ttl;
 691         flags = PREP_IE_FLAGS(prep_elem);
 692         lifetime = PREP_IE_LIFETIME(prep_elem);
 693         hopcount = PREP_IE_HOPCOUNT(prep_elem) + 1;
 694         target_addr = PREP_IE_TARGET_ADDR(prep_elem);
 695         target_sn = PREP_IE_TARGET_SN(prep_elem);
 696         orig_sn = PREP_IE_ORIG_SN(prep_elem);
 697
 698         mesh_path_sel_frame_tx(MPATH_PREP, flags, orig_addr,
 699                 cpu_to_le32(orig_sn), 0, target_addr,
 700                 cpu_to_le32(target_sn), next_hop, hopcount,
 701                 ttl, cpu_to_le32(lifetime), cpu_to_le32(metric),
 702                 0, sdata);
 703         rcu_read_unlock();
 704
 705         sdata->u.mesh.mshstats.fwded_unicast++;
 706         sdata->u.mesh.mshstats.fwded_frames++;
 707         return;
 708
 709 fail:
 710         rcu_read_unlock();
 711         sdata->u.mesh.mshstats.dropped_frames_no_route++;
 712 }
 713
 714 static void hwmp_perr_frame_process(struct ieee80211_sub_if_data *sdata,
 715                                     struct ieee80211_mgmt *mgmt,
 716                                     const u8 *perr_elem)
 717 {
 718         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 719         struct mesh_path *mpath;
 720         u8 ttl;
 721         const u8 *ta, *target_addr;
 722         u32 target_sn;
 723         u16 target_rcode;
 724
 725         ta = mgmt->sa;
 726         ttl = PERR_IE_TTL(perr_elem);
 727         if (ttl <= 1) {
 728                 ifmsh->mshstats.dropped_frames_ttl++;
 729                 return;
 730         }
 731         ttl--;
 732         target_addr = PERR_IE_TARGET_ADDR(perr_elem);
 733         target_sn = PERR_IE_TARGET_SN(perr_elem);
 734         target_rcode = PERR_IE_TARGET_RCODE(perr_elem);
 735
 736         rcu_read_lock();
 737         mpath = mesh_path_lookup(sdata, target_addr);
 738         if (mpath) {
 739                 struct sta_info *sta;
 740
 741                 spin_lock_bh(&mpath->state_lock);
 742                 sta = next_hop_deref_protected(mpath);
 743                 if (mpath->flags & MESH_PATH_ACTIVE &&
 744                     ether_addr_equal(ta, sta->sta.addr) &&
 745                     (!(mpath->flags & MESH_PATH_SN_VALID) ||
 746                     SN_GT(target_sn, mpath->sn))) {
 747                         mpath->flags &= ~MESH_PATH_ACTIVE;
 748                         mpath->sn = target_sn;
 749                         spin_unlock_bh(&mpath->state_lock);
 750                         if (!ifmsh->mshcfg.dot11MeshForwarding)
 751                                 goto endperr;
 752                         mesh_path_error_tx(sdata, ttl, target_addr,
 753                                            cpu_to_le32(target_sn),
 754                                            cpu_to_le16(target_rcode),
 755                                            broadcast_addr);
 756                 } else
 757                         spin_unlock_bh(&mpath->state_lock);
 758         }
 759 endperr:
 760         rcu_read_unlock();
 761 }
 762
 763 static void hwmp_rann_frame_process(struct ieee80211_sub_if_data *sdata,
 764                                     struct ieee80211_mgmt *mgmt,
 765                                     const struct ieee80211_rann_ie *rann)
 766 {
 767         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 768         struct ieee80211_local *local = sdata->local;
 769         struct sta_info *sta;
 770         struct mesh_path *mpath;
 771         u8 ttl, flags, hopcount;
 772         const u8 *orig_addr;
 773         u32 orig_sn, metric, metric_txsta, interval;
 774         bool root_is_gate;
 775
 776         ttl = rann->rann_ttl;
 777         flags = rann->rann_flags;
 778         root_is_gate = !!(flags & RANN_FLAG_IS_GATE);
 779         orig_addr = rann->rann_addr;
 780         orig_sn = le32_to_cpu(rann->rann_seq);
 781         interval = le32_to_cpu(rann->rann_interval);
 782         hopcount = rann->rann_hopcount;
 783         hopcount++;
 784         metric = le32_to_cpu(rann->rann_metric);
 785
 786         /*  Ignore our own RANNs */
 787         if (ether_addr_equal(orig_addr, sdata->vif.addr))
 788                 return;
 789
 790         mhwmp_dbg(sdata,
 791                   "received RANN from %pM via neighbour %pM (is_gate=%d)\n",
 792                   orig_addr, mgmt->sa, root_is_gate);
 793
 794         rcu_read_lock();
 795         sta = sta_info_get(sdata, mgmt->sa);
 796         if (!sta) {
 797                 rcu_read_unlock();
 798                 return;
 799         }
 800
 801         metric_txsta = airtime_link_metric_get(local, sta);
 802
 803         mpath = mesh_path_lookup(sdata, orig_addr);
 804         if (!mpath) {
 805                 mpath = mesh_path_add(sdata, orig_addr);
 806                 if (IS_ERR(mpath)) {
 807                         rcu_read_unlock();
 808                         sdata->u.mesh.mshstats.dropped_frames_no_route++;
 809                         return;
 810                 }
 811         }
 812
 813         if (!(SN_LT(mpath->sn, orig_sn)) &&
 814             !(mpath->sn == orig_sn && metric < mpath->rann_metric)) {
 815                 rcu_read_unlock();
 816                 return;
 817         }
 818
 819         if ((!(mpath->flags & (MESH_PATH_ACTIVE | MESH_PATH_RESOLVING)) ||
 820              (time_after(jiffies, mpath->last_preq_to_root +
 821                                   root_path_confirmation_jiffies(sdata)) ||
 822              time_before(jiffies, mpath->last_preq_to_root))) &&
 823              !(mpath->flags & MESH_PATH_FIXED) && (ttl != 0)) {
 824                 mhwmp_dbg(sdata,
 825                           "time to refresh root mpath %pM\n",
 826                           orig_addr);
 827                 mesh_queue_preq(mpath, PREQ_Q_F_START | PREQ_Q_F_REFRESH);
 828                 mpath->last_preq_to_root = jiffies;
 829         }
 830
 831         mpath->sn = orig_sn;
 832         mpath->rann_metric = metric + metric_txsta;
 833         mpath->is_root = true;
 834         /* Recording RANNs sender address to send individually
 835          * addressed PREQs destined for root mesh STA */
 836         memcpy(mpath->rann_snd_addr, mgmt->sa, ETH_ALEN);
 837
 838         if (root_is_gate)
 839                 mesh_path_add_gate(mpath);
 840
 841         if (ttl <= 1) {
 842                 ifmsh->mshstats.dropped_frames_ttl++;
 843                 rcu_read_unlock();
 844                 return;
 845         }
 846         ttl--;
 847
 848         if (ifmsh->mshcfg.dot11MeshForwarding) {
 849                 mesh_path_sel_frame_tx(MPATH_RANN, flags, orig_addr,
 850                                        cpu_to_le32(orig_sn),
 851                                        0, NULL, 0, broadcast_addr,
 852                                        hopcount, ttl, cpu_to_le32(interval),
 853                                        cpu_to_le32(metric + metric_txsta),
 854                                        0, sdata);
 855         }
 856
 857         rcu_read_unlock();
 858 }
 859
 860
 861 void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
 862                             struct ieee80211_mgmt *mgmt, size_t len)
 863 {
 864         struct ieee802_11_elems elems;
 865         size_t baselen;
 866         u32 last_hop_metric;
 867         struct sta_info *sta;
 868
 869         /* need action_code */
 870         if (len < IEEE80211_MIN_ACTION_SIZE + 1)
 871                 return;
 872
 873         rcu_read_lock();
 874         sta = sta_info_get(sdata, mgmt->sa);
 875         if (!sta || sta->plink_state != NL80211_PLINK_ESTAB) {
 876                 rcu_read_unlock();
 877                 return;
 878         }
 879         rcu_read_unlock();
 880
 881         baselen = (u8 *) mgmt->u.action.u.mesh_action.variable - (u8 *) mgmt;
 882         ieee802_11_parse_elems(mgmt->u.action.u.mesh_action.variable,
 883                                len - baselen, false, &elems);
 884
 885         if (elems.preq) {
 886                 if (elems.preq_len != 37)
 887                         /* Right now we support just 1 destination and no AE */
 888                         return;
 889                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.preq,
 890                                                       MPATH_PREQ);
 891                 if (last_hop_metric)
 892                         hwmp_preq_frame_process(sdata, mgmt, elems.preq,
 893                                                 last_hop_metric);
 894         }
 895         if (elems.prep) {
 896                 if (elems.prep_len != 31)
 897                         /* Right now we support no AE */
 898                         return;
 899                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.prep,
 900                                                       MPATH_PREP);
 901                 if (last_hop_metric)
 902                         hwmp_prep_frame_process(sdata, mgmt, elems.prep,
 903                                                 last_hop_metric);
 904         }
 905         if (elems.perr) {
 906                 if (elems.perr_len != 15)
 907                         /* Right now we support only one destination per PERR */
 908                         return;
 909                 hwmp_perr_frame_process(sdata, mgmt, elems.perr);
 910         }
 911         if (elems.rann)
 912                 hwmp_rann_frame_process(sdata, mgmt, elems.rann);
 913 }
 914
 915 /**
 916  * mesh_queue_preq - queue a PREQ to a given destination
 917  *
 918  * @mpath: mesh path to discover
 919  * @flags: special attributes of the PREQ to be sent
 920  *
 921  * Locking: the function must be called from within a rcu read lock block.
 922  *
 923  */
 924 static void mesh_queue_preq(struct mesh_path *mpath, u8 flags)
 925 {
 926         struct ieee80211_sub_if_data *sdata = mpath->sdata;
 927         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 928         struct mesh_preq_queue *preq_node;
 929
 930         preq_node = kmalloc(sizeof(struct mesh_preq_queue), GFP_ATOMIC);
 931         if (!preq_node) {
 932                 mhwmp_dbg(sdata, "could not allocate PREQ node\n");
 933                 return;
 934         }
 935
 936         spin_lock_bh(&ifmsh->mesh_preq_queue_lock);
 937         if (ifmsh->preq_queue_len == MAX_PREQ_QUEUE_LEN) {
 938                 spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 939                 kfree(preq_node);
 940                 if (printk_ratelimit())
 941                         mhwmp_dbg(sdata, "PREQ node queue full\n");
 942                 return;
 943         }
 944
 945         spin_lock(&mpath->state_lock);
 946         if (mpath->flags & MESH_PATH_REQ_QUEUED) {
 947                 spin_unlock(&mpath->state_lock);
 948                 spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 949                 kfree(preq_node);
 950                 return;
 951         }
 952
 953         memcpy(preq_node->dst, mpath->dst, ETH_ALEN);
 954         preq_node->flags = flags;
 955
 956         mpath->flags |= MESH_PATH_REQ_QUEUED;
 957         spin_unlock(&mpath->state_lock);
 958
 959         list_add_tail(&preq_node->list, &ifmsh->preq_queue.list);
 960         ++ifmsh->preq_queue_len;
 961         spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 962
 963         if (time_after(jiffies, ifmsh->last_preq + min_preq_int_jiff(sdata)))
 964                 ieee80211_queue_work(&sdata->local->hw, &sdata->work);
 965
 966         else if (time_before(jiffies, ifmsh->last_preq)) {
 967                 /* avoid long wait if did not send preqs for a long time
 968                  * and jiffies wrapped around
 969                  */
 970                 ifmsh->last_preq = jiffies - min_preq_int_jiff(sdata) - 1;
 971                 ieee80211_queue_work(&sdata->local->hw, &sdata->work);
 972         } else
 973                 mod_timer(&ifmsh->mesh_path_timer, ifmsh->last_preq +
 974                                                 min_preq_int_jiff(sdata));
 975 }
 976
 977 /**
 978  * mesh_path_start_discovery - launch a path discovery from the PREQ queue
 979  *
 980  * @sdata: local mesh subif
 981  */
 982 void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata)
 983 {
 984         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 985         struct mesh_preq_queue *preq_node;
 986         struct mesh_path *mpath;
 987         u8 ttl, target_flags;
 988         const u8 *da;
 989         u32 lifetime;
 990
 991         spin_lock_bh(&ifmsh->mesh_preq_queue_lock);
 992         if (!ifmsh->preq_queue_len ||
 993                 time_before(jiffies, ifmsh->last_preq +
 994                                 min_preq_int_jiff(sdata))) {
 995                 spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 996                 return;
 997         }
 998
 999         preq_node = list_first_entry(&ifmsh->preq_queue.list,
1000                         struct mesh_preq_queue, list);
1001         list_del(&preq_node->list);
1002         --ifmsh->preq_queue_len;
1003         spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
1004
1005         rcu_read_lock();
1006         mpath = mesh_path_lookup(sdata, preq_node->dst);
1007         if (!mpath)
1008                 goto enddiscovery;
1009
1010         spin_lock_bh(&mpath->state_lock);
1011         mpath->flags &= ~MESH_PATH_REQ_QUEUED;
1012         if (preq_node->flags & PREQ_Q_F_START) {
1013                 if (mpath->flags & MESH_PATH_RESOLVING) {
1014                         spin_unlock_bh(&mpath->state_lock);
1015                         goto enddiscovery;
1016                 } else {
1017                         mpath->flags &= ~MESH_PATH_RESOLVED;
1018                         mpath->flags |= MESH_PATH_RESOLVING;
1019                         mpath->discovery_retries = 0;
1020                         mpath->discovery_timeout = disc_timeout_jiff(sdata);
1021                 }
1022         } else if (!(mpath->flags & MESH_PATH_RESOLVING) ||
1023                         mpath->flags & MESH_PATH_RESOLVED) {
1024                 mpath->flags &= ~MESH_PATH_RESOLVING;
1025                 spin_unlock_bh(&mpath->state_lock);
1026                 goto enddiscovery;
1027         }
1028
1029         ifmsh->last_preq = jiffies;
1030
1031         if (time_after(jiffies, ifmsh->last_sn_update +
1032                                 net_traversal_jiffies(sdata)) ||
1033             time_before(jiffies, ifmsh->last_sn_update)) {
1034                 ++ifmsh->sn;
1035                 sdata->u.mesh.last_sn_update = jiffies;
1036         }
1037         lifetime = default_lifetime(sdata);
1038         ttl = sdata->u.mesh.mshcfg.element_ttl;
1039         if (ttl == 0) {
1040                 sdata->u.mesh.mshstats.dropped_frames_ttl++;
1041                 spin_unlock_bh(&mpath->state_lock);
1042                 goto enddiscovery;
1043         }
1044
1045         if (preq_node->flags & PREQ_Q_F_REFRESH)
1046                 target_flags = MP_F_DO;
1047         else
1048                 target_flags = MP_F_RF;
1049
1050         spin_unlock_bh(&mpath->state_lock);
1051         da = (mpath->is_root) ? mpath->rann_snd_addr : broadcast_addr;
1052         mesh_path_sel_frame_tx(MPATH_PREQ, 0, sdata->vif.addr,
1053                         cpu_to_le32(ifmsh->sn), target_flags, mpath->dst,
1054                         cpu_to_le32(mpath->sn), da, 0,
1055                         ttl, cpu_to_le32(lifetime), 0,
1056                         cpu_to_le32(ifmsh->preq_id++), sdata);
1057         mod_timer(&mpath->timer, jiffies + mpath->discovery_timeout);
1058
1059 enddiscovery:
1060         rcu_read_unlock();
1061         kfree(preq_node);
1062 }
1063
1064 /**
1065  * mesh_nexthop_resolve - lookup next hop; conditionally start path discovery
1066  *
1067  * @skb: 802.11 frame to be sent
1068  * @sdata: network subif the frame will be sent through
1069  *
1070  * Lookup next hop for given skb and start path discovery if no
1071  * forwarding information is found.
1072  *
1073  * Returns: 0 if the next hop was found and -ENOENT if the frame was queued.
1074  * skb is freeed here if no mpath could be allocated.
1075  */
1076 int mesh_nexthop_resolve(struct ieee80211_sub_if_data *sdata,
1077                          struct sk_buff *skb)
1078 {
1079         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
1080         struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
1081         struct mesh_path *mpath;
1082         struct sk_buff *skb_to_free = NULL;
1083         u8 *target_addr = hdr->addr3;
1084         int err = 0;
1085
1086         /* Nulls are only sent to peers for PS and should be pre-addressed */
1087         if (ieee80211_is_qos_nullfunc(hdr->frame_control))
1088                 return 0;
1089
1090         rcu_read_lock();
1091         err = mesh_nexthop_lookup(sdata, skb);
1092         if (!err)
1093                 goto endlookup;
1094
1095         /* no nexthop found, start resolving */
1096         mpath = mesh_path_lookup(sdata, target_addr);
1097         if (!mpath) {
1098                 mpath = mesh_path_add(sdata, target_addr);
1099                 if (IS_ERR(mpath)) {
1100                         mesh_path_discard_frame(sdata, skb);
1101                         err = PTR_ERR(mpath);
1102                         goto endlookup;
1103                 }
1104         }
1105
1106         if (!(mpath->flags & MESH_PATH_RESOLVING))
1107                 mesh_queue_preq(mpath, PREQ_Q_F_START);
1108
1109         if (skb_queue_len(&mpath->frame_queue) >= MESH_FRAME_QUEUE_LEN)
1110                 skb_to_free = skb_dequeue(&mpath->frame_queue);
1111
1112         info->flags |= IEEE80211_TX_INTFL_NEED_TXPROCESSING;
1113         ieee80211_set_qos_hdr(sdata, skb);
1114         skb_queue_tail(&mpath->frame_queue, skb);
1115         err = -ENOENT;
1116         if (skb_to_free)
1117                 mesh_path_discard_frame(sdata, skb_to_free);
1118
1119 endlookup:
1120         rcu_read_unlock();
1121         return err;
1122 }
1123
1124 /**
1125  * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame. Calling
1126  * this function is considered "using" the associated mpath, so preempt a path
1127  * refresh if this mpath expires soon.
1128  *
1129  * @skb: 802.11 frame to be sent
1130  * @sdata: network subif the frame will be sent through
1131  *
1132  * Returns: 0 if the next hop was found. Nonzero otherwise.
1133  */
1134 int mesh_nexthop_lookup(struct ieee80211_sub_if_data *sdata,
1135                         struct sk_buff *skb)
1136 {
1137         struct mesh_path *mpath;
1138         struct sta_info *next_hop;
1139         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
1140         u8 *target_addr = hdr->addr3;
1141         int err = -ENOENT;
1142
1143         rcu_read_lock();
1144         mpath = mesh_path_lookup(sdata, target_addr);
1145
1146         if (!mpath || !(mpath->flags & MESH_PATH_ACTIVE))
1147                 goto endlookup;
1148
1149         if (time_after(jiffies,
1150                        mpath->exp_time -
1151                        msecs_to_jiffies(sdata->u.mesh.mshcfg.path_refresh_time)) &&
1152             ether_addr_equal(sdata->vif.addr, hdr->addr4) &&
1153             !(mpath->flags & MESH_PATH_RESOLVING) &&
1154             !(mpath->flags & MESH_PATH_FIXED))
1155                 mesh_queue_preq(mpath, PREQ_Q_F_START | PREQ_Q_F_REFRESH);
1156
1157         next_hop = rcu_dereference(mpath->next_hop);
1158         if (next_hop) {
1159                 memcpy(hdr->addr1, next_hop->sta.addr, ETH_ALEN);
1160                 memcpy(hdr->addr2, sdata->vif.addr, ETH_ALEN);
1161                 ieee80211_mps_set_frame_flags(sdata, next_hop, hdr);
1162                 err = 0;
1163         }
1164
1165 endlookup:
1166         rcu_read_unlock();
1167         return err;
1168 }
1169
1170 void mesh_path_timer(unsigned long data)
1171 {
1172         struct mesh_path *mpath = (void *) data;
1173         struct ieee80211_sub_if_data *sdata = mpath->sdata;
1174         int ret;
1175
1176         if (sdata->local->quiescing)
1177                 return;
1178
1179         spin_lock_bh(&mpath->state_lock);
1180         if (mpath->flags & MESH_PATH_RESOLVED ||
1181                         (!(mpath->flags & MESH_PATH_RESOLVING))) {
1182                 mpath->flags &= ~(MESH_PATH_RESOLVING | MESH_PATH_RESOLVED);
1183                 spin_unlock_bh(&mpath->state_lock);
1184         } else if (mpath->discovery_retries < max_preq_retries(sdata)) {
1185                 ++mpath->discovery_retries;
1186                 mpath->discovery_timeout *= 2;
1187                 mpath->flags &= ~MESH_PATH_REQ_QUEUED;
1188                 spin_unlock_bh(&mpath->state_lock);
1189                 mesh_queue_preq(mpath, 0);
1190         } else {
1191                 mpath->flags = 0;
1192                 mpath->exp_time = jiffies;
1193                 spin_unlock_bh(&mpath->state_lock);
1194                 if (!mpath->is_gate && mesh_gate_num(sdata) > 0) {
1195                         ret = mesh_path_send_to_gates(mpath);
1196                         if (ret)
1197                                 mhwmp_dbg(sdata, "no gate was reachable\n");
1198                 } else
1199                         mesh_path_flush_pending(mpath);
1200         }
1201 }
1202
1203 void mesh_path_tx_root_frame(struct ieee80211_sub_if_data *sdata)
1204 {
1205         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
1206         u32 interval = ifmsh->mshcfg.dot11MeshHWMPRannInterval;
1207         u8 flags, target_flags = 0;
1208
1209         flags = (ifmsh->mshcfg.dot11MeshGateAnnouncementProtocol)
1210                         ? RANN_FLAG_IS_GATE : 0;
1211
1212         switch (ifmsh->mshcfg.dot11MeshHWMPRootMode) {
1213         case IEEE80211_PROACTIVE_RANN:
1214                 mesh_path_sel_frame_tx(MPATH_RANN, flags, sdata->vif.addr,
1215                                cpu_to_le32(++ifmsh->sn),
1216                                0, NULL, 0, broadcast_addr,
1217                                0, ifmsh->mshcfg.element_ttl,
1218                                cpu_to_le32(interval), 0, 0, sdata);
1219                 break;
1220         case IEEE80211_PROACTIVE_PREQ_WITH_PREP:
1221                 flags |= IEEE80211_PREQ_PROACTIVE_PREP_FLAG;
1222         case IEEE80211_PROACTIVE_PREQ_NO_PREP:
1223                 interval = ifmsh->mshcfg.dot11MeshHWMPactivePathToRootTimeout;
1224                 target_flags |= IEEE80211_PREQ_TO_FLAG |
1225                                 IEEE80211_PREQ_USN_FLAG;
1226                 mesh_path_sel_frame_tx(MPATH_PREQ, flags, sdata->vif.addr,
1227                                 cpu_to_le32(++ifmsh->sn), target_flags,
1228                                 (u8 *) broadcast_addr, 0, broadcast_addr,
1229                                 0, ifmsh->mshcfg.element_ttl,
1230                                 cpu_to_le32(interval),
1231                                 0, cpu_to_le32(ifmsh->preq_id++), sdata);
1232                 break;
1233         default:
1234                 mhwmp_dbg(sdata, "Proactive mechanism not supported\n");
1235                 return;
1236         }
1237 }