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