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