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 to %pM\n", dst);
 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 to %pM\n", dst);
 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 from %pM\n", orig_addr);
 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 from %pM\n", orig_addr);
 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 from %pM\n", PREP_IE_ORIG_ADDR(prep_elem));
 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         if (elems.preq) {
 632                 if (elems.preq_len != 37)
 633                         /* Right now we support just 1 destination and no AE */
 634                         return;
 635                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.preq,
 636                                                       MPATH_PREQ);
 637                 if (last_hop_metric)
 638                         hwmp_preq_frame_process(sdata, mgmt, elems.preq,
 639                                                 last_hop_metric);
 640         }
 641         if (elems.prep) {
 642                 if (elems.prep_len != 31)
 643                         /* Right now we support no AE */
 644                         return;
 645                 last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.prep,
 646                                                       MPATH_PREP);
 647                 if (last_hop_metric)
 648                         hwmp_prep_frame_process(sdata, mgmt, elems.prep,
 649                                                 last_hop_metric);
 650         }
 651         if (elems.perr) {
 652                 if (elems.perr_len != 12)
 653                         /* Right now we support only one destination per PERR */
 654                         return;
 655                 hwmp_perr_frame_process(sdata, mgmt, elems.perr);
 656         }
 657
 658 }
 659
 660 /**
 661  * mesh_queue_preq - queue a PREQ to a given destination
 662  *
 663  * @mpath: mesh path to discover
 664  * @flags: special attributes of the PREQ to be sent
 665  *
 666  * Locking: the function must be called from within a rcu read lock block.
 667  *
 668  */
 669 static void mesh_queue_preq(struct mesh_path *mpath, u8 flags)
 670 {
 671         struct ieee80211_sub_if_data *sdata = mpath->sdata;
 672         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 673         struct mesh_preq_queue *preq_node;
 674
 675         preq_node = kmalloc(sizeof(struct mesh_preq_queue), GFP_ATOMIC);
 676         if (!preq_node) {
 677                 mhwmp_dbg("could not allocate PREQ node\n");
 678                 return;
 679         }
 680
 681         spin_lock(&ifmsh->mesh_preq_queue_lock);
 682         if (ifmsh->preq_queue_len == MAX_PREQ_QUEUE_LEN) {
 683                 spin_unlock(&ifmsh->mesh_preq_queue_lock);
 684                 kfree(preq_node);
 685                 if (printk_ratelimit())
 686                         mhwmp_dbg("PREQ node queue full\n");
 687                 return;
 688         }
 689
 690         memcpy(preq_node->dst, mpath->dst, ETH_ALEN);
 691         preq_node->flags = flags;
 692
 693         list_add_tail(&preq_node->list, &ifmsh->preq_queue.list);
 694         ++ifmsh->preq_queue_len;
 695         spin_unlock(&ifmsh->mesh_preq_queue_lock);
 696
 697         if (time_after(jiffies, ifmsh->last_preq + min_preq_int_jiff(sdata)))
 698                 ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
 699
 700         else if (time_before(jiffies, ifmsh->last_preq)) {
 701                 /* avoid long wait if did not send preqs for a long time
 702                  * and jiffies wrapped around
 703                  */
 704                 ifmsh->last_preq = jiffies - min_preq_int_jiff(sdata) - 1;
 705                 ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
 706         } else
 707                 mod_timer(&ifmsh->mesh_path_timer, ifmsh->last_preq +
 708                                                 min_preq_int_jiff(sdata));
 709 }
 710
 711 /**
 712  * mesh_path_start_discovery - launch a path discovery from the PREQ queue
 713  *
 714  * @sdata: local mesh subif
 715  */
 716 void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata)
 717 {
 718         struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
 719         struct mesh_preq_queue *preq_node;
 720         struct mesh_path *mpath;
 721         u8 ttl, dst_flags;
 722         u32 lifetime;
 723
 724         spin_lock_bh(&ifmsh->mesh_preq_queue_lock);
 725         if (!ifmsh->preq_queue_len ||
 726                 time_before(jiffies, ifmsh->last_preq +
 727                                 min_preq_int_jiff(sdata))) {
 728                 spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 729                 return;
 730         }
 731
 732         preq_node = list_first_entry(&ifmsh->preq_queue.list,
 733                         struct mesh_preq_queue, list);
 734         list_del(&preq_node->list);
 735         --ifmsh->preq_queue_len;
 736         spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
 737
 738         rcu_read_lock();
 739         mpath = mesh_path_lookup(preq_node->dst, sdata);
 740         if (!mpath)
 741                 goto enddiscovery;
 742
 743         spin_lock_bh(&mpath->state_lock);
 744         if (preq_node->flags & PREQ_Q_F_START) {
 745                 if (mpath->flags & MESH_PATH_RESOLVING) {
 746                         spin_unlock_bh(&mpath->state_lock);
 747                         goto enddiscovery;
 748                 } else {
 749                         mpath->flags &= ~MESH_PATH_RESOLVED;
 750                         mpath->flags |= MESH_PATH_RESOLVING;
 751                         mpath->discovery_retries = 0;
 752                         mpath->discovery_timeout = disc_timeout_jiff(sdata);
 753                 }
 754         } else if (!(mpath->flags & MESH_PATH_RESOLVING) ||
 755                         mpath->flags & MESH_PATH_RESOLVED) {
 756                 mpath->flags &= ~MESH_PATH_RESOLVING;
 757                 spin_unlock_bh(&mpath->state_lock);
 758                 goto enddiscovery;
 759         }
 760
 761         ifmsh->last_preq = jiffies;
 762
 763         if (time_after(jiffies, ifmsh->last_dsn_update +
 764                                 net_traversal_jiffies(sdata)) ||
 765             time_before(jiffies, ifmsh->last_dsn_update)) {
 766                 ++ifmsh->dsn;
 767                 sdata->u.mesh.last_dsn_update = jiffies;
 768         }
 769         lifetime = default_lifetime(sdata);
 770         ttl = sdata->u.mesh.mshcfg.dot11MeshTTL;
 771         if (ttl == 0) {
 772                 sdata->u.mesh.mshstats.dropped_frames_ttl++;
 773                 spin_unlock_bh(&mpath->state_lock);
 774                 goto enddiscovery;
 775         }
 776
 777         if (preq_node->flags & PREQ_Q_F_REFRESH)
 778                 dst_flags = MP_F_DO;
 779         else
 780                 dst_flags = MP_F_RF;
 781
 782         spin_unlock_bh(&mpath->state_lock);
 783         mesh_path_sel_frame_tx(MPATH_PREQ, 0, sdata->dev->dev_addr,
 784                         cpu_to_le32(ifmsh->dsn), dst_flags, mpath->dst,
 785                         cpu_to_le32(mpath->dsn), sdata->dev->broadcast, 0,
 786                         ttl, cpu_to_le32(lifetime), 0,
 787                         cpu_to_le32(ifmsh->preq_id++), sdata);
 788         mod_timer(&mpath->timer, jiffies + mpath->discovery_timeout);
 789
 790 enddiscovery:
 791         rcu_read_unlock();
 792         kfree(preq_node);
 793 }
 794
 795 /**
 796  * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
 797  *
 798  * @skb: 802.11 frame to be sent
 799  * @sdata: network subif the frame will be sent through
 800  *
 801  * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
 802  * found, the function will start a path discovery and queue the frame so it is
 803  * sent when the path is resolved. This means the caller must not free the skb
 804  * in this case.
 805  */
 806 int mesh_nexthop_lookup(struct sk_buff *skb,
 807                         struct ieee80211_sub_if_data *sdata)
 808 {
 809         struct sk_buff *skb_to_free = NULL;
 810         struct mesh_path *mpath;
 811         struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
 812         u8 *dst_addr = hdr->addr3;
 813         int err = 0;
 814
 815         rcu_read_lock();
 816         mpath = mesh_path_lookup(dst_addr, sdata);
 817
 818         if (!mpath) {
 819                 mesh_path_add(dst_addr, sdata);
 820                 mpath = mesh_path_lookup(dst_addr, sdata);
 821                 if (!mpath) {
 822                         sdata->u.mesh.mshstats.dropped_frames_no_route++;
 823                         err = -ENOSPC;
 824                         goto endlookup;
 825                 }
 826         }
 827
 828         if (mpath->flags & MESH_PATH_ACTIVE) {
 829                 if (time_after(jiffies, mpath->exp_time +
 830                         msecs_to_jiffies(sdata->u.mesh.mshcfg.path_refresh_time))
 831                                 && !memcmp(sdata->dev->dev_addr, hdr->addr4,
 832                                            ETH_ALEN)
 833                                 && !(mpath->flags & MESH_PATH_RESOLVING)
 834                                 && !(mpath->flags & MESH_PATH_FIXED)) {
 835                         mesh_queue_preq(mpath,
 836                                         PREQ_Q_F_START | PREQ_Q_F_REFRESH);
 837                 }
 838                 memcpy(hdr->addr1, mpath->next_hop->sta.addr,
 839                                 ETH_ALEN);
 840         } else {
 841                 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
 842                 if (!(mpath->flags & MESH_PATH_RESOLVING)) {
 843                         /* Start discovery only if it is not running yet */
 844                         mesh_queue_preq(mpath, PREQ_Q_F_START);
 845                 }
 846
 847                 if (skb_queue_len(&mpath->frame_queue) >=
 848                                 MESH_FRAME_QUEUE_LEN)
 849                         skb_to_free = skb_dequeue(&mpath->frame_queue);
 850
 851                 info->flags |= IEEE80211_TX_INTFL_NEED_TXPROCESSING;
 852                 skb_queue_tail(&mpath->frame_queue, skb);
 853                 if (skb_to_free)
 854                         mesh_path_discard_frame(skb_to_free, sdata);
 855                 err = -ENOENT;
 856         }
 857
 858 endlookup:
 859         rcu_read_unlock();
 860         return err;
 861 }
 862
 863 void mesh_path_timer(unsigned long data)
 864 {
 865         struct ieee80211_sub_if_data *sdata;
 866         struct mesh_path *mpath;
 867
 868         rcu_read_lock();
 869         mpath = (struct mesh_path *) data;
 870         mpath = rcu_dereference(mpath);
 871         if (!mpath)
 872                 goto endmpathtimer;
 873         sdata = mpath->sdata;
 874
 875         if (sdata->local->quiescing) {
 876                 rcu_read_unlock();
 877                 return;
 878         }
 879
 880         spin_lock_bh(&mpath->state_lock);
 881         if (mpath->flags & MESH_PATH_RESOLVED ||
 882                         (!(mpath->flags & MESH_PATH_RESOLVING)))
 883                 mpath->flags &= ~(MESH_PATH_RESOLVING | MESH_PATH_RESOLVED);
 884         else if (mpath->discovery_retries < max_preq_retries(sdata)) {
 885                 ++mpath->discovery_retries;
 886                 mpath->discovery_timeout *= 2;
 887                 mesh_queue_preq(mpath, 0);
 888         } else {
 889                 mpath->flags = 0;
 890                 mpath->exp_time = jiffies;
 891                 mesh_path_flush_pending(mpath);
 892         }
 893
 894         spin_unlock_bh(&mpath->state_lock);
 895 endmpathtimer:
 896         rcu_read_unlock();
 897 }