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 = MESH_PATH_SEL_ACTION;
 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, enum mpath_frame_type action)
 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
 292         rcu_read_lock();
 293         sta = sta_info_get(local, mgmt->sa);
 294         if (!sta) {
 295                 rcu_read_unlock();
 296                 return 0;
 297         }
 298
 299         last_hop_metric = airtime_link_metric_get(local, sta);
 300         /* Update and check originator routing info */
 301         fresh_info = true;
 302
 303         switch (action) {
 304         case MPATH_PREQ:
 305                 orig_addr = PREQ_IE_ORIG_ADDR(hwmp_ie);
 306                 orig_dsn = PREQ_IE_ORIG_DSN(hwmp_ie);
 307                 orig_lifetime = PREQ_IE_LIFETIME(hwmp_ie);
 308                 orig_metric = PREQ_IE_METRIC(hwmp_ie);
 309                 break;
 310         case MPATH_PREP:
 311                 /* Originator here refers to the MP that was the destination in
 312                  * the Path Request. The draft refers to that MP as the
 313                  * destination address, even though usually it is the origin of
 314                  * the PREP frame. We divert from the nomenclature in the draft
 315                  * so that we can easily use a single function to gather path
 316                  * information from both PREQ and PREP frames.
 317                  */
 318                 orig_addr = PREP_IE_ORIG_ADDR(hwmp_ie);
 319                 orig_dsn = PREP_IE_ORIG_DSN(hwmp_ie);
 320                 orig_lifetime = PREP_IE_LIFETIME(hwmp_ie);
 321                 orig_metric = PREP_IE_METRIC(hwmp_ie);
 322                 break;
 323         default:
 324                 rcu_read_unlock();
 325                 return 0;
 326         }
 327         new_metric = orig_metric + last_hop_metric;
 328         if (new_metric < orig_metric)
 329                 new_metric = MAX_METRIC;
 330         exp_time = TU_TO_EXP_TIME(orig_lifetime);
 331
 332         if (memcmp(orig_addr, sdata->dev->dev_addr, ETH_ALEN) == 0) {
 333                 /* This MP is the originator, we are not interested in this
 334                  * frame, except for updating transmitter's path info.
 335                  */
 336                 process = false;
 337                 fresh_info = false;
 338         } else {
 339                 mpath = mesh_path_lookup(orig_addr, sdata);
 340                 if (mpath) {
 341                         spin_lock_bh(&mpath->state_lock);
 342                         if (mpath->flags & MESH_PATH_FIXED)
 343                                 fresh_info = false;
 344                         else if ((mpath->flags & MESH_PATH_ACTIVE) &&
 345                             (mpath->flags & MESH_PATH_DSN_VALID)) {
 346                                 if (DSN_GT(mpath->dsn, orig_dsn) ||
 347                                     (mpath->dsn == orig_dsn &&
 348                                      action == MPATH_PREQ &&
 349                                      new_metric > mpath->metric)) {
 350                                         process = false;
 351                                         fresh_info = false;
 352                                 }
 353                         }
 354                 } else {
 355                         mesh_path_add(orig_addr, sdata);
 356                         mpath = mesh_path_lookup(orig_addr, sdata);
 357                         if (!mpath) {
 358                                 rcu_read_unlock();
 359                                 return 0;
 360                         }
 361                         spin_lock_bh(&mpath->state_lock);
 362                 }
 363
 364                 if (fresh_info) {
 365                         mesh_path_assign_nexthop(mpath, sta);
 366                         mpath->flags |= MESH_PATH_DSN_VALID;
 367                         mpath->metric = new_metric;
 368                         mpath->dsn = orig_dsn;
 369                         mpath->exp_time = time_after(mpath->exp_time, exp_time)
 370                                           ?  mpath->exp_time : exp_time;
 371                         mesh_path_activate(mpath);
 372                         spin_unlock_bh(&mpath->state_lock);
 373                         mesh_path_tx_pending(mpath);
 374                         /* draft says preq_id should be saved to, but there does
 375                          * not seem to be any use for it, skipping by now
 376                          */
 377                 } else
 378                         spin_unlock_bh(&mpath->state_lock);
 379         }
 380
 381         /* Update and check transmitter routing info */
 382         ta = mgmt->sa;
 383         if (memcmp(orig_addr, ta, ETH_ALEN) == 0)
 384                 fresh_info = false;
 385         else {
 386                 fresh_info = true;
 387
 388                 mpath = mesh_path_lookup(ta, sdata);
 389                 if (mpath) {
 390                         spin_lock_bh(&mpath->state_lock);
 391                         if ((mpath->flags & MESH_PATH_FIXED) ||
 392                                 ((mpath->flags & MESH_PATH_ACTIVE) &&
 393                                         (last_hop_metric > mpath->metric)))
 394                                 fresh_info = false;
 395                 } else {
 396                         mesh_path_add(ta, sdata);
 397                         mpath = mesh_path_lookup(ta, sdata);
 398                         if (!mpath) {
 399                                 rcu_read_unlock();
 400                                 return 0;
 401                         }
 402                         spin_lock_bh(&mpath->state_lock);
 403                 }
 404
 405                 if (fresh_info) {
 406                         mesh_path_assign_nexthop(mpath, sta);
 407                         mpath->flags &= ~MESH_PATH_DSN_VALID;
 408                         mpath->metric = last_hop_metric;
 409                         mpath->exp_time = time_after(mpath->exp_time, exp_time)
 410                                           ?  mpath->exp_time : exp_time;
 411                         mesh_path_activate(mpath);
 412                         spin_unlock_bh(&mpath->state_lock);
 413                         mesh_path_tx_pending(mpath);
 414                 } else
 415                         spin_unlock_bh(&mpath->state_lock);
 416         }
 417
 418         rcu_read_unlock();
 419
 420         return process ? new_metric : 0;
 421 }
 422
 423 static void hwmp_preq_frame_process(struct ieee80211_sub_if_data *sdata,
 424                                     struct ieee80211_mgmt *mgmt,
 425                                     u8 *preq_elem, u32 metric)
 426 {
 427         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 428         struct mesh_path *mpath;
 429         u8 *dst_addr, *orig_addr;
 430         u8 dst_flags, ttl;
 431         u32 orig_dsn, dst_dsn, lifetime;
 432         bool reply = false;
 433         bool forward = true;
 434
 435         /* Update destination DSN, if present */
 436         dst_addr = PREQ_IE_DST_ADDR(preq_elem);
 437         orig_addr = PREQ_IE_ORIG_ADDR(preq_elem);
 438         dst_dsn = PREQ_IE_DST_DSN(preq_elem);
 439         orig_dsn = PREQ_IE_ORIG_DSN(preq_elem);
 440         dst_flags = PREQ_IE_DST_F(preq_elem);
 441
 442         mhwmp_dbg("received PREQ\n");
 443
 444         if (memcmp(dst_addr, sdata->dev->dev_addr, ETH_ALEN) == 0) {
 445                 mhwmp_dbg("PREQ is for us\n");
 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                 mhwmp_dbg("forwarding the PREQ\n");
 502                 --ttl;
 503                 flags = PREQ_IE_FLAGS(preq_elem);
 504                 preq_id = PREQ_IE_PREQ_ID(preq_elem);
 505                 hopcount = PREQ_IE_HOPCOUNT(preq_elem) + 1;
 506                 mesh_path_sel_frame_tx(MPATH_PREQ, flags, orig_addr,
 507                                 cpu_to_le32(orig_dsn), dst_flags, dst_addr,
 508                                 cpu_to_le32(dst_dsn), sdata->dev->broadcast,
 509                                 hopcount, ttl, cpu_to_le32(lifetime),
 510                                 cpu_to_le32(metric), cpu_to_le32(preq_id),
 511                                 sdata);
 512                 ifmsh->mshstats.fwded_mcast++;
 513                 ifmsh->mshstats.fwded_frames++;
 514         }
 515 }
 516
 517
 518 static void hwmp_prep_frame_process(struct ieee80211_sub_if_data *sdata,
 519                                     struct ieee80211_mgmt *mgmt,
 520                                     u8 *prep_elem, u32 metric)
 521 {
 522         struct mesh_path *mpath;
 523         u8 *dst_addr, *orig_addr;
 524         u8 ttl, hopcount, flags;
 525         u8 next_hop[ETH_ALEN];
 526         u32 dst_dsn, orig_dsn, lifetime;
 527
 528         mhwmp_dbg("received PREP\n");
 529
 530         /* Note that we divert from the draft nomenclature and denominate
 531          * destination to what the draft refers to as origininator. So in this
 532          * function destnation refers to the final destination of the PREP,
 533          * which corresponds with the originator of the PREQ which this PREP
 534          * replies
 535          */
 536         dst_addr = PREP_IE_DST_ADDR(prep_elem);
 537         if (memcmp(dst_addr, sdata->dev->dev_addr, ETH_ALEN) == 0)
 538                 /* destination, no forwarding required */
 539                 return;
 540
 541         ttl = PREP_IE_TTL(prep_elem);
 542         if (ttl <= 1) {
 543                 sdata->u.mesh.mshstats.dropped_frames_ttl++;
 544                 return;
 545         }
 546
 547         rcu_read_lock();
 548         mpath = mesh_path_lookup(dst_addr, sdata);
 549         if (mpath)
 550                 spin_lock_bh(&mpath->state_lock);
 551         else
 552                 goto fail;
 553         if (!(mpath->flags & MESH_PATH_ACTIVE)) {
 554                 spin_unlock_bh(&mpath->state_lock);
 555                 goto fail;
 556         }
 557         memcpy(next_hop, mpath->next_hop->sta.addr, ETH_ALEN);
 558         spin_unlock_bh(&mpath->state_lock);
 559         --ttl;
 560         flags = PREP_IE_FLAGS(prep_elem);
 561         lifetime = PREP_IE_LIFETIME(prep_elem);
 562         hopcount = PREP_IE_HOPCOUNT(prep_elem) + 1;
 563         orig_addr = PREP_IE_ORIG_ADDR(prep_elem);
 564         dst_dsn = PREP_IE_DST_DSN(prep_elem);
 565         orig_dsn = PREP_IE_ORIG_DSN(prep_elem);
 566
 567         mesh_path_sel_frame_tx(MPATH_PREP, flags, orig_addr,
 568                 cpu_to_le32(orig_dsn), 0, dst_addr,
 569                 cpu_to_le32(dst_dsn), mpath->next_hop->sta.addr, hopcount, ttl,
 570                 cpu_to_le32(lifetime), cpu_to_le32(metric),
 571                 0, sdata);
 572         rcu_read_unlock();
 573
 574         sdata->u.mesh.mshstats.fwded_unicast++;
 575         sdata->u.mesh.mshstats.fwded_frames++;
 576         return;
 577
 578 fail:
 579         rcu_read_unlock();
 580         sdata->u.mesh.mshstats.dropped_frames_no_route++;
 581         return;
 582 }
 583
 584 static void hwmp_perr_frame_process(struct ieee80211_sub_if_data *sdata,
 585                              struct ieee80211_mgmt *mgmt, u8 *perr_elem)
 586 {
 587         struct mesh_path *mpath;
 588         u8 *ta, *dst_addr;
 589         u32 dst_dsn;
 590
 591         ta = mgmt->sa;
 592         dst_addr = PERR_IE_DST_ADDR(perr_elem);
 593         dst_dsn = PERR_IE_DST_DSN(perr_elem);
 594         rcu_read_lock();
 595         mpath = mesh_path_lookup(dst_addr, sdata);
 596         if (mpath) {
 597                 spin_lock_bh(&mpath->state_lock);
 598                 if (mpath->flags & MESH_PATH_ACTIVE &&
 599                     memcmp(ta, mpath->next_hop->sta.addr, ETH_ALEN) == 0 &&
 600                     (!(mpath->flags & MESH_PATH_DSN_VALID) ||
 601                     DSN_GT(dst_dsn, mpath->dsn))) {
 602                         mpath->flags &= ~MESH_PATH_ACTIVE;
 603                         mpath->dsn = dst_dsn;
 604                         spin_unlock_bh(&mpath->state_lock);
 605                         mesh_path_error_tx(dst_addr, cpu_to_le32(dst_dsn),
 606                                            sdata->dev->broadcast, sdata);
 607                 } else
 608                         spin_unlock_bh(&mpath->state_lock);
 609         }
 610         rcu_read_unlock();
 611 }
 612
 613
 614
 615 void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
 616                             struct ieee80211_mgmt *mgmt,
 617                             size_t len)
 618 {
 619         struct ieee802_11_elems elems;
 620         size_t baselen;
 621         u32 last_hop_metric;
 622
 623         /* need action_code */
 624         if (len < IEEE80211_MIN_ACTION_SIZE + 1)
 625                 return;
 626
 627         baselen = (u8 *) mgmt->u.action.u.mesh_action.variable - (u8 *) mgmt;
 628         ieee802_11_parse_elems(mgmt->u.action.u.mesh_action.variable,
 629                         len - baselen, &elems);
 630
 631         mhwmp_dbg("RX path selection frame\n");
 632         if (elems.preq) {
 633                 if (elems.preq_len != 37)
 634                         /* Right now we support just 1 destination and no AE */
 635                         return;
 636                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.preq,
 637                                                       MPATH_PREQ);
 638                 if (last_hop_metric)
 639                         hwmp_preq_frame_process(sdata, mgmt, elems.preq,
 640                                                 last_hop_metric);
 641         }
 642         if (elems.prep) {
 643                 if (elems.prep_len != 31)
 644                         /* Right now we support no AE */
 645                         return;
 646                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.prep,
 647                                                       MPATH_PREP);
 648                 if (last_hop_metric)
 649                         hwmp_prep_frame_process(sdata, mgmt, elems.prep,
 650                                                 last_hop_metric);
 651         }
 652         if (elems.perr) {
 653                 if (elems.perr_len != 12)
 654                         /* Right now we support only one destination per PERR */
 655                         return;
 656                 hwmp_perr_frame_process(sdata, mgmt, elems.perr);
 657         }
 658
 659 }
 660
 661 /**
 662  * mesh_queue_preq - queue a PREQ to a given destination
 663  *
 664  * @mpath: mesh path to discover
 665  * @flags: special attributes of the PREQ to be sent
 666  *
 667  * Locking: the function must be called from within a rcu read lock block.
 668  *
 669  */
 670 static void mesh_queue_preq(struct mesh_path *mpath, u8 flags)
 671 {
 672         struct ieee80211_sub_if_data *sdata = mpath->sdata;
 673         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 674         struct mesh_preq_queue *preq_node;
 675
 676         preq_node = kmalloc(sizeof(struct mesh_preq_queue), GFP_ATOMIC);
 677         if (!preq_node) {
 678                 mhwmp_dbg("could not allocate PREQ node\n");
 679                 return;
 680         }
 681
 682         spin_lock(&ifmsh->mesh_preq_queue_lock);
 683         if (ifmsh->preq_queue_len == MAX_PREQ_QUEUE_LEN) {
 684                 spin_unlock(&ifmsh->mesh_preq_queue_lock);
 685                 kfree(preq_node);
 686                 if (printk_ratelimit())
 687                         mhwmp_dbg("PREQ node queue full\n");
 688                 return;
 689         }
 690
 691         memcpy(preq_node->dst, mpath->dst, ETH_ALEN);
 692         preq_node->flags = flags;
 693
 694         list_add_tail(&preq_node->list, &ifmsh->preq_queue.list);
 695         ++ifmsh->preq_queue_len;
 696         spin_unlock(&ifmsh->mesh_preq_queue_lock);
 697
 698         if (time_after(jiffies, ifmsh->last_preq + min_preq_int_jiff(sdata)))
 699                 ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
 700
 701         else if (time_before(jiffies, ifmsh->last_preq)) {
 702                 /* avoid long wait if did not send preqs for a long time
 703                  * and jiffies wrapped around
 704                  */
 705                 ifmsh->last_preq = jiffies - min_preq_int_jiff(sdata) - 1;
 706                 ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
 707         } else
 708                 mod_timer(&ifmsh->mesh_path_timer, ifmsh->last_preq +
 709                                                 min_preq_int_jiff(sdata));
 710 }
 711
 712 /**
 713  * mesh_path_start_discovery - launch a path discovery from the PREQ queue
 714  *
 715  * @sdata: local mesh subif
 716  */
 717 void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata)
 718 {
 719         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 720         struct mesh_preq_queue *preq_node;
 721         struct mesh_path *mpath;
 722         u8 ttl, dst_flags;
 723         u32 lifetime;
 724
 725         spin_lock_bh(&ifmsh->mesh_preq_queue_lock);
 726         if (!ifmsh->preq_queue_len ||
 727                 time_before(jiffies, ifmsh->last_preq +
 728                                 min_preq_int_jiff(sdata))) {
 729                 spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 730                 return;
 731         }
 732
 733         preq_node = list_first_entry(&ifmsh->preq_queue.list,
 734                         struct mesh_preq_queue, list);
 735         list_del(&preq_node->list);
 736         --ifmsh->preq_queue_len;
 737         spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 738
 739         rcu_read_lock();
 740         mpath = mesh_path_lookup(preq_node->dst, sdata);
 741         if (!mpath)
 742                 goto enddiscovery;
 743
 744         spin_lock_bh(&mpath->state_lock);
 745         if (preq_node->flags & PREQ_Q_F_START) {
 746                 if (mpath->flags & MESH_PATH_RESOLVING) {
 747                         spin_unlock_bh(&mpath->state_lock);
 748                         goto enddiscovery;
 749                 } else {
 750                         mpath->flags &= ~MESH_PATH_RESOLVED;
 751                         mpath->flags |= MESH_PATH_RESOLVING;
 752                         mpath->discovery_retries = 0;
 753                         mpath->discovery_timeout = disc_timeout_jiff(sdata);
 754                 }
 755         } else if (!(mpath->flags & MESH_PATH_RESOLVING) ||
 756                         mpath->flags & MESH_PATH_RESOLVED) {
 757                 mpath->flags &= ~MESH_PATH_RESOLVING;
 758                 spin_unlock_bh(&mpath->state_lock);
 759                 goto enddiscovery;
 760         }
 761
 762         ifmsh->last_preq = jiffies;
 763
 764         if (time_after(jiffies, ifmsh->last_dsn_update +
 765                                 net_traversal_jiffies(sdata)) ||
 766             time_before(jiffies, ifmsh->last_dsn_update)) {
 767                 ++ifmsh->dsn;
 768                 sdata->u.mesh.last_dsn_update = jiffies;
 769         }
 770         lifetime = default_lifetime(sdata);
 771         ttl = sdata->u.mesh.mshcfg.dot11MeshTTL;
 772         if (ttl == 0) {
 773                 sdata->u.mesh.mshstats.dropped_frames_ttl++;
 774                 spin_unlock_bh(&mpath->state_lock);
 775                 goto enddiscovery;
 776         }
 777
 778         if (preq_node->flags & PREQ_Q_F_REFRESH)
 779                 dst_flags = MP_F_DO;
 780         else
 781                 dst_flags = MP_F_RF;
 782
 783         spin_unlock_bh(&mpath->state_lock);
 784         mesh_path_sel_frame_tx(MPATH_PREQ, 0, sdata->dev->dev_addr,
 785                         cpu_to_le32(ifmsh->dsn), dst_flags, mpath->dst,
 786                         cpu_to_le32(mpath->dsn), sdata->dev->broadcast, 0,
 787                         ttl, cpu_to_le32(lifetime), 0,
 788                         cpu_to_le32(ifmsh->preq_id++), sdata);
 789         mod_timer(&mpath->timer, jiffies + mpath->discovery_timeout);
 790
 791 enddiscovery:
 792         rcu_read_unlock();
 793         kfree(preq_node);
 794 }
 795
 796 /**
 797  * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
 798  *
 799  * @skb: 802.11 frame to be sent
 800  * @sdata: network subif the frame will be sent through
 801  *
 802  * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
 803  * found, the function will start a path discovery and queue the frame so it is
 804  * sent when the path is resolved. This means the caller must not free the skb
 805  * in this case.
 806  */
 807 int mesh_nexthop_lookup(struct sk_buff *skb,
 808                         struct ieee80211_sub_if_data *sdata)
 809 {
 810         struct sk_buff *skb_to_free = NULL;
 811         struct mesh_path *mpath;
 812         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
 813         u8 *dst_addr = hdr->addr3;
 814         int err = 0;
 815
 816         rcu_read_lock();
 817         mpath = mesh_path_lookup(dst_addr, sdata);
 818
 819         if (!mpath) {
 820                 mesh_path_add(dst_addr, sdata);
 821                 mpath = mesh_path_lookup(dst_addr, sdata);
 822                 if (!mpath) {
 823                         sdata->u.mesh.mshstats.dropped_frames_no_route++;
 824                         err = -ENOSPC;
 825                         goto endlookup;
 826                 }
 827         }
 828
 829         if (mpath->flags & MESH_PATH_ACTIVE) {
 830                 if (time_after(jiffies, mpath->exp_time +
 831                         msecs_to_jiffies(sdata->u.mesh.mshcfg.path_refresh_time))
 832                                 && !memcmp(sdata->dev->dev_addr, hdr->addr4,
 833                                            ETH_ALEN)
 834                                 && !(mpath->flags & MESH_PATH_RESOLVING)
 835                                 && !(mpath->flags & MESH_PATH_FIXED)) {
 836                         mesh_queue_preq(mpath,
 837                                         PREQ_Q_F_START | PREQ_Q_F_REFRESH);
 838                 }
 839                 memcpy(hdr->addr1, mpath->next_hop->sta.addr,
 840                                 ETH_ALEN);
 841         } else {
 842                 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
 843                 if (!(mpath->flags & MESH_PATH_RESOLVING)) {
 844                         /* Start discovery only if it is not running yet */
 845                         mesh_queue_preq(mpath, PREQ_Q_F_START);
 846                 }
 847
 848                 if (skb_queue_len(&mpath->frame_queue) >=
 849                                 MESH_FRAME_QUEUE_LEN)
 850                         skb_to_free = skb_dequeue(&mpath->frame_queue);
 851
 852                 info->flags |= IEEE80211_TX_INTFL_NEED_TXPROCESSING;
 853                 skb_queue_tail(&mpath->frame_queue, skb);
 854                 if (skb_to_free)
 855                         mesh_path_discard_frame(skb_to_free, sdata);
 856                 err = -ENOENT;
 857         }
 858
 859 endlookup:
 860         rcu_read_unlock();
 861         return err;
 862 }
 863
 864 void mesh_path_timer(unsigned long data)
 865 {
 866         struct ieee80211_sub_if_data *sdata;
 867         struct mesh_path *mpath;
 868
 869         rcu_read_lock();
 870         mpath = (struct mesh_path *) data;
 871         mpath = rcu_dereference(mpath);
 872         if (!mpath)
 873                 goto endmpathtimer;
 874         sdata = mpath->sdata;
 875
 876         if (sdata->local->quiescing) {
 877                 rcu_read_unlock();
 878                 return;
 879         }
 880
 881         spin_lock_bh(&mpath->state_lock);
 882         if (mpath->flags & MESH_PATH_RESOLVED ||
 883                         (!(mpath->flags & MESH_PATH_RESOLVING)))
 884                 mpath->flags &= ~(MESH_PATH_RESOLVING | MESH_PATH_RESOLVED);
 885         else if (mpath->discovery_retries < max_preq_retries(sdata)) {
 886                 ++mpath->discovery_retries;
 887                 mpath->discovery_timeout *= 2;
 888                 mesh_queue_preq(mpath, 0);
 889         } else {
 890                 mpath->flags = 0;
 891                 mpath->exp_time = jiffies;
 892                 mesh_path_flush_pending(mpath);
 893         }
 894
 895         spin_unlock_bh(&mpath->state_lock);
 896 endmpathtimer:
 897         rcu_read_unlock();
 898 }