1// SPDX-License-Identifier: GPL-2.0-only 2/* 3 * Copyright (c) 2008, 2009 open80211s Ltd. 4 * Copyright (C) 2023 Intel Corporation 5 * Author: Luis Carlos Cobo <luisca@cozybit.com> 6 */ 7 8#include <linux/etherdevice.h> 9#include <linux/list.h> 10#include <linux/random.h> 11#include <linux/slab.h> 12#include <linux/spinlock.h> 13#include <linux/string.h> 14#include <net/mac80211.h> 15#include "wme.h" 16#include "ieee80211_i.h" 17#include "mesh.h" 18#include <linux/rhashtable.h> 19 20static void mesh_path_free_rcu(struct mesh_table *tbl, struct mesh_path *mpath); 21 22static u32 mesh_table_hash(const void *addr, u32 len, u32 seed) 23{ 24 /* Use last four bytes of hw addr as hash index */ 25 return jhash_1word(__get_unaligned_cpu32((u8 *)addr + 2), seed); 26} 27 28static const struct rhashtable_params mesh_rht_params = { 29 .nelem_hint = 2, 30 .automatic_shrinking = true, 31 .key_len = ETH_ALEN, 32 .key_offset = offsetof(struct mesh_path, dst), 33 .head_offset = offsetof(struct mesh_path, rhash), 34 .hashfn = mesh_table_hash, 35}; 36 37static const struct rhashtable_params fast_tx_rht_params = { 38 .nelem_hint = 10, 39 .automatic_shrinking = true, 40 .key_len = ETH_ALEN, 41 .key_offset = offsetof(struct ieee80211_mesh_fast_tx, addr_key), 42 .head_offset = offsetof(struct ieee80211_mesh_fast_tx, rhash), 43 .hashfn = mesh_table_hash, 44}; 45 46static void __mesh_fast_tx_entry_free(void *ptr, void *tblptr) 47{ 48 struct ieee80211_mesh_fast_tx *entry = ptr; 49 50 kfree_rcu(entry, fast_tx.rcu_head); 51} 52 53static void mesh_fast_tx_deinit(struct ieee80211_sub_if_data *sdata) 54{ 55 struct mesh_tx_cache *cache; 56 57 cache = &sdata->u.mesh.tx_cache; 58 rhashtable_free_and_destroy(&cache->rht, 59 __mesh_fast_tx_entry_free, NULL); 60} 61 62static void mesh_fast_tx_init(struct ieee80211_sub_if_data *sdata) 63{ 64 struct mesh_tx_cache *cache; 65 66 cache = &sdata->u.mesh.tx_cache; 67 rhashtable_init(&cache->rht, &fast_tx_rht_params); 68 INIT_HLIST_HEAD(&cache->walk_head); 69 spin_lock_init(&cache->walk_lock); 70} 71 72static inline bool mpath_expired(struct mesh_path *mpath) 73{ 74 return (mpath->flags & MESH_PATH_ACTIVE) && 75 time_after(jiffies, mpath->exp_time) && 76 !(mpath->flags & MESH_PATH_FIXED); 77} 78 79static void mesh_path_rht_free(void *ptr, void *tblptr) 80{ 81 struct mesh_path *mpath = ptr; 82 struct mesh_table *tbl = tblptr; 83 84 mesh_path_free_rcu(tbl, mpath); 85} 86 87static void mesh_table_init(struct mesh_table *tbl) 88{ 89 INIT_HLIST_HEAD(&tbl->known_gates); 90 INIT_HLIST_HEAD(&tbl->walk_head); 91 atomic_set(&tbl->entries, 0); 92 spin_lock_init(&tbl->gates_lock); 93 spin_lock_init(&tbl->walk_lock); 94 95 /* rhashtable_init() may fail only in case of wrong 96 * mesh_rht_params 97 */ 98 WARN_ON(rhashtable_init(&tbl->rhead, &mesh_rht_params)); 99} 100 101static void mesh_table_free(struct mesh_table *tbl) 102{ 103 rhashtable_free_and_destroy(&tbl->rhead, 104 mesh_path_rht_free, tbl); 105} 106 107/** 108 * mesh_path_assign_nexthop - update mesh path next hop 109 * 110 * @mpath: mesh path to update 111 * @sta: next hop to assign 112 * 113 * Locking: mpath->state_lock must be held when calling this function 114 */ 115void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta) 116{ 117 struct sk_buff *skb; 118 struct ieee80211_hdr *hdr; 119 unsigned long flags; 120 121 rcu_assign_pointer(mpath->next_hop, sta); 122 123 spin_lock_irqsave(&mpath->frame_queue.lock, flags); 124 skb_queue_walk(&mpath->frame_queue, skb) { 125 hdr = (struct ieee80211_hdr *) skb->data; 126 memcpy(hdr->addr1, sta->sta.addr, ETH_ALEN); 127 memcpy(hdr->addr2, mpath->sdata->vif.addr, ETH_ALEN); 128 ieee80211_mps_set_frame_flags(sta->sdata, sta, hdr); 129 } 130 131 spin_unlock_irqrestore(&mpath->frame_queue.lock, flags); 132} 133 134static void prepare_for_gate(struct sk_buff *skb, char *dst_addr, 135 struct mesh_path *gate_mpath) 136{ 137 struct ieee80211_hdr *hdr; 138 struct ieee80211s_hdr *mshdr; 139 int mesh_hdrlen, hdrlen; 140 char *next_hop; 141 142 hdr = (struct ieee80211_hdr *) skb->data; 143 hdrlen = ieee80211_hdrlen(hdr->frame_control); 144 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen); 145 146 if (!(mshdr->flags & MESH_FLAGS_AE)) { 147 /* size of the fixed part of the mesh header */ 148 mesh_hdrlen = 6; 149 150 /* make room for the two extended addresses */ 151 skb_push(skb, 2 * ETH_ALEN); 152 memmove(skb->data, hdr, hdrlen + mesh_hdrlen); 153 154 hdr = (struct ieee80211_hdr *) skb->data; 155 156 /* we preserve the previous mesh header and only add 157 * the new addresses */ 158 mshdr = (struct ieee80211s_hdr *) (skb->data + hdrlen); 159 mshdr->flags = MESH_FLAGS_AE_A5_A6; 160 memcpy(mshdr->eaddr1, hdr->addr3, ETH_ALEN); 161 memcpy(mshdr->eaddr2, hdr->addr4, ETH_ALEN); 162 } 163 164 /* update next hop */ 165 hdr = (struct ieee80211_hdr *) skb->data; 166 rcu_read_lock(); 167 next_hop = rcu_dereference(gate_mpath->next_hop)->sta.addr; 168 memcpy(hdr->addr1, next_hop, ETH_ALEN); 169 rcu_read_unlock(); 170 memcpy(hdr->addr2, gate_mpath->sdata->vif.addr, ETH_ALEN); 171 memcpy(hdr->addr3, dst_addr, ETH_ALEN); 172} 173 174/** 175 * mesh_path_move_to_queue - Move or copy frames from one mpath queue to another 176 * 177 * @gate_mpath: An active mpath the frames will be sent to (i.e. the gate) 178 * @from_mpath: The failed mpath 179 * @copy: When true, copy all the frames to the new mpath queue. When false, 180 * move them. 181 * 182 * This function is used to transfer or copy frames from an unresolved mpath to 183 * a gate mpath. The function also adds the Address Extension field and 184 * updates the next hop. 185 * 186 * If a frame already has an Address Extension field, only the next hop and 187 * destination addresses are updated. 188 * 189 * The gate mpath must be an active mpath with a valid mpath->next_hop. 190 */ 191static void mesh_path_move_to_queue(struct mesh_path *gate_mpath, 192 struct mesh_path *from_mpath, 193 bool copy) 194{ 195 struct sk_buff *skb, *fskb, *tmp; 196 struct sk_buff_head failq; 197 unsigned long flags; 198 199 if (WARN_ON(gate_mpath == from_mpath)) 200 return; 201 if (WARN_ON(!gate_mpath->next_hop)) 202 return; 203 204 __skb_queue_head_init(&failq); 205 206 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags); 207 skb_queue_splice_init(&from_mpath->frame_queue, &failq); 208 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags); 209 210 skb_queue_walk_safe(&failq, fskb, tmp) { 211 if (skb_queue_len(&gate_mpath->frame_queue) >= 212 MESH_FRAME_QUEUE_LEN) { 213 mpath_dbg(gate_mpath->sdata, "mpath queue full!\n"); 214 break; 215 } 216 217 skb = skb_copy(fskb, GFP_ATOMIC); 218 if (WARN_ON(!skb)) 219 break; 220 221 prepare_for_gate(skb, gate_mpath->dst, gate_mpath); 222 skb_queue_tail(&gate_mpath->frame_queue, skb); 223 224 if (copy) 225 continue; 226 227 __skb_unlink(fskb, &failq); 228 kfree_skb(fskb); 229 } 230 231 mpath_dbg(gate_mpath->sdata, "Mpath queue for gate %pM has %d frames\n", 232 gate_mpath->dst, skb_queue_len(&gate_mpath->frame_queue)); 233 234 if (!copy) 235 return; 236 237 spin_lock_irqsave(&from_mpath->frame_queue.lock, flags); 238 skb_queue_splice(&failq, &from_mpath->frame_queue); 239 spin_unlock_irqrestore(&from_mpath->frame_queue.lock, flags); 240} 241 242 243static struct mesh_path *mpath_lookup(struct mesh_table *tbl, const u8 *dst, 244 struct ieee80211_sub_if_data *sdata) 245{ 246 struct mesh_path *mpath; 247 248 mpath = rhashtable_lookup(&tbl->rhead, dst, mesh_rht_params); 249 250 if (mpath && mpath_expired(mpath)) { 251 spin_lock_bh(&mpath->state_lock); 252 mpath->flags &= ~MESH_PATH_ACTIVE; 253 spin_unlock_bh(&mpath->state_lock); 254 } 255 return mpath; 256} 257 258/** 259 * mesh_path_lookup - look up a path in the mesh path table 260 * @sdata: local subif 261 * @dst: hardware address (ETH_ALEN length) of destination 262 * 263 * Returns: pointer to the mesh path structure, or NULL if not found 264 * 265 * Locking: must be called within a read rcu section. 266 */ 267struct mesh_path * 268mesh_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) 269{ 270 return mpath_lookup(&sdata->u.mesh.mesh_paths, dst, sdata); 271} 272 273struct mesh_path * 274mpp_path_lookup(struct ieee80211_sub_if_data *sdata, const u8 *dst) 275{ 276 return mpath_lookup(&sdata->u.mesh.mpp_paths, dst, sdata); 277} 278 279static struct mesh_path * 280__mesh_path_lookup_by_idx(struct mesh_table *tbl, int idx) 281{ 282 int i = 0; 283 struct mesh_path *mpath; 284 285 hlist_for_each_entry_rcu(mpath, &tbl->walk_head, walk_list) { 286 if (i++ == idx) 287 break; 288 } 289 290 if (!mpath) 291 return NULL; 292 293 if (mpath_expired(mpath)) { 294 spin_lock_bh(&mpath->state_lock); 295 mpath->flags &= ~MESH_PATH_ACTIVE; 296 spin_unlock_bh(&mpath->state_lock); 297 } 298 return mpath; 299} 300 301/** 302 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index 303 * @idx: index 304 * @sdata: local subif, or NULL for all entries 305 * 306 * Returns: pointer to the mesh path structure, or NULL if not found. 307 * 308 * Locking: must be called within a read rcu section. 309 */ 310struct mesh_path * 311mesh_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) 312{ 313 return __mesh_path_lookup_by_idx(&sdata->u.mesh.mesh_paths, idx); 314} 315 316/** 317 * mpp_path_lookup_by_idx - look up a path in the proxy path table by its index 318 * @idx: index 319 * @sdata: local subif, or NULL for all entries 320 * 321 * Returns: pointer to the proxy path structure, or NULL if not found. 322 * 323 * Locking: must be called within a read rcu section. 324 */ 325struct mesh_path * 326mpp_path_lookup_by_idx(struct ieee80211_sub_if_data *sdata, int idx) 327{ 328 return __mesh_path_lookup_by_idx(&sdata->u.mesh.mpp_paths, idx); 329} 330 331/** 332 * mesh_path_add_gate - add the given mpath to a mesh gate to our path table 333 * @mpath: gate path to add to table 334 * 335 * Returns: 0 on success, -EEXIST 336 */ 337int mesh_path_add_gate(struct mesh_path *mpath) 338{ 339 struct mesh_table *tbl; 340 int err; 341 342 rcu_read_lock(); 343 tbl = &mpath->sdata->u.mesh.mesh_paths; 344 345 spin_lock_bh(&mpath->state_lock); 346 if (mpath->is_gate) { 347 err = -EEXIST; 348 spin_unlock_bh(&mpath->state_lock); 349 goto err_rcu; 350 } 351 mpath->is_gate = true; 352 mpath->sdata->u.mesh.num_gates++; 353 354 spin_lock(&tbl->gates_lock); 355 hlist_add_head_rcu(&mpath->gate_list, &tbl->known_gates); 356 spin_unlock(&tbl->gates_lock); 357 358 spin_unlock_bh(&mpath->state_lock); 359 360 mpath_dbg(mpath->sdata, 361 "Mesh path: Recorded new gate: %pM. %d known gates\n", 362 mpath->dst, mpath->sdata->u.mesh.num_gates); 363 err = 0; 364err_rcu: 365 rcu_read_unlock(); 366 return err; 367} 368 369/** 370 * mesh_gate_del - remove a mesh gate from the list of known gates 371 * @tbl: table which holds our list of known gates 372 * @mpath: gate mpath 373 */ 374static void mesh_gate_del(struct mesh_table *tbl, struct mesh_path *mpath) 375{ 376 lockdep_assert_held(&mpath->state_lock); 377 if (!mpath->is_gate) 378 return; 379 380 mpath->is_gate = false; 381 spin_lock_bh(&tbl->gates_lock); 382 hlist_del_rcu(&mpath->gate_list); 383 mpath->sdata->u.mesh.num_gates--; 384 spin_unlock_bh(&tbl->gates_lock); 385 386 mpath_dbg(mpath->sdata, 387 "Mesh path: Deleted gate: %pM. %d known gates\n", 388 mpath->dst, mpath->sdata->u.mesh.num_gates); 389} 390 391/** 392 * mesh_gate_num - number of gates known to this interface 393 * @sdata: subif data 394 * 395 * Returns: The number of gates 396 */ 397int mesh_gate_num(struct ieee80211_sub_if_data *sdata) 398{ 399 return sdata->u.mesh.num_gates; 400} 401 402static 403struct mesh_path *mesh_path_new(struct ieee80211_sub_if_data *sdata, 404 const u8 *dst, gfp_t gfp_flags) 405{ 406 struct mesh_path *new_mpath; 407 408 new_mpath = kzalloc(sizeof(struct mesh_path), gfp_flags); 409 if (!new_mpath) 410 return NULL; 411 412 memcpy(new_mpath->dst, dst, ETH_ALEN); 413 eth_broadcast_addr(new_mpath->rann_snd_addr); 414 new_mpath->is_root = false; 415 new_mpath->sdata = sdata; 416 new_mpath->flags = 0; 417 skb_queue_head_init(&new_mpath->frame_queue); 418 new_mpath->exp_time = jiffies; 419 spin_lock_init(&new_mpath->state_lock); 420 timer_setup(&new_mpath->timer, mesh_path_timer, 0); 421 422 return new_mpath; 423} 424 425static void mesh_fast_tx_entry_free(struct mesh_tx_cache *cache, 426 struct ieee80211_mesh_fast_tx *entry) 427{ 428 hlist_del_rcu(&entry->walk_list); 429 rhashtable_remove_fast(&cache->rht, &entry->rhash, fast_tx_rht_params); 430 kfree_rcu(entry, fast_tx.rcu_head); 431} 432 433struct ieee80211_mesh_fast_tx * 434mesh_fast_tx_get(struct ieee80211_sub_if_data *sdata, const u8 *addr) 435{ 436 struct ieee80211_mesh_fast_tx *entry; 437 struct mesh_tx_cache *cache; 438 439 cache = &sdata->u.mesh.tx_cache; 440 entry = rhashtable_lookup(&cache->rht, addr, fast_tx_rht_params); 441 if (!entry) 442 return NULL; 443 444 if (!(entry->mpath->flags & MESH_PATH_ACTIVE) || 445 mpath_expired(entry->mpath)) { 446 spin_lock_bh(&cache->walk_lock); 447 entry = rhashtable_lookup(&cache->rht, addr, fast_tx_rht_params); 448 if (entry) 449 mesh_fast_tx_entry_free(cache, entry); 450 spin_unlock_bh(&cache->walk_lock); 451 return NULL; 452 } 453 454 mesh_path_refresh(sdata, entry->mpath, NULL); 455 if (entry->mppath) 456 entry->mppath->exp_time = jiffies; 457 entry->timestamp = jiffies; 458 459 return entry; 460} 461 462void mesh_fast_tx_cache(struct ieee80211_sub_if_data *sdata, 463 struct sk_buff *skb, struct mesh_path *mpath) 464{ 465 struct ieee80211_hdr *hdr = (struct ieee80211_hdr *)skb->data; 466 struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb); 467 struct ieee80211_mesh_fast_tx *entry, *prev; 468 struct ieee80211_mesh_fast_tx build = {}; 469 struct ieee80211s_hdr *meshhdr; 470 struct mesh_tx_cache *cache; 471 struct ieee80211_key *key; 472 struct mesh_path *mppath; 473 struct sta_info *sta; 474 u8 *qc; 475 476 if (sdata->noack_map || 477 !ieee80211_is_data_qos(hdr->frame_control)) 478 return; 479 480 build.fast_tx.hdr_len = ieee80211_hdrlen(hdr->frame_control); 481 meshhdr = (struct ieee80211s_hdr *)(skb->data + build.fast_tx.hdr_len); 482 build.hdrlen = ieee80211_get_mesh_hdrlen(meshhdr); 483 484 cache = &sdata->u.mesh.tx_cache; 485 if (atomic_read(&cache->rht.nelems) >= MESH_FAST_TX_CACHE_MAX_SIZE) 486 return; 487 488 sta = rcu_dereference(mpath->next_hop); 489 if (!sta) 490 return; 491 492 if ((meshhdr->flags & MESH_FLAGS_AE) == MESH_FLAGS_AE_A5_A6) { 493 /* This is required to keep the mppath alive */ 494 mppath = mpp_path_lookup(sdata, meshhdr->eaddr1); 495 if (!mppath) 496 return; 497 build.mppath = mppath; 498 } else if (ieee80211_has_a4(hdr->frame_control)) { 499 mppath = mpath; 500 } else { 501 return; 502 } 503 504 /* rate limit, in case fast xmit can't be enabled */ 505 if (mppath->fast_tx_check == jiffies) 506 return; 507 508 mppath->fast_tx_check = jiffies; 509 510 /* 511 * Same use of the sta lock as in ieee80211_check_fast_xmit, in order 512 * to protect against concurrent sta key updates. 513 */ 514 spin_lock_bh(&sta->lock); 515 key = rcu_access_pointer(sta->ptk[sta->ptk_idx]); 516 if (!key) 517 key = rcu_access_pointer(sdata->default_unicast_key); 518 build.fast_tx.key = key; 519 520 if (key) { 521 bool gen_iv, iv_spc; 522 523 gen_iv = key->conf.flags & IEEE80211_KEY_FLAG_GENERATE_IV; 524 iv_spc = key->conf.flags & IEEE80211_KEY_FLAG_PUT_IV_SPACE; 525 526 if (!(key->flags & KEY_FLAG_UPLOADED_TO_HARDWARE) || 527 (key->flags & KEY_FLAG_TAINTED)) 528 goto unlock_sta; 529 530 switch (key->conf.cipher) { 531 case WLAN_CIPHER_SUITE_CCMP: 532 case WLAN_CIPHER_SUITE_CCMP_256: 533 if (gen_iv) 534 build.fast_tx.pn_offs = build.fast_tx.hdr_len; 535 if (gen_iv || iv_spc) 536 build.fast_tx.hdr_len += IEEE80211_CCMP_HDR_LEN; 537 break; 538 case WLAN_CIPHER_SUITE_GCMP: 539 case WLAN_CIPHER_SUITE_GCMP_256: 540 if (gen_iv) 541 build.fast_tx.pn_offs = build.fast_tx.hdr_len; 542 if (gen_iv || iv_spc) 543 build.fast_tx.hdr_len += IEEE80211_GCMP_HDR_LEN; 544 break; 545 default: 546 goto unlock_sta; 547 } 548 } 549 550 memcpy(build.addr_key, mppath->dst, ETH_ALEN); 551 build.timestamp = jiffies; 552 build.fast_tx.band = info->band; 553 build.fast_tx.da_offs = offsetof(struct ieee80211_hdr, addr3); 554 build.fast_tx.sa_offs = offsetof(struct ieee80211_hdr, addr4); 555 build.mpath = mpath; 556 memcpy(build.hdr, meshhdr, build.hdrlen); 557 memcpy(build.hdr + build.hdrlen, rfc1042_header, sizeof(rfc1042_header)); 558 build.hdrlen += sizeof(rfc1042_header); 559 memcpy(build.fast_tx.hdr, hdr, build.fast_tx.hdr_len); 560 561 hdr = (struct ieee80211_hdr *)build.fast_tx.hdr; 562 if (build.fast_tx.key) 563 hdr->frame_control |= cpu_to_le16(IEEE80211_FCTL_PROTECTED); 564 565 qc = ieee80211_get_qos_ctl(hdr); 566 qc[1] |= IEEE80211_QOS_CTL_MESH_CONTROL_PRESENT >> 8; 567 568 entry = kmemdup(&build, sizeof(build), GFP_ATOMIC); 569 if (!entry) 570 goto unlock_sta; 571 572 spin_lock(&cache->walk_lock); 573 prev = rhashtable_lookup_get_insert_fast(&cache->rht, 574 &entry->rhash, 575 fast_tx_rht_params); 576 if (unlikely(IS_ERR(prev))) { 577 kfree(entry); 578 goto unlock_cache; 579 } 580 581 /* 582 * replace any previous entry in the hash table, in case we're 583 * replacing it with a different type (e.g. mpath -> mpp) 584 */ 585 if (unlikely(prev)) { 586 rhashtable_replace_fast(&cache->rht, &prev->rhash, 587 &entry->rhash, fast_tx_rht_params); 588 hlist_del_rcu(&prev->walk_list); 589 kfree_rcu(prev, fast_tx.rcu_head); 590 } 591 592 hlist_add_head(&entry->walk_list, &cache->walk_head); 593 594unlock_cache: 595 spin_unlock(&cache->walk_lock); 596unlock_sta: 597 spin_unlock_bh(&sta->lock); 598} 599 600void mesh_fast_tx_gc(struct ieee80211_sub_if_data *sdata) 601{ 602 unsigned long timeout = msecs_to_jiffies(MESH_FAST_TX_CACHE_TIMEOUT); 603 struct mesh_tx_cache *cache = &sdata->u.mesh.tx_cache; 604 struct ieee80211_mesh_fast_tx *entry; 605 struct hlist_node *n; 606 607 if (atomic_read(&cache->rht.nelems) < MESH_FAST_TX_CACHE_THRESHOLD_SIZE) 608 return; 609 610 spin_lock_bh(&cache->walk_lock); 611 hlist_for_each_entry_safe(entry, n, &cache->walk_head, walk_list) 612 if (!time_is_after_jiffies(entry->timestamp + timeout)) 613 mesh_fast_tx_entry_free(cache, entry); 614 spin_unlock_bh(&cache->walk_lock); 615} 616 617void mesh_fast_tx_flush_mpath(struct mesh_path *mpath) 618{ 619 struct ieee80211_sub_if_data *sdata = mpath->sdata; 620 struct mesh_tx_cache *cache = &sdata->u.mesh.tx_cache; 621 struct ieee80211_mesh_fast_tx *entry; 622 struct hlist_node *n; 623 624 spin_lock_bh(&cache->walk_lock); 625 hlist_for_each_entry_safe(entry, n, &cache->walk_head, walk_list) 626 if (entry->mpath == mpath) 627 mesh_fast_tx_entry_free(cache, entry); 628 spin_unlock_bh(&cache->walk_lock); 629} 630 631void mesh_fast_tx_flush_sta(struct ieee80211_sub_if_data *sdata, 632 struct sta_info *sta) 633{ 634 struct mesh_tx_cache *cache = &sdata->u.mesh.tx_cache; 635 struct ieee80211_mesh_fast_tx *entry; 636 struct hlist_node *n; 637 638 spin_lock_bh(&cache->walk_lock); 639 hlist_for_each_entry_safe(entry, n, &cache->walk_head, walk_list) 640 if (rcu_access_pointer(entry->mpath->next_hop) == sta) 641 mesh_fast_tx_entry_free(cache, entry); 642 spin_unlock_bh(&cache->walk_lock); 643} 644 645void mesh_fast_tx_flush_addr(struct ieee80211_sub_if_data *sdata, 646 const u8 *addr) 647{ 648 struct mesh_tx_cache *cache = &sdata->u.mesh.tx_cache; 649 struct ieee80211_mesh_fast_tx *entry; 650 651 spin_lock_bh(&cache->walk_lock); 652 entry = rhashtable_lookup_fast(&cache->rht, addr, fast_tx_rht_params); 653 if (entry) 654 mesh_fast_tx_entry_free(cache, entry); 655 spin_unlock_bh(&cache->walk_lock); 656} 657 658/** 659 * mesh_path_add - allocate and add a new path to the mesh path table 660 * @dst: destination address of the path (ETH_ALEN length) 661 * @sdata: local subif 662 * 663 * Returns: 0 on success 664 * 665 * State: the initial state of the new path is set to 0 666 */ 667struct mesh_path *mesh_path_add(struct ieee80211_sub_if_data *sdata, 668 const u8 *dst) 669{ 670 struct mesh_table *tbl; 671 struct mesh_path *mpath, *new_mpath; 672 673 if (ether_addr_equal(dst, sdata->vif.addr)) 674 /* never add ourselves as neighbours */ 675 return ERR_PTR(-EOPNOTSUPP); 676 677 if (is_multicast_ether_addr(dst)) 678 return ERR_PTR(-EOPNOTSUPP); 679 680 if (atomic_add_unless(&sdata->u.mesh.mpaths, 1, MESH_MAX_MPATHS) == 0) 681 return ERR_PTR(-ENOSPC); 682 683 new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); 684 if (!new_mpath) 685 return ERR_PTR(-ENOMEM); 686 687 tbl = &sdata->u.mesh.mesh_paths; 688 spin_lock_bh(&tbl->walk_lock); 689 mpath = rhashtable_lookup_get_insert_fast(&tbl->rhead, 690 &new_mpath->rhash, 691 mesh_rht_params); 692 if (!mpath) 693 hlist_add_head(&new_mpath->walk_list, &tbl->walk_head); 694 spin_unlock_bh(&tbl->walk_lock); 695 696 if (mpath) { 697 kfree(new_mpath); 698 699 if (IS_ERR(mpath)) 700 return mpath; 701 702 new_mpath = mpath; 703 } 704 705 sdata->u.mesh.mesh_paths_generation++; 706 return new_mpath; 707} 708 709int mpp_path_add(struct ieee80211_sub_if_data *sdata, 710 const u8 *dst, const u8 *mpp) 711{ 712 struct mesh_table *tbl; 713 struct mesh_path *new_mpath; 714 int ret; 715 716 if (ether_addr_equal(dst, sdata->vif.addr)) 717 /* never add ourselves as neighbours */ 718 return -EOPNOTSUPP; 719 720 if (is_multicast_ether_addr(dst)) 721 return -EOPNOTSUPP; 722 723 new_mpath = mesh_path_new(sdata, dst, GFP_ATOMIC); 724 725 if (!new_mpath) 726 return -ENOMEM; 727 728 memcpy(new_mpath->mpp, mpp, ETH_ALEN); 729 tbl = &sdata->u.mesh.mpp_paths; 730 731 spin_lock_bh(&tbl->walk_lock); 732 ret = rhashtable_lookup_insert_fast(&tbl->rhead, 733 &new_mpath->rhash, 734 mesh_rht_params); 735 if (!ret) 736 hlist_add_head_rcu(&new_mpath->walk_list, &tbl->walk_head); 737 spin_unlock_bh(&tbl->walk_lock); 738 739 if (ret) 740 kfree(new_mpath); 741 else 742 mesh_fast_tx_flush_addr(sdata, dst); 743 744 sdata->u.mesh.mpp_paths_generation++; 745 return ret; 746} 747 748 749/** 750 * mesh_plink_broken - deactivates paths and sends perr when a link breaks 751 * 752 * @sta: broken peer link 753 * 754 * This function must be called from the rate control algorithm if enough 755 * delivery errors suggest that a peer link is no longer usable. 756 */ 757void mesh_plink_broken(struct sta_info *sta) 758{ 759 struct ieee80211_sub_if_data *sdata = sta->sdata; 760 struct mesh_table *tbl = &sdata->u.mesh.mesh_paths; 761 static const u8 bcast[ETH_ALEN] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff}; 762 struct mesh_path *mpath; 763 764 rcu_read_lock(); 765 hlist_for_each_entry_rcu(mpath, &tbl->walk_head, walk_list) { 766 if (rcu_access_pointer(mpath->next_hop) == sta && 767 mpath->flags & MESH_PATH_ACTIVE && 768 !(mpath->flags & MESH_PATH_FIXED)) { 769 spin_lock_bh(&mpath->state_lock); 770 mpath->flags &= ~MESH_PATH_ACTIVE; 771 ++mpath->sn; 772 spin_unlock_bh(&mpath->state_lock); 773 mesh_path_error_tx(sdata, 774 sdata->u.mesh.mshcfg.element_ttl, 775 mpath->dst, mpath->sn, 776 WLAN_REASON_MESH_PATH_DEST_UNREACHABLE, bcast); 777 } 778 } 779 rcu_read_unlock(); 780} 781 782static void mesh_path_free_rcu(struct mesh_table *tbl, 783 struct mesh_path *mpath) 784{ 785 struct ieee80211_sub_if_data *sdata = mpath->sdata; 786 787 spin_lock_bh(&mpath->state_lock); 788 mpath->flags |= MESH_PATH_RESOLVING | MESH_PATH_DELETED; 789 mesh_gate_del(tbl, mpath); 790 spin_unlock_bh(&mpath->state_lock); 791 timer_shutdown_sync(&mpath->timer); 792 atomic_dec(&sdata->u.mesh.mpaths); 793 atomic_dec(&tbl->entries); 794 mesh_path_flush_pending(mpath); 795 kfree_rcu(mpath, rcu); 796} 797 798static void __mesh_path_del(struct mesh_table *tbl, struct mesh_path *mpath) 799{ 800 hlist_del_rcu(&mpath->walk_list); 801 rhashtable_remove_fast(&tbl->rhead, &mpath->rhash, mesh_rht_params); 802 if (tbl == &mpath->sdata->u.mesh.mpp_paths) 803 mesh_fast_tx_flush_addr(mpath->sdata, mpath->dst); 804 else 805 mesh_fast_tx_flush_mpath(mpath); 806 mesh_path_free_rcu(tbl, mpath); 807} 808 809/** 810 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches 811 * 812 * @sta: mesh peer to match 813 * 814 * RCU notes: this function is called when a mesh plink transitions from 815 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that 816 * allows path creation. This will happen before the sta can be freed (because 817 * sta_info_destroy() calls this) so any reader in a rcu read block will be 818 * protected against the plink disappearing. 819 */ 820void mesh_path_flush_by_nexthop(struct sta_info *sta) 821{ 822 struct ieee80211_sub_if_data *sdata = sta->sdata; 823 struct mesh_table *tbl = &sdata->u.mesh.mesh_paths; 824 struct mesh_path *mpath; 825 struct hlist_node *n; 826 827 spin_lock_bh(&tbl->walk_lock); 828 hlist_for_each_entry_safe(mpath, n, &tbl->walk_head, walk_list) { 829 if (rcu_access_pointer(mpath->next_hop) == sta) 830 __mesh_path_del(tbl, mpath); 831 } 832 spin_unlock_bh(&tbl->walk_lock); 833} 834 835static void mpp_flush_by_proxy(struct ieee80211_sub_if_data *sdata, 836 const u8 *proxy) 837{ 838 struct mesh_table *tbl = &sdata->u.mesh.mpp_paths; 839 struct mesh_path *mpath; 840 struct hlist_node *n; 841 842 spin_lock_bh(&tbl->walk_lock); 843 hlist_for_each_entry_safe(mpath, n, &tbl->walk_head, walk_list) { 844 if (ether_addr_equal(mpath->mpp, proxy)) 845 __mesh_path_del(tbl, mpath); 846 } 847 spin_unlock_bh(&tbl->walk_lock); 848} 849 850static void table_flush_by_iface(struct mesh_table *tbl) 851{ 852 struct mesh_path *mpath; 853 struct hlist_node *n; 854 855 spin_lock_bh(&tbl->walk_lock); 856 hlist_for_each_entry_safe(mpath, n, &tbl->walk_head, walk_list) { 857 __mesh_path_del(tbl, mpath); 858 } 859 spin_unlock_bh(&tbl->walk_lock); 860} 861 862/** 863 * mesh_path_flush_by_iface - Deletes all mesh paths associated with a given iface 864 * 865 * @sdata: interface data to match 866 * 867 * This function deletes both mesh paths as well as mesh portal paths. 868 */ 869void mesh_path_flush_by_iface(struct ieee80211_sub_if_data *sdata) 870{ 871 table_flush_by_iface(&sdata->u.mesh.mesh_paths); 872 table_flush_by_iface(&sdata->u.mesh.mpp_paths); 873} 874 875/** 876 * table_path_del - delete a path from the mesh or mpp table 877 * 878 * @tbl: mesh or mpp path table 879 * @sdata: local subif 880 * @addr: dst address (ETH_ALEN length) 881 * 882 * Returns: 0 if successful 883 */ 884static int table_path_del(struct mesh_table *tbl, 885 struct ieee80211_sub_if_data *sdata, 886 const u8 *addr) 887{ 888 struct mesh_path *mpath; 889 890 spin_lock_bh(&tbl->walk_lock); 891 mpath = rhashtable_lookup_fast(&tbl->rhead, addr, mesh_rht_params); 892 if (!mpath) { 893 spin_unlock_bh(&tbl->walk_lock); 894 return -ENXIO; 895 } 896 897 __mesh_path_del(tbl, mpath); 898 spin_unlock_bh(&tbl->walk_lock); 899 return 0; 900} 901 902 903/** 904 * mesh_path_del - delete a mesh path from the table 905 * 906 * @addr: dst address (ETH_ALEN length) 907 * @sdata: local subif 908 * 909 * Returns: 0 if successful 910 */ 911int mesh_path_del(struct ieee80211_sub_if_data *sdata, const u8 *addr) 912{ 913 int err; 914 915 /* flush relevant mpp entries first */ 916 mpp_flush_by_proxy(sdata, addr); 917 918 err = table_path_del(&sdata->u.mesh.mesh_paths, sdata, addr); 919 sdata->u.mesh.mesh_paths_generation++; 920 return err; 921} 922 923/** 924 * mesh_path_tx_pending - sends pending frames in a mesh path queue 925 * 926 * @mpath: mesh path to activate 927 * 928 * Locking: the state_lock of the mpath structure must NOT be held when calling 929 * this function. 930 */ 931void mesh_path_tx_pending(struct mesh_path *mpath) 932{ 933 if (mpath->flags & MESH_PATH_ACTIVE) 934 ieee80211_add_pending_skbs(mpath->sdata->local, 935 &mpath->frame_queue); 936} 937 938/** 939 * mesh_path_send_to_gates - sends pending frames to all known mesh gates 940 * 941 * @mpath: mesh path whose queue will be emptied 942 * 943 * If there is only one gate, the frames are transferred from the failed mpath 944 * queue to that gate's queue. If there are more than one gates, the frames 945 * are copied from each gate to the next. After frames are copied, the 946 * mpath queues are emptied onto the transmission queue. 947 * 948 * Returns: 0 on success, -EHOSTUNREACH 949 */ 950int mesh_path_send_to_gates(struct mesh_path *mpath) 951{ 952 struct ieee80211_sub_if_data *sdata = mpath->sdata; 953 struct mesh_table *tbl; 954 struct mesh_path *from_mpath = mpath; 955 struct mesh_path *gate; 956 bool copy = false; 957 958 tbl = &sdata->u.mesh.mesh_paths; 959 960 rcu_read_lock(); 961 hlist_for_each_entry_rcu(gate, &tbl->known_gates, gate_list) { 962 if (gate->flags & MESH_PATH_ACTIVE) { 963 mpath_dbg(sdata, "Forwarding to %pM\n", gate->dst); 964 mesh_path_move_to_queue(gate, from_mpath, copy); 965 from_mpath = gate; 966 copy = true; 967 } else { 968 mpath_dbg(sdata, 969 "Not forwarding to %pM (flags %#x)\n", 970 gate->dst, gate->flags); 971 } 972 } 973 974 hlist_for_each_entry_rcu(gate, &tbl->known_gates, gate_list) { 975 mpath_dbg(sdata, "Sending to %pM\n", gate->dst); 976 mesh_path_tx_pending(gate); 977 } 978 rcu_read_unlock(); 979 980 return (from_mpath == mpath) ? -EHOSTUNREACH : 0; 981} 982 983/** 984 * mesh_path_discard_frame - discard a frame whose path could not be resolved 985 * 986 * @skb: frame to discard 987 * @sdata: network subif the frame was to be sent through 988 * 989 * Locking: the function must me called within a rcu_read_lock region 990 */ 991void mesh_path_discard_frame(struct ieee80211_sub_if_data *sdata, 992 struct sk_buff *skb) 993{ 994 ieee80211_free_txskb(&sdata->local->hw, skb); 995 sdata->u.mesh.mshstats.dropped_frames_no_route++; 996} 997 998/** 999 * mesh_path_flush_pending - free the pending queue of a mesh path 1000 * 1001 * @mpath: mesh path whose queue has to be freed 1002 * 1003 * Locking: the function must me called within a rcu_read_lock region 1004 */ 1005void mesh_path_flush_pending(struct mesh_path *mpath) 1006{ 1007 struct sk_buff *skb; 1008 1009 while ((skb = skb_dequeue(&mpath->frame_queue)) != NULL) 1010 mesh_path_discard_frame(mpath->sdata, skb); 1011} 1012 1013/** 1014 * mesh_path_fix_nexthop - force a specific next hop for a mesh path 1015 * 1016 * @mpath: the mesh path to modify 1017 * @next_hop: the next hop to force 1018 * 1019 * Locking: this function must be called holding mpath->state_lock 1020 */ 1021void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop) 1022{ 1023 spin_lock_bh(&mpath->state_lock); 1024 mesh_path_assign_nexthop(mpath, next_hop); 1025 mpath->sn = 0xffff; 1026 mpath->metric = 0; 1027 mpath->hop_count = 0; 1028 mpath->exp_time = 0; 1029 mpath->flags = MESH_PATH_FIXED | MESH_PATH_SN_VALID; 1030 mesh_path_activate(mpath); 1031 mesh_fast_tx_flush_mpath(mpath); 1032 spin_unlock_bh(&mpath->state_lock); 1033 ewma_mesh_fail_avg_init(&next_hop->mesh->fail_avg); 1034 /* init it at a low value - 0 start is tricky */ 1035 ewma_mesh_fail_avg_add(&next_hop->mesh->fail_avg, 1); 1036 mesh_path_tx_pending(mpath); 1037} 1038 1039void mesh_pathtbl_init(struct ieee80211_sub_if_data *sdata) 1040{ 1041 mesh_table_init(&sdata->u.mesh.mesh_paths); 1042 mesh_table_init(&sdata->u.mesh.mpp_paths); 1043 mesh_fast_tx_init(sdata); 1044} 1045 1046static 1047void mesh_path_tbl_expire(struct ieee80211_sub_if_data *sdata, 1048 struct mesh_table *tbl) 1049{ 1050 struct mesh_path *mpath; 1051 struct hlist_node *n; 1052 1053 spin_lock_bh(&tbl->walk_lock); 1054 hlist_for_each_entry_safe(mpath, n, &tbl->walk_head, walk_list) { 1055 if ((!(mpath->flags & MESH_PATH_RESOLVING)) && 1056 (!(mpath->flags & MESH_PATH_FIXED)) && 1057 time_after(jiffies, mpath->exp_time + MESH_PATH_EXPIRE)) 1058 __mesh_path_del(tbl, mpath); 1059 } 1060 spin_unlock_bh(&tbl->walk_lock); 1061} 1062 1063void mesh_path_expire(struct ieee80211_sub_if_data *sdata) 1064{ 1065 mesh_path_tbl_expire(sdata, &sdata->u.mesh.mesh_paths); 1066 mesh_path_tbl_expire(sdata, &sdata->u.mesh.mpp_paths); 1067} 1068 1069void mesh_pathtbl_unregister(struct ieee80211_sub_if_data *sdata) 1070{ 1071 mesh_fast_tx_deinit(sdata); 1072 mesh_table_free(&sdata->u.mesh.mesh_paths); 1073 mesh_table_free(&sdata->u.mesh.mpp_paths); 1074} 1075