net/mac80211/mesh.c

   1 /*
   2  * Copyright (c) 2008 open80211s Ltd.
   3  * Authors:    Luis Carlos Cobo <luisca@cozybit.com>
   4  *             Javier Cardona <javier@cozybit.com>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 as
   8  * published by the Free Software Foundation.
   9  */
  10
  11 #include "ieee80211_i.h"
  12 #include "mesh.h"
  13
  14 #define ACCEPT_PLINKS 0x80
  15
  16 int mesh_allocated;
  17 static struct kmem_cache *rm_cache;
  18
  19 void ieee80211s_init(void)
  20 {
  21         mesh_pathtbl_init();
  22         mesh_allocated = 1;
  23         rm_cache = kmem_cache_create("mesh_rmc", sizeof(struct rmc_entry),
  24                                      0, 0, NULL);
  25 }
  26
  27 void ieee80211s_stop(void)
  28 {
  29         mesh_pathtbl_unregister();
  30         kmem_cache_destroy(rm_cache);
  31 }
  32
  33 /**
  34  * mesh_matches_local - check if the config of a mesh point matches ours
  35  *
  36  * @ie: information elements of a management frame from the mesh peer
  37  * @dev: local mesh interface
  38  *
  39  * This function checks if the mesh configuration of a mesh point matches the
  40  * local mesh configuration, i.e. if both nodes belong to the same mesh network.
  41  */
  42 bool mesh_matches_local(struct ieee802_11_elems *ie, struct net_device *dev)
  43 {
  44         struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
  45         struct ieee80211_if_sta *sta = &sdata->u.sta;
  46
  47         /*
  48          * As support for each feature is added, check for matching
  49          * - On mesh config capabilities
  50          *   - Power Save Support En
  51          *   - Sync support enabled
  52          *   - Sync support active
  53          *   - Sync support required from peer
  54          *   - MDA enabled
  55          * - Power management control on fc
  56          */
  57         if (sta->mesh_id_len == ie->mesh_id_len &&
  58                 memcmp(sta->mesh_id, ie->mesh_id, ie->mesh_id_len) == 0 &&
  59                 memcmp(sta->mesh_pp_id, ie->mesh_config + PP_OFFSET, 4) == 0 &&
  60                 memcmp(sta->mesh_pm_id, ie->mesh_config + PM_OFFSET, 4) == 0 &&
  61                 memcmp(sta->mesh_cc_id, ie->mesh_config + CC_OFFSET, 4) == 0)
  62                 return true;
  63
  64         return false;
  65 }
  66
  67 /**
  68  * mesh_peer_accepts_plinks - check if an mp is willing to establish peer links
  69  *
  70  * @ie: information elements of a management frame from the mesh peer
  71  * @dev: local mesh interface
  72  */
  73 bool mesh_peer_accepts_plinks(struct ieee802_11_elems *ie,
  74                               struct net_device *dev)
  75 {
  76         return (*(ie->mesh_config + CAPAB_OFFSET) & ACCEPT_PLINKS) != 0;
  77 }
  78
  79 /**
  80  * mesh_accept_plinks_update: update accepting_plink in local mesh beacons
  81  *
  82  * @sdata: mesh interface in which mesh beacons are going to be updated
  83  */
  84 void mesh_accept_plinks_update(struct ieee80211_sub_if_data *sdata)
  85 {
  86         bool free_plinks;
  87
  88         /* In case mesh_plink_free_count > 0 and mesh_plinktbl_capacity == 0,
  89          * the mesh interface might be able to establish plinks with peers that
  90          * are already on the table but are not on PLINK_ESTAB state. However,
  91          * in general the mesh interface is not accepting peer link requests
  92          * from new peers, and that must be reflected in the beacon
  93          */
  94         free_plinks = mesh_plink_availables(sdata);
  95
  96         if (free_plinks != sdata->u.sta.accepting_plinks)
  97                 ieee80211_sta_timer((unsigned long) sdata);
  98 }
  99
 100 void mesh_ids_set_default(struct ieee80211_if_sta *sta)
 101 {
 102         u8 def_id[4] = {0x00, 0x0F, 0xAC, 0xff};
 103
 104         memcpy(sta->mesh_pp_id, def_id, 4);
 105         memcpy(sta->mesh_pm_id, def_id, 4);
 106         memcpy(sta->mesh_cc_id, def_id, 4);
 107 }
 108
 109 int mesh_rmc_init(struct net_device *dev)
 110 {
 111         struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
 112         int i;
 113
 114         sdata->u.sta.rmc = kmalloc(sizeof(struct mesh_rmc), GFP_KERNEL);
 115         if (!sdata->u.sta.rmc)
 116                 return -ENOMEM;
 117         sdata->u.sta.rmc->idx_mask = RMC_BUCKETS - 1;
 118         for (i = 0; i < RMC_BUCKETS; i++)
 119                 INIT_LIST_HEAD(&sdata->u.sta.rmc->bucket[i].list);
 120         return 0;
 121 }
 122
 123 void mesh_rmc_free(struct net_device *dev)
 124 {
 125         struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
 126         struct mesh_rmc *rmc = sdata->u.sta.rmc;
 127         struct rmc_entry *p, *n;
 128         int i;
 129
 130         if (!sdata->u.sta.rmc)
 131                 return;
 132
 133         for (i = 0; i < RMC_BUCKETS; i++)
 134                 list_for_each_entry_safe(p, n, &rmc->bucket[i].list, list) {
 135                         list_del(&p->list);
 136                         kmem_cache_free(rm_cache, p);
 137                 }
 138
 139         kfree(rmc);
 140         sdata->u.sta.rmc = NULL;
 141 }
 142
 143 /**
 144  * mesh_rmc_check - Check frame in recent multicast cache and add if absent.
 145  *
 146  * @sa:         source address
 147  * @mesh_hdr:   mesh_header
 148  *
 149  * Returns: 0 if the frame is not in the cache, nonzero otherwise.
 150  *
 151  * Checks using the source address and the mesh sequence number if we have
 152  * received this frame lately. If the frame is not in the cache, it is added to
 153  * it.
 154  */
 155 int mesh_rmc_check(u8 *sa, struct ieee80211s_hdr *mesh_hdr,
 156                    struct net_device *dev)
 157 {
 158         struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
 159         struct mesh_rmc *rmc = sdata->u.sta.rmc;
 160         u32 seqnum = 0;
 161         int entries = 0;
 162         u8 idx;
 163         struct rmc_entry *p, *n;
 164
 165         /* Don't care about endianness since only match matters */
 166         memcpy(&seqnum, mesh_hdr->seqnum, sizeof(mesh_hdr->seqnum));
 167         idx = mesh_hdr->seqnum[0] & rmc->idx_mask;
 168         list_for_each_entry_safe(p, n, &rmc->bucket[idx].list, list) {
 169                 ++entries;
 170                 if (time_after(jiffies, p->exp_time) ||
 171                                 (entries == RMC_QUEUE_MAX_LEN)) {
 172                         list_del(&p->list);
 173                         kmem_cache_free(rm_cache, p);
 174                         --entries;
 175                 } else if ((seqnum == p->seqnum)
 176                                 && (memcmp(sa, p->sa, ETH_ALEN) == 0))
 177                         return -1;
 178         }
 179
 180         p = kmem_cache_alloc(rm_cache, GFP_ATOMIC);
 181         if (!p) {
 182                 printk(KERN_DEBUG "o11s: could not allocate RMC entry\n");
 183                 return 0;
 184         }
 185         p->seqnum = seqnum;
 186         p->exp_time = jiffies + RMC_TIMEOUT;
 187         memcpy(p->sa, sa, ETH_ALEN);
 188         list_add(&p->list, &rmc->bucket[idx].list);
 189         return 0;
 190 }
 191
 192 void mesh_mgmt_ies_add(struct sk_buff *skb, struct net_device *dev)
 193 {
 194         struct ieee80211_local *local = wdev_priv(dev->ieee80211_ptr);
 195         struct ieee80211_sub_if_data *sdata = IEEE80211_DEV_TO_SUB_IF(dev);
 196         struct ieee80211_supported_band *sband;
 197         u8 *pos;
 198         int len, i, rate;
 199
 200         sband = local->hw.wiphy->bands[local->hw.conf.channel->band];
 201         len = sband->n_bitrates;
 202         if (len > 8)
 203                 len = 8;
 204         pos = skb_put(skb, len + 2);
 205         *pos++ = WLAN_EID_SUPP_RATES;
 206         *pos++ = len;
 207         for (i = 0; i < len; i++) {
 208                 rate = sband->bitrates[i].bitrate;
 209                 *pos++ = (u8) (rate / 5);
 210         }
 211
 212         if (sband->n_bitrates > len) {
 213                 pos = skb_put(skb, sband->n_bitrates - len + 2);
 214                 *pos++ = WLAN_EID_EXT_SUPP_RATES;
 215                 *pos++ = sband->n_bitrates - len;
 216                 for (i = len; i < sband->n_bitrates; i++) {
 217                         rate = sband->bitrates[i].bitrate;
 218                         *pos++ = (u8) (rate / 5);
 219                 }
 220         }
 221
 222         pos = skb_put(skb, 2 + sdata->u.sta.mesh_id_len);
 223         *pos++ = WLAN_EID_MESH_ID;
 224         *pos++ = sdata->u.sta.mesh_id_len;
 225         if (sdata->u.sta.mesh_id_len)
 226                 memcpy(pos, sdata->u.sta.mesh_id, sdata->u.sta.mesh_id_len);
 227
 228         pos = skb_put(skb, 21);
 229         *pos++ = WLAN_EID_MESH_CONFIG;
 230         *pos++ = MESH_CFG_LEN;
 231         /* Version */
 232         *pos++ = 1;
 233
 234         /* Active path selection protocol ID */
 235         memcpy(pos, sdata->u.sta.mesh_pp_id, 4);
 236         pos += 4;
 237
 238         /* Active path selection metric ID   */
 239         memcpy(pos, sdata->u.sta.mesh_pm_id, 4);
 240         pos += 4;
 241
 242         /* Congestion control mode identifier */
 243         memcpy(pos, sdata->u.sta.mesh_cc_id, 4);
 244         pos += 4;
 245
 246         /* Channel precedence:
 247          * Not running simple channel unification protocol
 248          */
 249         memset(pos, 0x00, 4);
 250         pos += 4;
 251
 252         /* Mesh capability */
 253         sdata->u.sta.accepting_plinks = mesh_plink_availables(sdata);
 254         *pos++ = sdata->u.sta.accepting_plinks ? ACCEPT_PLINKS : 0x00;
 255         *pos++ = 0x00;
 256
 257         return;
 258 }
 259
 260 u32 mesh_table_hash(u8 *addr, struct net_device *dev, struct mesh_table *tbl)
 261 {
 262         /* Use last four bytes of hw addr and interface index as hash index */
 263         return jhash_2words(*(u32 *)(addr+2), dev->ifindex, tbl->hash_rnd)
 264                 & tbl->hash_mask;
 265 }
 266
 267 u8 mesh_id_hash(u8 *mesh_id, int mesh_id_len)
 268 {
 269         if (!mesh_id_len)
 270                 return 1;
 271         else if (mesh_id_len == 1)
 272                 return (u8) mesh_id[0];
 273         else
 274                 return (u8) (mesh_id[0] + 2 * mesh_id[1]);
 275 }
 276
 277 struct mesh_table *mesh_table_alloc(int size_order)
 278 {
 279         int i;
 280         struct mesh_table *newtbl;
 281
 282         newtbl = kmalloc(sizeof(struct mesh_table), GFP_KERNEL);
 283         if (!newtbl)
 284                 return NULL;
 285
 286         newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) *
 287                         (1 << size_order), GFP_KERNEL);
 288
 289         if (!newtbl->hash_buckets) {
 290                 kfree(newtbl);
 291                 return NULL;
 292         }
 293
 294         newtbl->hashwlock = kmalloc(sizeof(spinlock_t) *
 295                         (1 << size_order), GFP_KERNEL);
 296         if (!newtbl->hashwlock) {
 297                 kfree(newtbl->hash_buckets);
 298                 kfree(newtbl);
 299                 return NULL;
 300         }
 301
 302         newtbl->size_order = size_order;
 303         newtbl->hash_mask = (1 << size_order) - 1;
 304         atomic_set(&newtbl->entries,  0);
 305         get_random_bytes(&newtbl->hash_rnd,
 306                         sizeof(newtbl->hash_rnd));
 307         for (i = 0; i <= newtbl->hash_mask; i++)
 308                 spin_lock_init(&newtbl->hashwlock[i]);
 309
 310         return newtbl;
 311 }
 312
 313 void mesh_table_free(struct mesh_table *tbl, bool free_leafs)
 314 {
 315         struct hlist_head *mesh_hash;
 316         struct hlist_node *p, *q;
 317         int i;
 318
 319         mesh_hash = tbl->hash_buckets;
 320         for (i = 0; i <= tbl->hash_mask; i++) {
 321                 spin_lock(&tbl->hashwlock[i]);
 322                 hlist_for_each_safe(p, q, &mesh_hash[i]) {
 323                         tbl->free_node(p, free_leafs);
 324                         atomic_dec(&tbl->entries);
 325                 }
 326                 spin_unlock(&tbl->hashwlock[i]);
 327         }
 328         kfree(tbl->hash_buckets);
 329         kfree(tbl->hashwlock);
 330         kfree(tbl);
 331 }
 332
 333 static void ieee80211_mesh_path_timer(unsigned long data)
 334 {
 335         struct ieee80211_sub_if_data *sdata =
 336                 (struct ieee80211_sub_if_data *) data;
 337         struct ieee80211_if_sta *ifsta = &sdata->u.sta;
 338         struct ieee80211_local *local = wdev_priv(&sdata->wdev);
 339
 340         queue_work(local->hw.workqueue, &ifsta->work);
 341 }
 342
 343 struct mesh_table *mesh_table_grow(struct mesh_table *tbl)
 344 {
 345         struct mesh_table *newtbl;
 346         struct hlist_head *oldhash;
 347         struct hlist_node *p;
 348         int err = 0;
 349         int i;
 350
 351         if (atomic_read(&tbl->entries)
 352                         < tbl->mean_chain_len * (tbl->hash_mask + 1)) {
 353                 err = -EPERM;
 354                 goto endgrow;
 355         }
 356
 357         newtbl = mesh_table_alloc(tbl->size_order + 1);
 358         if (!newtbl) {
 359                 err = -ENOMEM;
 360                 goto endgrow;
 361         }
 362
 363         newtbl->free_node = tbl->free_node;
 364         newtbl->mean_chain_len = tbl->mean_chain_len;
 365         newtbl->copy_node = tbl->copy_node;
 366         atomic_set(&newtbl->entries, atomic_read(&tbl->entries));
 367
 368         oldhash = tbl->hash_buckets;
 369         for (i = 0; i <= tbl->hash_mask; i++)
 370                 hlist_for_each(p, &oldhash[i])
 371                         tbl->copy_node(p, newtbl);
 372
 373 endgrow:
 374         if (err)
 375                 return NULL;
 376         else
 377                 return newtbl;
 378 }
 379
 380 /**
 381  * ieee80211_new_mesh_header - create a new mesh header
 382  * @meshhdr:    uninitialized mesh header
 383  * @sdata:      mesh interface to be used
 384  *
 385  * Return the header length.
 386  */
 387 int ieee80211_new_mesh_header(struct ieee80211s_hdr *meshhdr,
 388                 struct ieee80211_sub_if_data *sdata)
 389 {
 390         meshhdr->flags = 0;
 391         meshhdr->ttl = sdata->u.sta.mshcfg.dot11MeshTTL;
 392
 393         meshhdr->seqnum[0] = sdata->u.sta.mesh_seqnum[0]++;
 394         meshhdr->seqnum[1] = sdata->u.sta.mesh_seqnum[1];
 395         meshhdr->seqnum[2] = sdata->u.sta.mesh_seqnum[2];
 396
 397         if (sdata->u.sta.mesh_seqnum[0] == 0) {
 398                 sdata->u.sta.mesh_seqnum[1]++;
 399                 if (sdata->u.sta.mesh_seqnum[1] == 0)
 400                         sdata->u.sta.mesh_seqnum[2]++;
 401         }
 402
 403         return 5;
 404 }
 405
 406 void ieee80211_mesh_init_sdata(struct ieee80211_sub_if_data *sdata)
 407 {
 408         struct ieee80211_if_sta *ifsta = &sdata->u.sta;
 409
 410         ifsta->mshcfg.dot11MeshRetryTimeout = MESH_RET_T;
 411         ifsta->mshcfg.dot11MeshConfirmTimeout = MESH_CONF_T;
 412         ifsta->mshcfg.dot11MeshHoldingTimeout = MESH_HOLD_T;
 413         ifsta->mshcfg.dot11MeshMaxRetries = MESH_MAX_RETR;
 414         ifsta->mshcfg.dot11MeshTTL = MESH_TTL;
 415         ifsta->mshcfg.auto_open_plinks = true;
 416         ifsta->mshcfg.dot11MeshMaxPeerLinks =
 417                 MESH_MAX_ESTAB_PLINKS;
 418         ifsta->mshcfg.dot11MeshHWMPactivePathTimeout =
 419                 MESH_PATH_TIMEOUT;
 420         ifsta->mshcfg.dot11MeshHWMPpreqMinInterval =
 421                 MESH_PREQ_MIN_INT;
 422         ifsta->mshcfg.dot11MeshHWMPnetDiameterTraversalTime =
 423                 MESH_DIAM_TRAVERSAL_TIME;
 424         ifsta->mshcfg.dot11MeshHWMPmaxPREQretries =
 425                 MESH_MAX_PREQ_RETRIES;
 426         ifsta->mshcfg.path_refresh_time =
 427                 MESH_PATH_REFRESH_TIME;
 428         ifsta->mshcfg.min_discovery_timeout =
 429                 MESH_MIN_DISCOVERY_TIMEOUT;
 430         ifsta->accepting_plinks = true;
 431         ifsta->preq_id = 0;
 432         ifsta->dsn = 0;
 433         atomic_set(&ifsta->mpaths, 0);
 434         mesh_rmc_init(sdata->dev);
 435         ifsta->last_preq = jiffies;
 436         /* Allocate all mesh structures when creating the first mesh interface. */
 437         if (!mesh_allocated)
 438                 ieee80211s_init();
 439         mesh_ids_set_default(ifsta);
 440         setup_timer(&ifsta->mesh_path_timer,
 441                     ieee80211_mesh_path_timer,
 442                     (unsigned long) sdata);
 443         INIT_LIST_HEAD(&ifsta->preq_queue.list);
 444         spin_lock_init(&ifsta->mesh_preq_queue_lock);
 445 }