Commit | Line | Data |
---|---|---|
2e3c8736 LCC |
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 | ||
51ceddad | 11 | #include <asm/unaligned.h> |
2e3c8736 LCC |
12 | #include "ieee80211_i.h" |
13 | #include "mesh.h" | |
14 | ||
24736701 JL |
15 | #define PP_OFFSET 1 /* Path Selection Protocol */ |
16 | #define PM_OFFSET 5 /* Path Selection Metric */ | |
17 | #define CC_OFFSET 9 /* Congestion Control Mode */ | |
18 | #define CAPAB_OFFSET 17 | |
2e3c8736 LCC |
19 | #define ACCEPT_PLINKS 0x80 |
20 | ||
21 | int mesh_allocated; | |
22 | static struct kmem_cache *rm_cache; | |
23 | ||
24 | void ieee80211s_init(void) | |
25 | { | |
26 | mesh_pathtbl_init(); | |
27 | mesh_allocated = 1; | |
28 | rm_cache = kmem_cache_create("mesh_rmc", sizeof(struct rmc_entry), | |
29 | 0, 0, NULL); | |
30 | } | |
31 | ||
32 | void ieee80211s_stop(void) | |
33 | { | |
34 | mesh_pathtbl_unregister(); | |
35 | kmem_cache_destroy(rm_cache); | |
36 | } | |
37 | ||
38 | /** | |
39 | * mesh_matches_local - check if the config of a mesh point matches ours | |
40 | * | |
41 | * @ie: information elements of a management frame from the mesh peer | |
f698d856 | 42 | * @sdata: local mesh subif |
2e3c8736 LCC |
43 | * |
44 | * This function checks if the mesh configuration of a mesh point matches the | |
45 | * local mesh configuration, i.e. if both nodes belong to the same mesh network. | |
46 | */ | |
f698d856 | 47 | bool mesh_matches_local(struct ieee802_11_elems *ie, struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 48 | { |
2e3c8736 LCC |
49 | struct ieee80211_if_sta *sta = &sdata->u.sta; |
50 | ||
2e3c8736 LCC |
51 | /* |
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 | */ | |
3b091cd4 LCC |
61 | 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) | |
2e3c8736 LCC |
66 | 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 | |
2e3c8736 | 75 | */ |
f698d856 | 76 | bool mesh_peer_accepts_plinks(struct ieee802_11_elems *ie) |
2e3c8736 LCC |
77 | { |
78 | return (*(ie->mesh_config + CAPAB_OFFSET) & ACCEPT_PLINKS) != 0; | |
79 | } | |
80 | ||
81 | /** | |
82 | * mesh_accept_plinks_update: update accepting_plink in local mesh beacons | |
83 | * | |
d0709a65 | 84 | * @sdata: mesh interface in which mesh beacons are going to be updated |
2e3c8736 | 85 | */ |
d0709a65 | 86 | void mesh_accept_plinks_update(struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 87 | { |
2e3c8736 LCC |
88 | bool free_plinks; |
89 | ||
90 | /* In case mesh_plink_free_count > 0 and mesh_plinktbl_capacity == 0, | |
91 | * the mesh interface might be able to establish plinks with peers that | |
b4e08ea1 LCC |
92 | * are already on the table but are not on PLINK_ESTAB state. However, |
93 | * in general the mesh interface is not accepting peer link requests | |
94 | * from new peers, and that must be reflected in the beacon | |
2e3c8736 LCC |
95 | */ |
96 | free_plinks = mesh_plink_availables(sdata); | |
97 | ||
98 | if (free_plinks != sdata->u.sta.accepting_plinks) | |
99 | ieee80211_sta_timer((unsigned long) sdata); | |
100 | } | |
101 | ||
102 | void mesh_ids_set_default(struct ieee80211_if_sta *sta) | |
103 | { | |
104 | u8 def_id[4] = {0x00, 0x0F, 0xAC, 0xff}; | |
105 | ||
106 | memcpy(sta->mesh_pp_id, def_id, 4); | |
107 | memcpy(sta->mesh_pm_id, def_id, 4); | |
108 | memcpy(sta->mesh_cc_id, def_id, 4); | |
109 | } | |
110 | ||
f698d856 | 111 | int mesh_rmc_init(struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 112 | { |
2e3c8736 LCC |
113 | int i; |
114 | ||
115 | sdata->u.sta.rmc = kmalloc(sizeof(struct mesh_rmc), GFP_KERNEL); | |
116 | if (!sdata->u.sta.rmc) | |
117 | return -ENOMEM; | |
118 | sdata->u.sta.rmc->idx_mask = RMC_BUCKETS - 1; | |
119 | for (i = 0; i < RMC_BUCKETS; i++) | |
120 | INIT_LIST_HEAD(&sdata->u.sta.rmc->bucket[i].list); | |
121 | return 0; | |
122 | } | |
123 | ||
f698d856 | 124 | void mesh_rmc_free(struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 125 | { |
2e3c8736 LCC |
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, | |
f698d856 | 156 | struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 157 | { |
2e3c8736 LCC |
158 | struct mesh_rmc *rmc = sdata->u.sta.rmc; |
159 | u32 seqnum = 0; | |
160 | int entries = 0; | |
161 | u8 idx; | |
162 | struct rmc_entry *p, *n; | |
163 | ||
164 | /* Don't care about endianness since only match matters */ | |
51ceddad LCC |
165 | memcpy(&seqnum, &mesh_hdr->seqnum, sizeof(mesh_hdr->seqnum)); |
166 | idx = le32_to_cpu(mesh_hdr->seqnum) & rmc->idx_mask; | |
2e3c8736 LCC |
167 | list_for_each_entry_safe(p, n, &rmc->bucket[idx].list, list) { |
168 | ++entries; | |
169 | if (time_after(jiffies, p->exp_time) || | |
170 | (entries == RMC_QUEUE_MAX_LEN)) { | |
171 | list_del(&p->list); | |
172 | kmem_cache_free(rm_cache, p); | |
173 | --entries; | |
174 | } else if ((seqnum == p->seqnum) | |
175 | && (memcmp(sa, p->sa, ETH_ALEN) == 0)) | |
176 | return -1; | |
177 | } | |
178 | ||
179 | p = kmem_cache_alloc(rm_cache, GFP_ATOMIC); | |
180 | if (!p) { | |
181 | printk(KERN_DEBUG "o11s: could not allocate RMC entry\n"); | |
182 | return 0; | |
183 | } | |
184 | p->seqnum = seqnum; | |
185 | p->exp_time = jiffies + RMC_TIMEOUT; | |
186 | memcpy(p->sa, sa, ETH_ALEN); | |
187 | list_add(&p->list, &rmc->bucket[idx].list); | |
188 | return 0; | |
189 | } | |
190 | ||
f698d856 | 191 | void mesh_mgmt_ies_add(struct sk_buff *skb, struct ieee80211_sub_if_data *sdata) |
2e3c8736 | 192 | { |
f698d856 | 193 | struct ieee80211_local *local = sdata->local; |
2e3c8736 LCC |
194 | struct ieee80211_supported_band *sband; |
195 | u8 *pos; | |
196 | int len, i, rate; | |
197 | ||
198 | sband = local->hw.wiphy->bands[local->hw.conf.channel->band]; | |
199 | len = sband->n_bitrates; | |
200 | if (len > 8) | |
201 | len = 8; | |
202 | pos = skb_put(skb, len + 2); | |
203 | *pos++ = WLAN_EID_SUPP_RATES; | |
204 | *pos++ = len; | |
205 | for (i = 0; i < len; i++) { | |
206 | rate = sband->bitrates[i].bitrate; | |
207 | *pos++ = (u8) (rate / 5); | |
208 | } | |
209 | ||
210 | if (sband->n_bitrates > len) { | |
211 | pos = skb_put(skb, sband->n_bitrates - len + 2); | |
212 | *pos++ = WLAN_EID_EXT_SUPP_RATES; | |
213 | *pos++ = sband->n_bitrates - len; | |
214 | for (i = len; i < sband->n_bitrates; i++) { | |
215 | rate = sband->bitrates[i].bitrate; | |
216 | *pos++ = (u8) (rate / 5); | |
217 | } | |
218 | } | |
219 | ||
220 | pos = skb_put(skb, 2 + sdata->u.sta.mesh_id_len); | |
221 | *pos++ = WLAN_EID_MESH_ID; | |
222 | *pos++ = sdata->u.sta.mesh_id_len; | |
223 | if (sdata->u.sta.mesh_id_len) | |
224 | memcpy(pos, sdata->u.sta.mesh_id, sdata->u.sta.mesh_id_len); | |
225 | ||
226 | pos = skb_put(skb, 21); | |
227 | *pos++ = WLAN_EID_MESH_CONFIG; | |
228 | *pos++ = MESH_CFG_LEN; | |
229 | /* Version */ | |
230 | *pos++ = 1; | |
231 | ||
232 | /* Active path selection protocol ID */ | |
233 | memcpy(pos, sdata->u.sta.mesh_pp_id, 4); | |
234 | pos += 4; | |
235 | ||
236 | /* Active path selection metric ID */ | |
237 | memcpy(pos, sdata->u.sta.mesh_pm_id, 4); | |
238 | pos += 4; | |
239 | ||
240 | /* Congestion control mode identifier */ | |
241 | memcpy(pos, sdata->u.sta.mesh_cc_id, 4); | |
242 | pos += 4; | |
243 | ||
244 | /* Channel precedence: | |
245 | * Not running simple channel unification protocol | |
246 | */ | |
247 | memset(pos, 0x00, 4); | |
248 | pos += 4; | |
249 | ||
250 | /* Mesh capability */ | |
251 | sdata->u.sta.accepting_plinks = mesh_plink_availables(sdata); | |
252 | *pos++ = sdata->u.sta.accepting_plinks ? ACCEPT_PLINKS : 0x00; | |
253 | *pos++ = 0x00; | |
254 | ||
255 | return; | |
256 | } | |
257 | ||
f698d856 | 258 | u32 mesh_table_hash(u8 *addr, struct ieee80211_sub_if_data *sdata, struct mesh_table *tbl) |
2e3c8736 LCC |
259 | { |
260 | /* Use last four bytes of hw addr and interface index as hash index */ | |
f698d856 | 261 | return jhash_2words(*(u32 *)(addr+2), sdata->dev->ifindex, tbl->hash_rnd) |
2e3c8736 LCC |
262 | & tbl->hash_mask; |
263 | } | |
264 | ||
265 | u8 mesh_id_hash(u8 *mesh_id, int mesh_id_len) | |
266 | { | |
267 | if (!mesh_id_len) | |
268 | return 1; | |
269 | else if (mesh_id_len == 1) | |
270 | return (u8) mesh_id[0]; | |
271 | else | |
272 | return (u8) (mesh_id[0] + 2 * mesh_id[1]); | |
273 | } | |
274 | ||
275 | struct mesh_table *mesh_table_alloc(int size_order) | |
276 | { | |
277 | int i; | |
278 | struct mesh_table *newtbl; | |
279 | ||
280 | newtbl = kmalloc(sizeof(struct mesh_table), GFP_KERNEL); | |
281 | if (!newtbl) | |
282 | return NULL; | |
283 | ||
284 | newtbl->hash_buckets = kzalloc(sizeof(struct hlist_head) * | |
285 | (1 << size_order), GFP_KERNEL); | |
286 | ||
287 | if (!newtbl->hash_buckets) { | |
288 | kfree(newtbl); | |
289 | return NULL; | |
290 | } | |
291 | ||
292 | newtbl->hashwlock = kmalloc(sizeof(spinlock_t) * | |
293 | (1 << size_order), GFP_KERNEL); | |
294 | if (!newtbl->hashwlock) { | |
295 | kfree(newtbl->hash_buckets); | |
296 | kfree(newtbl); | |
297 | return NULL; | |
298 | } | |
299 | ||
300 | newtbl->size_order = size_order; | |
301 | newtbl->hash_mask = (1 << size_order) - 1; | |
302 | atomic_set(&newtbl->entries, 0); | |
303 | get_random_bytes(&newtbl->hash_rnd, | |
304 | sizeof(newtbl->hash_rnd)); | |
305 | for (i = 0; i <= newtbl->hash_mask; i++) | |
306 | spin_lock_init(&newtbl->hashwlock[i]); | |
307 | ||
308 | return newtbl; | |
309 | } | |
310 | ||
bd9b448f PE |
311 | static void __mesh_table_free(struct mesh_table *tbl) |
312 | { | |
313 | kfree(tbl->hash_buckets); | |
314 | kfree(tbl->hashwlock); | |
315 | kfree(tbl); | |
316 | } | |
317 | ||
2e3c8736 LCC |
318 | void mesh_table_free(struct mesh_table *tbl, bool free_leafs) |
319 | { | |
320 | struct hlist_head *mesh_hash; | |
321 | struct hlist_node *p, *q; | |
322 | int i; | |
323 | ||
324 | mesh_hash = tbl->hash_buckets; | |
325 | for (i = 0; i <= tbl->hash_mask; i++) { | |
326 | spin_lock(&tbl->hashwlock[i]); | |
327 | hlist_for_each_safe(p, q, &mesh_hash[i]) { | |
328 | tbl->free_node(p, free_leafs); | |
329 | atomic_dec(&tbl->entries); | |
330 | } | |
331 | spin_unlock(&tbl->hashwlock[i]); | |
332 | } | |
bd9b448f | 333 | __mesh_table_free(tbl); |
2e3c8736 LCC |
334 | } |
335 | ||
336 | static void ieee80211_mesh_path_timer(unsigned long data) | |
337 | { | |
338 | struct ieee80211_sub_if_data *sdata = | |
339 | (struct ieee80211_sub_if_data *) data; | |
340 | struct ieee80211_if_sta *ifsta = &sdata->u.sta; | |
341 | struct ieee80211_local *local = wdev_priv(&sdata->wdev); | |
342 | ||
343 | queue_work(local->hw.workqueue, &ifsta->work); | |
344 | } | |
345 | ||
346 | struct mesh_table *mesh_table_grow(struct mesh_table *tbl) | |
347 | { | |
348 | struct mesh_table *newtbl; | |
349 | struct hlist_head *oldhash; | |
4caf86c6 | 350 | struct hlist_node *p, *q; |
2e3c8736 LCC |
351 | int i; |
352 | ||
353 | if (atomic_read(&tbl->entries) | |
a3538b19 | 354 | < tbl->mean_chain_len * (tbl->hash_mask + 1)) |
2e3c8736 | 355 | goto endgrow; |
2e3c8736 LCC |
356 | |
357 | newtbl = mesh_table_alloc(tbl->size_order + 1); | |
a3538b19 | 358 | if (!newtbl) |
2e3c8736 | 359 | goto endgrow; |
2e3c8736 LCC |
360 | |
361 | newtbl->free_node = tbl->free_node; | |
362 | newtbl->mean_chain_len = tbl->mean_chain_len; | |
363 | newtbl->copy_node = tbl->copy_node; | |
364 | atomic_set(&newtbl->entries, atomic_read(&tbl->entries)); | |
365 | ||
366 | oldhash = tbl->hash_buckets; | |
367 | for (i = 0; i <= tbl->hash_mask; i++) | |
368 | hlist_for_each(p, &oldhash[i]) | |
4caf86c6 PE |
369 | if (tbl->copy_node(p, newtbl) < 0) |
370 | goto errcopy; | |
2e3c8736 | 371 | |
a3538b19 | 372 | return newtbl; |
4caf86c6 PE |
373 | |
374 | errcopy: | |
375 | for (i = 0; i <= newtbl->hash_mask; i++) { | |
376 | hlist_for_each_safe(p, q, &newtbl->hash_buckets[i]) | |
377 | tbl->free_node(p, 0); | |
378 | } | |
bd9b448f | 379 | __mesh_table_free(tbl); |
a3538b19 | 380 | endgrow: |
4caf86c6 | 381 | return NULL; |
2e3c8736 | 382 | } |
902acc78 JB |
383 | |
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 | */ | |
391 | int 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; | |
51ceddad LCC |
396 | put_unaligned(cpu_to_le32(sdata->u.sta.mesh_seqnum), &meshhdr->seqnum); |
397 | sdata->u.sta.mesh_seqnum++; | |
902acc78 | 398 | |
ef269254 | 399 | return 6; |
902acc78 JB |
400 | } |
401 | ||
402 | void ieee80211_mesh_init_sdata(struct ieee80211_sub_if_data *sdata) | |
403 | { | |
404 | struct ieee80211_if_sta *ifsta = &sdata->u.sta; | |
405 | ||
406 | ifsta->mshcfg.dot11MeshRetryTimeout = MESH_RET_T; | |
407 | ifsta->mshcfg.dot11MeshConfirmTimeout = MESH_CONF_T; | |
408 | ifsta->mshcfg.dot11MeshHoldingTimeout = MESH_HOLD_T; | |
409 | ifsta->mshcfg.dot11MeshMaxRetries = MESH_MAX_RETR; | |
410 | ifsta->mshcfg.dot11MeshTTL = MESH_TTL; | |
411 | ifsta->mshcfg.auto_open_plinks = true; | |
412 | ifsta->mshcfg.dot11MeshMaxPeerLinks = | |
413 | MESH_MAX_ESTAB_PLINKS; | |
414 | ifsta->mshcfg.dot11MeshHWMPactivePathTimeout = | |
415 | MESH_PATH_TIMEOUT; | |
416 | ifsta->mshcfg.dot11MeshHWMPpreqMinInterval = | |
417 | MESH_PREQ_MIN_INT; | |
418 | ifsta->mshcfg.dot11MeshHWMPnetDiameterTraversalTime = | |
419 | MESH_DIAM_TRAVERSAL_TIME; | |
420 | ifsta->mshcfg.dot11MeshHWMPmaxPREQretries = | |
421 | MESH_MAX_PREQ_RETRIES; | |
422 | ifsta->mshcfg.path_refresh_time = | |
423 | MESH_PATH_REFRESH_TIME; | |
424 | ifsta->mshcfg.min_discovery_timeout = | |
425 | MESH_MIN_DISCOVERY_TIMEOUT; | |
426 | ifsta->accepting_plinks = true; | |
427 | ifsta->preq_id = 0; | |
428 | ifsta->dsn = 0; | |
429 | atomic_set(&ifsta->mpaths, 0); | |
f698d856 | 430 | mesh_rmc_init(sdata); |
902acc78 JB |
431 | ifsta->last_preq = jiffies; |
432 | /* Allocate all mesh structures when creating the first mesh interface. */ | |
433 | if (!mesh_allocated) | |
434 | ieee80211s_init(); | |
435 | mesh_ids_set_default(ifsta); | |
436 | setup_timer(&ifsta->mesh_path_timer, | |
437 | ieee80211_mesh_path_timer, | |
438 | (unsigned long) sdata); | |
439 | INIT_LIST_HEAD(&ifsta->preq_queue.list); | |
440 | spin_lock_init(&ifsta->mesh_preq_queue_lock); | |
441 | } |