SAFE public projects git trees. - safe/jmp/linux-2.6/blob - net/mac80211/mesh_hwmp.c

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