1eb2b9311SLuis Carlos Cobo /* 2eb2b9311SLuis Carlos Cobo * Copyright (c) 2008 open80211s Ltd. 3eb2b9311SLuis Carlos Cobo * Author: Luis Carlos Cobo <luisca@cozybit.com> 4eb2b9311SLuis Carlos Cobo * 5eb2b9311SLuis Carlos Cobo * This program is free software; you can redistribute it and/or modify 6eb2b9311SLuis Carlos Cobo * it under the terms of the GNU General Public License version 2 as 7eb2b9311SLuis Carlos Cobo * published by the Free Software Foundation. 8eb2b9311SLuis Carlos Cobo */ 9eb2b9311SLuis Carlos Cobo 10eb2b9311SLuis Carlos Cobo #include <linux/etherdevice.h> 11eb2b9311SLuis Carlos Cobo #include <linux/list.h> 12eb2b9311SLuis Carlos Cobo #include <linux/random.h> 13eb2b9311SLuis Carlos Cobo #include <linux/spinlock.h> 14eb2b9311SLuis Carlos Cobo #include <linux/string.h> 15eb2b9311SLuis Carlos Cobo #include <net/mac80211.h> 16eb2b9311SLuis Carlos Cobo #include "ieee80211_i.h" 17eb2b9311SLuis Carlos Cobo #include "mesh.h" 18eb2b9311SLuis Carlos Cobo 19eb2b9311SLuis Carlos Cobo /* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */ 20eb2b9311SLuis Carlos Cobo #define INIT_PATHS_SIZE_ORDER 2 21eb2b9311SLuis Carlos Cobo 22eb2b9311SLuis Carlos Cobo /* Keep the mean chain length below this constant */ 23eb2b9311SLuis Carlos Cobo #define MEAN_CHAIN_LEN 2 24eb2b9311SLuis Carlos Cobo 25eb2b9311SLuis Carlos Cobo #define MPATH_EXPIRED(mpath) ((mpath->flags & MESH_PATH_ACTIVE) && \ 26eb2b9311SLuis Carlos Cobo time_after(jiffies, mpath->exp_time) && \ 27eb2b9311SLuis Carlos Cobo !(mpath->flags & MESH_PATH_FIXED)) 28eb2b9311SLuis Carlos Cobo 29eb2b9311SLuis Carlos Cobo struct mpath_node { 30eb2b9311SLuis Carlos Cobo struct hlist_node list; 31eb2b9311SLuis Carlos Cobo struct rcu_head rcu; 32eb2b9311SLuis Carlos Cobo /* This indirection allows two different tables to point to the same 33eb2b9311SLuis Carlos Cobo * mesh_path structure, useful when resizing 34eb2b9311SLuis Carlos Cobo */ 35eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 36eb2b9311SLuis Carlos Cobo }; 37eb2b9311SLuis Carlos Cobo 38eb2b9311SLuis Carlos Cobo static struct mesh_table *mesh_paths; 39eb2b9311SLuis Carlos Cobo 40eb2b9311SLuis Carlos Cobo /* This lock will have the grow table function as writer and add / delete nodes 41eb2b9311SLuis Carlos Cobo * as readers. When reading the table (i.e. doing lookups) we are well protected 42eb2b9311SLuis Carlos Cobo * by RCU 43eb2b9311SLuis Carlos Cobo */ 44eb2b9311SLuis Carlos Cobo static DEFINE_RWLOCK(pathtbl_resize_lock); 45eb2b9311SLuis Carlos Cobo 46eb2b9311SLuis Carlos Cobo /** 47eb2b9311SLuis Carlos Cobo * 48eb2b9311SLuis Carlos Cobo * mesh_path_assign_nexthop - update mesh path next hop 49eb2b9311SLuis Carlos Cobo * 50eb2b9311SLuis Carlos Cobo * @mpath: mesh path to update 51eb2b9311SLuis Carlos Cobo * @sta: next hop to assign 52eb2b9311SLuis Carlos Cobo * 53eb2b9311SLuis Carlos Cobo * Locking: mpath->state_lock must be held when calling this function 54eb2b9311SLuis Carlos Cobo */ 55eb2b9311SLuis Carlos Cobo void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta) 56eb2b9311SLuis Carlos Cobo { 57d0709a65SJohannes Berg rcu_assign_pointer(mpath->next_hop, sta); 58eb2b9311SLuis Carlos Cobo } 59eb2b9311SLuis Carlos Cobo 60eb2b9311SLuis Carlos Cobo 61eb2b9311SLuis Carlos Cobo /** 62eb2b9311SLuis Carlos Cobo * mesh_path_lookup - look up a path in the mesh path table 63eb2b9311SLuis Carlos Cobo * @dst: hardware address (ETH_ALEN length) of destination 64f698d856SJasper Bryant-Greene * @sdata: local subif 65eb2b9311SLuis Carlos Cobo * 66eb2b9311SLuis Carlos Cobo * Returns: pointer to the mesh path structure, or NULL if not found 67eb2b9311SLuis Carlos Cobo * 68eb2b9311SLuis Carlos Cobo * Locking: must be called within a read rcu section. 69eb2b9311SLuis Carlos Cobo */ 70f698d856SJasper Bryant-Greene struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata) 71eb2b9311SLuis Carlos Cobo { 72eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 73eb2b9311SLuis Carlos Cobo struct hlist_node *n; 74eb2b9311SLuis Carlos Cobo struct hlist_head *bucket; 75eb2b9311SLuis Carlos Cobo struct mesh_table *tbl; 76eb2b9311SLuis Carlos Cobo struct mpath_node *node; 77eb2b9311SLuis Carlos Cobo 78eb2b9311SLuis Carlos Cobo tbl = rcu_dereference(mesh_paths); 79eb2b9311SLuis Carlos Cobo 80f698d856SJasper Bryant-Greene bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)]; 81eb2b9311SLuis Carlos Cobo hlist_for_each_entry_rcu(node, n, bucket, list) { 82eb2b9311SLuis Carlos Cobo mpath = node->mpath; 83f698d856SJasper Bryant-Greene if (mpath->sdata == sdata && 84eb2b9311SLuis Carlos Cobo memcmp(dst, mpath->dst, ETH_ALEN) == 0) { 85eb2b9311SLuis Carlos Cobo if (MPATH_EXPIRED(mpath)) { 86eb2b9311SLuis Carlos Cobo spin_lock_bh(&mpath->state_lock); 87eb2b9311SLuis Carlos Cobo if (MPATH_EXPIRED(mpath)) 88eb2b9311SLuis Carlos Cobo mpath->flags &= ~MESH_PATH_ACTIVE; 89eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 90eb2b9311SLuis Carlos Cobo } 91eb2b9311SLuis Carlos Cobo return mpath; 92eb2b9311SLuis Carlos Cobo } 93eb2b9311SLuis Carlos Cobo } 94eb2b9311SLuis Carlos Cobo return NULL; 95eb2b9311SLuis Carlos Cobo } 96eb2b9311SLuis Carlos Cobo 97eb2b9311SLuis Carlos Cobo /** 98eb2b9311SLuis Carlos Cobo * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index 99eb2b9311SLuis Carlos Cobo * @idx: index 100f698d856SJasper Bryant-Greene * @sdata: local subif, or NULL for all entries 101eb2b9311SLuis Carlos Cobo * 102eb2b9311SLuis Carlos Cobo * Returns: pointer to the mesh path structure, or NULL if not found. 103eb2b9311SLuis Carlos Cobo * 104eb2b9311SLuis Carlos Cobo * Locking: must be called within a read rcu section. 105eb2b9311SLuis Carlos Cobo */ 106f698d856SJasper Bryant-Greene struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data *sdata) 107eb2b9311SLuis Carlos Cobo { 108eb2b9311SLuis Carlos Cobo struct mpath_node *node; 109eb2b9311SLuis Carlos Cobo struct hlist_node *p; 110eb2b9311SLuis Carlos Cobo int i; 111eb2b9311SLuis Carlos Cobo int j = 0; 112eb2b9311SLuis Carlos Cobo 1132a8ca29aSLuis Carlos Cobo for_each_mesh_entry(mesh_paths, p, node, i) { 114f698d856SJasper Bryant-Greene if (sdata && node->mpath->sdata != sdata) 1152a8ca29aSLuis Carlos Cobo continue; 116eb2b9311SLuis Carlos Cobo if (j++ == idx) { 117eb2b9311SLuis Carlos Cobo if (MPATH_EXPIRED(node->mpath)) { 118eb2b9311SLuis Carlos Cobo spin_lock_bh(&node->mpath->state_lock); 119eb2b9311SLuis Carlos Cobo if (MPATH_EXPIRED(node->mpath)) 120eb2b9311SLuis Carlos Cobo node->mpath->flags &= ~MESH_PATH_ACTIVE; 121eb2b9311SLuis Carlos Cobo spin_unlock_bh(&node->mpath->state_lock); 122eb2b9311SLuis Carlos Cobo } 123eb2b9311SLuis Carlos Cobo return node->mpath; 124eb2b9311SLuis Carlos Cobo } 1252a8ca29aSLuis Carlos Cobo } 126eb2b9311SLuis Carlos Cobo 127eb2b9311SLuis Carlos Cobo return NULL; 128eb2b9311SLuis Carlos Cobo } 129eb2b9311SLuis Carlos Cobo 130eb2b9311SLuis Carlos Cobo /** 131eb2b9311SLuis Carlos Cobo * mesh_path_add - allocate and add a new path to the mesh path table 132eb2b9311SLuis Carlos Cobo * @addr: destination address of the path (ETH_ALEN length) 133f698d856SJasper Bryant-Greene * @sdata: local subif 134eb2b9311SLuis Carlos Cobo * 135eb2b9311SLuis Carlos Cobo * Returns: 0 on sucess 136eb2b9311SLuis Carlos Cobo * 137eb2b9311SLuis Carlos Cobo * State: the initial state of the new path is set to 0 138eb2b9311SLuis Carlos Cobo */ 139f698d856SJasper Bryant-Greene int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata) 140eb2b9311SLuis Carlos Cobo { 141eb2b9311SLuis Carlos Cobo struct mesh_path *mpath, *new_mpath; 142eb2b9311SLuis Carlos Cobo struct mpath_node *node, *new_node; 143eb2b9311SLuis Carlos Cobo struct hlist_head *bucket; 144eb2b9311SLuis Carlos Cobo struct hlist_node *n; 145eb2b9311SLuis Carlos Cobo int grow = 0; 146eb2b9311SLuis Carlos Cobo int err = 0; 147eb2b9311SLuis Carlos Cobo u32 hash_idx; 148eb2b9311SLuis Carlos Cobo 149f698d856SJasper Bryant-Greene if (memcmp(dst, sdata->dev->dev_addr, ETH_ALEN) == 0) 150eb2b9311SLuis Carlos Cobo /* never add ourselves as neighbours */ 151eb2b9311SLuis Carlos Cobo return -ENOTSUPP; 152eb2b9311SLuis Carlos Cobo 153eb2b9311SLuis Carlos Cobo if (is_multicast_ether_addr(dst)) 154eb2b9311SLuis Carlos Cobo return -ENOTSUPP; 155eb2b9311SLuis Carlos Cobo 156eb2b9311SLuis Carlos Cobo if (atomic_add_unless(&sdata->u.sta.mpaths, 1, MESH_MAX_MPATHS) == 0) 157eb2b9311SLuis Carlos Cobo return -ENOSPC; 158eb2b9311SLuis Carlos Cobo 159402d7752SPavel Emelyanov err = -ENOMEM; 160eb2b9311SLuis Carlos Cobo new_mpath = kzalloc(sizeof(struct mesh_path), GFP_KERNEL); 161402d7752SPavel Emelyanov if (!new_mpath) 162402d7752SPavel Emelyanov goto err_path_alloc; 163402d7752SPavel Emelyanov 1640eb03d5aSPavel Emelyanov new_node = kmalloc(sizeof(struct mpath_node), GFP_KERNEL); 165402d7752SPavel Emelyanov if (!new_node) 166402d7752SPavel Emelyanov goto err_node_alloc; 167f84e71a9SPavel Emelyanov 168f84e71a9SPavel Emelyanov read_lock(&pathtbl_resize_lock); 169eb2b9311SLuis Carlos Cobo memcpy(new_mpath->dst, dst, ETH_ALEN); 170f698d856SJasper Bryant-Greene new_mpath->sdata = sdata; 171eb2b9311SLuis Carlos Cobo new_mpath->flags = 0; 172eb2b9311SLuis Carlos Cobo skb_queue_head_init(&new_mpath->frame_queue); 173eb2b9311SLuis Carlos Cobo new_node->mpath = new_mpath; 174eb2b9311SLuis Carlos Cobo new_mpath->timer.data = (unsigned long) new_mpath; 175eb2b9311SLuis Carlos Cobo new_mpath->timer.function = mesh_path_timer; 176eb2b9311SLuis Carlos Cobo new_mpath->exp_time = jiffies; 177eb2b9311SLuis Carlos Cobo spin_lock_init(&new_mpath->state_lock); 178eb2b9311SLuis Carlos Cobo init_timer(&new_mpath->timer); 179eb2b9311SLuis Carlos Cobo 180f698d856SJasper Bryant-Greene hash_idx = mesh_table_hash(dst, sdata, mesh_paths); 181eb2b9311SLuis Carlos Cobo bucket = &mesh_paths->hash_buckets[hash_idx]; 182eb2b9311SLuis Carlos Cobo 183eb2b9311SLuis Carlos Cobo spin_lock(&mesh_paths->hashwlock[hash_idx]); 184eb2b9311SLuis Carlos Cobo 185402d7752SPavel Emelyanov err = -EEXIST; 186eb2b9311SLuis Carlos Cobo hlist_for_each_entry(node, n, bucket, list) { 187eb2b9311SLuis Carlos Cobo mpath = node->mpath; 188f698d856SJasper Bryant-Greene if (mpath->sdata == sdata && memcmp(dst, mpath->dst, ETH_ALEN) == 0) 189402d7752SPavel Emelyanov goto err_exists; 190eb2b9311SLuis Carlos Cobo } 191eb2b9311SLuis Carlos Cobo 192eb2b9311SLuis Carlos Cobo hlist_add_head_rcu(&new_node->list, bucket); 193eb2b9311SLuis Carlos Cobo if (atomic_inc_return(&mesh_paths->entries) >= 194eb2b9311SLuis Carlos Cobo mesh_paths->mean_chain_len * (mesh_paths->hash_mask + 1)) 195eb2b9311SLuis Carlos Cobo grow = 1; 196eb2b9311SLuis Carlos Cobo 197eb2b9311SLuis Carlos Cobo spin_unlock(&mesh_paths->hashwlock[hash_idx]); 198eb2b9311SLuis Carlos Cobo read_unlock(&pathtbl_resize_lock); 199402d7752SPavel Emelyanov if (grow) { 200eb2b9311SLuis Carlos Cobo struct mesh_table *oldtbl, *newtbl; 201eb2b9311SLuis Carlos Cobo 202eb2b9311SLuis Carlos Cobo write_lock(&pathtbl_resize_lock); 203eb2b9311SLuis Carlos Cobo oldtbl = mesh_paths; 204eb2b9311SLuis Carlos Cobo newtbl = mesh_table_grow(mesh_paths); 205eb2b9311SLuis Carlos Cobo if (!newtbl) { 206eb2b9311SLuis Carlos Cobo write_unlock(&pathtbl_resize_lock); 2073282aea9SPavel Emelyanov return 0; 208eb2b9311SLuis Carlos Cobo } 209eb2b9311SLuis Carlos Cobo rcu_assign_pointer(mesh_paths, newtbl); 2106d6936e2SPavel Emelyanov write_unlock(&pathtbl_resize_lock); 2116d6936e2SPavel Emelyanov 212eb2b9311SLuis Carlos Cobo synchronize_rcu(); 213eb2b9311SLuis Carlos Cobo mesh_table_free(oldtbl, false); 214eb2b9311SLuis Carlos Cobo } 215402d7752SPavel Emelyanov return 0; 216402d7752SPavel Emelyanov 217402d7752SPavel Emelyanov err_exists: 218402d7752SPavel Emelyanov spin_unlock(&mesh_paths->hashwlock[hash_idx]); 219402d7752SPavel Emelyanov read_unlock(&pathtbl_resize_lock); 220402d7752SPavel Emelyanov kfree(new_node); 221402d7752SPavel Emelyanov err_node_alloc: 222402d7752SPavel Emelyanov kfree(new_mpath); 223402d7752SPavel Emelyanov err_path_alloc: 224402d7752SPavel Emelyanov atomic_dec(&sdata->u.sta.mpaths); 225eb2b9311SLuis Carlos Cobo return err; 226eb2b9311SLuis Carlos Cobo } 227eb2b9311SLuis Carlos Cobo 228eb2b9311SLuis Carlos Cobo 229eb2b9311SLuis Carlos Cobo /** 230eb2b9311SLuis Carlos Cobo * mesh_plink_broken - deactivates paths and sends perr when a link breaks 231eb2b9311SLuis Carlos Cobo * 232eb2b9311SLuis Carlos Cobo * @sta: broken peer link 233eb2b9311SLuis Carlos Cobo * 234eb2b9311SLuis Carlos Cobo * This function must be called from the rate control algorithm if enough 235eb2b9311SLuis Carlos Cobo * delivery errors suggest that a peer link is no longer usable. 236eb2b9311SLuis Carlos Cobo */ 237eb2b9311SLuis Carlos Cobo void mesh_plink_broken(struct sta_info *sta) 238eb2b9311SLuis Carlos Cobo { 239eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 240eb2b9311SLuis Carlos Cobo struct mpath_node *node; 241eb2b9311SLuis Carlos Cobo struct hlist_node *p; 242f698d856SJasper Bryant-Greene struct ieee80211_sub_if_data *sdata = sta->sdata; 243eb2b9311SLuis Carlos Cobo int i; 244eb2b9311SLuis Carlos Cobo 245eb2b9311SLuis Carlos Cobo rcu_read_lock(); 246eb2b9311SLuis Carlos Cobo for_each_mesh_entry(mesh_paths, p, node, i) { 247eb2b9311SLuis Carlos Cobo mpath = node->mpath; 248eb2b9311SLuis Carlos Cobo spin_lock_bh(&mpath->state_lock); 249eb2b9311SLuis Carlos Cobo if (mpath->next_hop == sta && 250eb2b9311SLuis Carlos Cobo mpath->flags & MESH_PATH_ACTIVE && 251eb2b9311SLuis Carlos Cobo !(mpath->flags & MESH_PATH_FIXED)) { 252eb2b9311SLuis Carlos Cobo mpath->flags &= ~MESH_PATH_ACTIVE; 253eb2b9311SLuis Carlos Cobo ++mpath->dsn; 254eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 255eb2b9311SLuis Carlos Cobo mesh_path_error_tx(mpath->dst, 256eb2b9311SLuis Carlos Cobo cpu_to_le32(mpath->dsn), 257f698d856SJasper Bryant-Greene sdata->dev->broadcast, sdata); 258eb2b9311SLuis Carlos Cobo } else 259eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 260eb2b9311SLuis Carlos Cobo } 261eb2b9311SLuis Carlos Cobo rcu_read_unlock(); 262eb2b9311SLuis Carlos Cobo } 263eb2b9311SLuis Carlos Cobo 264eb2b9311SLuis Carlos Cobo /** 265eb2b9311SLuis Carlos Cobo * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches 266eb2b9311SLuis Carlos Cobo * 267eb2b9311SLuis Carlos Cobo * @sta - mesh peer to match 268eb2b9311SLuis Carlos Cobo * 269b4e08ea1SLuis Carlos Cobo * RCU notes: this function is called when a mesh plink transitions from 270b4e08ea1SLuis Carlos Cobo * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that 271b4e08ea1SLuis Carlos Cobo * allows path creation. This will happen before the sta can be freed (because 272d0709a65SJohannes Berg * sta_info_destroy() calls this) so any reader in a rcu read block will be 273d0709a65SJohannes Berg * protected against the plink disappearing. 274eb2b9311SLuis Carlos Cobo */ 275eb2b9311SLuis Carlos Cobo void mesh_path_flush_by_nexthop(struct sta_info *sta) 276eb2b9311SLuis Carlos Cobo { 277eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 278eb2b9311SLuis Carlos Cobo struct mpath_node *node; 279eb2b9311SLuis Carlos Cobo struct hlist_node *p; 280eb2b9311SLuis Carlos Cobo int i; 281eb2b9311SLuis Carlos Cobo 282eb2b9311SLuis Carlos Cobo for_each_mesh_entry(mesh_paths, p, node, i) { 283eb2b9311SLuis Carlos Cobo mpath = node->mpath; 284eb2b9311SLuis Carlos Cobo if (mpath->next_hop == sta) 285f698d856SJasper Bryant-Greene mesh_path_del(mpath->dst, mpath->sdata); 286eb2b9311SLuis Carlos Cobo } 287eb2b9311SLuis Carlos Cobo } 288eb2b9311SLuis Carlos Cobo 289f698d856SJasper Bryant-Greene void mesh_path_flush(struct ieee80211_sub_if_data *sdata) 290eb2b9311SLuis Carlos Cobo { 291eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 292eb2b9311SLuis Carlos Cobo struct mpath_node *node; 293eb2b9311SLuis Carlos Cobo struct hlist_node *p; 294eb2b9311SLuis Carlos Cobo int i; 295eb2b9311SLuis Carlos Cobo 296eb2b9311SLuis Carlos Cobo for_each_mesh_entry(mesh_paths, p, node, i) { 297eb2b9311SLuis Carlos Cobo mpath = node->mpath; 298f698d856SJasper Bryant-Greene if (mpath->sdata == sdata) 299f698d856SJasper Bryant-Greene mesh_path_del(mpath->dst, mpath->sdata); 300eb2b9311SLuis Carlos Cobo } 301eb2b9311SLuis Carlos Cobo } 302eb2b9311SLuis Carlos Cobo 303eb2b9311SLuis Carlos Cobo static void mesh_path_node_reclaim(struct rcu_head *rp) 304eb2b9311SLuis Carlos Cobo { 305eb2b9311SLuis Carlos Cobo struct mpath_node *node = container_of(rp, struct mpath_node, rcu); 306f698d856SJasper Bryant-Greene struct ieee80211_sub_if_data *sdata = node->mpath->sdata; 307d0709a65SJohannes Berg 30889a1ad69SLuis Carlos Cobo del_timer_sync(&node->mpath->timer); 309eb2b9311SLuis Carlos Cobo atomic_dec(&sdata->u.sta.mpaths); 310eb2b9311SLuis Carlos Cobo kfree(node->mpath); 311eb2b9311SLuis Carlos Cobo kfree(node); 312eb2b9311SLuis Carlos Cobo } 313eb2b9311SLuis Carlos Cobo 314eb2b9311SLuis Carlos Cobo /** 315eb2b9311SLuis Carlos Cobo * mesh_path_del - delete a mesh path from the table 316eb2b9311SLuis Carlos Cobo * 317eb2b9311SLuis Carlos Cobo * @addr: dst address (ETH_ALEN length) 318f698d856SJasper Bryant-Greene * @sdata: local subif 319eb2b9311SLuis Carlos Cobo * 320eb2b9311SLuis Carlos Cobo * Returns: 0 if succesful 321eb2b9311SLuis Carlos Cobo */ 322f698d856SJasper Bryant-Greene int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata) 323eb2b9311SLuis Carlos Cobo { 324eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 325eb2b9311SLuis Carlos Cobo struct mpath_node *node; 326eb2b9311SLuis Carlos Cobo struct hlist_head *bucket; 327eb2b9311SLuis Carlos Cobo struct hlist_node *n; 328eb2b9311SLuis Carlos Cobo int hash_idx; 329eb2b9311SLuis Carlos Cobo int err = 0; 330eb2b9311SLuis Carlos Cobo 331eb2b9311SLuis Carlos Cobo read_lock(&pathtbl_resize_lock); 332f698d856SJasper Bryant-Greene hash_idx = mesh_table_hash(addr, sdata, mesh_paths); 333eb2b9311SLuis Carlos Cobo bucket = &mesh_paths->hash_buckets[hash_idx]; 334eb2b9311SLuis Carlos Cobo 335eb2b9311SLuis Carlos Cobo spin_lock(&mesh_paths->hashwlock[hash_idx]); 336eb2b9311SLuis Carlos Cobo hlist_for_each_entry(node, n, bucket, list) { 337eb2b9311SLuis Carlos Cobo mpath = node->mpath; 338f698d856SJasper Bryant-Greene if (mpath->sdata == sdata && 339eb2b9311SLuis Carlos Cobo memcmp(addr, mpath->dst, ETH_ALEN) == 0) { 340eb2b9311SLuis Carlos Cobo spin_lock_bh(&mpath->state_lock); 341eb2b9311SLuis Carlos Cobo mpath->flags |= MESH_PATH_RESOLVING; 342eb2b9311SLuis Carlos Cobo hlist_del_rcu(&node->list); 343eb2b9311SLuis Carlos Cobo call_rcu(&node->rcu, mesh_path_node_reclaim); 344eb2b9311SLuis Carlos Cobo atomic_dec(&mesh_paths->entries); 345eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 346eb2b9311SLuis Carlos Cobo goto enddel; 347eb2b9311SLuis Carlos Cobo } 348eb2b9311SLuis Carlos Cobo } 349eb2b9311SLuis Carlos Cobo 350eb2b9311SLuis Carlos Cobo err = -ENXIO; 351eb2b9311SLuis Carlos Cobo enddel: 352eb2b9311SLuis Carlos Cobo spin_unlock(&mesh_paths->hashwlock[hash_idx]); 353eb2b9311SLuis Carlos Cobo read_unlock(&pathtbl_resize_lock); 354eb2b9311SLuis Carlos Cobo return err; 355eb2b9311SLuis Carlos Cobo } 356eb2b9311SLuis Carlos Cobo 357eb2b9311SLuis Carlos Cobo /** 358eb2b9311SLuis Carlos Cobo * mesh_path_tx_pending - sends pending frames in a mesh path queue 359eb2b9311SLuis Carlos Cobo * 360eb2b9311SLuis Carlos Cobo * @mpath: mesh path to activate 361eb2b9311SLuis Carlos Cobo * 362eb2b9311SLuis Carlos Cobo * Locking: the state_lock of the mpath structure must NOT be held when calling 363eb2b9311SLuis Carlos Cobo * this function. 364eb2b9311SLuis Carlos Cobo */ 365eb2b9311SLuis Carlos Cobo void mesh_path_tx_pending(struct mesh_path *mpath) 366eb2b9311SLuis Carlos Cobo { 367eb2b9311SLuis Carlos Cobo struct sk_buff *skb; 368eb2b9311SLuis Carlos Cobo 369eb2b9311SLuis Carlos Cobo while ((skb = skb_dequeue(&mpath->frame_queue)) && 370eb2b9311SLuis Carlos Cobo (mpath->flags & MESH_PATH_ACTIVE)) 371eb2b9311SLuis Carlos Cobo dev_queue_xmit(skb); 372eb2b9311SLuis Carlos Cobo } 373eb2b9311SLuis Carlos Cobo 374eb2b9311SLuis Carlos Cobo /** 375eb2b9311SLuis Carlos Cobo * mesh_path_discard_frame - discard a frame whose path could not be resolved 376eb2b9311SLuis Carlos Cobo * 377eb2b9311SLuis Carlos Cobo * @skb: frame to discard 378f698d856SJasper Bryant-Greene * @sdata: network subif the frame was to be sent through 379eb2b9311SLuis Carlos Cobo * 380eb2b9311SLuis Carlos Cobo * If the frame was beign forwarded from another MP, a PERR frame will be sent 381eb2b9311SLuis Carlos Cobo * to the precursor. 382eb2b9311SLuis Carlos Cobo * 383eb2b9311SLuis Carlos Cobo * Locking: the function must me called within a rcu_read_lock region 384eb2b9311SLuis Carlos Cobo */ 385f698d856SJasper Bryant-Greene void mesh_path_discard_frame(struct sk_buff *skb, 386f698d856SJasper Bryant-Greene struct ieee80211_sub_if_data *sdata) 387eb2b9311SLuis Carlos Cobo { 388e32f85f7SLuis Carlos Cobo struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data; 389eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 390eb2b9311SLuis Carlos Cobo u32 dsn = 0; 391eb2b9311SLuis Carlos Cobo 392f698d856SJasper Bryant-Greene if (memcmp(hdr->addr4, sdata->dev->dev_addr, ETH_ALEN) != 0) { 393eb2b9311SLuis Carlos Cobo u8 *ra, *da; 394eb2b9311SLuis Carlos Cobo 395e32f85f7SLuis Carlos Cobo da = hdr->addr3; 396e32f85f7SLuis Carlos Cobo ra = hdr->addr2; 397f698d856SJasper Bryant-Greene mpath = mesh_path_lookup(da, sdata); 398eb2b9311SLuis Carlos Cobo if (mpath) 399eb2b9311SLuis Carlos Cobo dsn = ++mpath->dsn; 400f698d856SJasper Bryant-Greene mesh_path_error_tx(skb->data, cpu_to_le32(dsn), ra, sdata); 401eb2b9311SLuis Carlos Cobo } 402eb2b9311SLuis Carlos Cobo 403eb2b9311SLuis Carlos Cobo kfree_skb(skb); 404eb2b9311SLuis Carlos Cobo sdata->u.sta.mshstats.dropped_frames_no_route++; 405eb2b9311SLuis Carlos Cobo } 406eb2b9311SLuis Carlos Cobo 407eb2b9311SLuis Carlos Cobo /** 408eb2b9311SLuis Carlos Cobo * mesh_path_flush_pending - free the pending queue of a mesh path 409eb2b9311SLuis Carlos Cobo * 410eb2b9311SLuis Carlos Cobo * @mpath: mesh path whose queue has to be freed 411eb2b9311SLuis Carlos Cobo * 412eb2b9311SLuis Carlos Cobo * Locking: the function must me called withing a rcu_read_lock region 413eb2b9311SLuis Carlos Cobo */ 414eb2b9311SLuis Carlos Cobo void mesh_path_flush_pending(struct mesh_path *mpath) 415eb2b9311SLuis Carlos Cobo { 416eb2b9311SLuis Carlos Cobo struct sk_buff *skb; 417eb2b9311SLuis Carlos Cobo 418eb2b9311SLuis Carlos Cobo while ((skb = skb_dequeue(&mpath->frame_queue)) && 419eb2b9311SLuis Carlos Cobo (mpath->flags & MESH_PATH_ACTIVE)) 420f698d856SJasper Bryant-Greene mesh_path_discard_frame(skb, mpath->sdata); 421eb2b9311SLuis Carlos Cobo } 422eb2b9311SLuis Carlos Cobo 423eb2b9311SLuis Carlos Cobo /** 424eb2b9311SLuis Carlos Cobo * mesh_path_fix_nexthop - force a specific next hop for a mesh path 425eb2b9311SLuis Carlos Cobo * 426eb2b9311SLuis Carlos Cobo * @mpath: the mesh path to modify 427eb2b9311SLuis Carlos Cobo * @next_hop: the next hop to force 428eb2b9311SLuis Carlos Cobo * 429eb2b9311SLuis Carlos Cobo * Locking: this function must be called holding mpath->state_lock 430eb2b9311SLuis Carlos Cobo */ 431eb2b9311SLuis Carlos Cobo void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop) 432eb2b9311SLuis Carlos Cobo { 433eb2b9311SLuis Carlos Cobo spin_lock_bh(&mpath->state_lock); 434eb2b9311SLuis Carlos Cobo mesh_path_assign_nexthop(mpath, next_hop); 435eb2b9311SLuis Carlos Cobo mpath->dsn = 0xffff; 436eb2b9311SLuis Carlos Cobo mpath->metric = 0; 437eb2b9311SLuis Carlos Cobo mpath->hop_count = 0; 438eb2b9311SLuis Carlos Cobo mpath->exp_time = 0; 439eb2b9311SLuis Carlos Cobo mpath->flags |= MESH_PATH_FIXED; 440eb2b9311SLuis Carlos Cobo mesh_path_activate(mpath); 441eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 442eb2b9311SLuis Carlos Cobo mesh_path_tx_pending(mpath); 443eb2b9311SLuis Carlos Cobo } 444eb2b9311SLuis Carlos Cobo 445eb2b9311SLuis Carlos Cobo static void mesh_path_node_free(struct hlist_node *p, bool free_leafs) 446eb2b9311SLuis Carlos Cobo { 447eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 448eb2b9311SLuis Carlos Cobo struct mpath_node *node = hlist_entry(p, struct mpath_node, list); 449eb2b9311SLuis Carlos Cobo mpath = node->mpath; 450eb2b9311SLuis Carlos Cobo hlist_del_rcu(p); 451eb2b9311SLuis Carlos Cobo if (free_leafs) 452eb2b9311SLuis Carlos Cobo kfree(mpath); 453eb2b9311SLuis Carlos Cobo kfree(node); 454eb2b9311SLuis Carlos Cobo } 455eb2b9311SLuis Carlos Cobo 4564caf86c6SPavel Emelyanov static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl) 457eb2b9311SLuis Carlos Cobo { 458eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 459eb2b9311SLuis Carlos Cobo struct mpath_node *node, *new_node; 460eb2b9311SLuis Carlos Cobo u32 hash_idx; 461eb2b9311SLuis Carlos Cobo 4628566dc3fSPavel Emelyanov new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC); 46300242c40SPavel Emelyanov if (new_node == NULL) 46400242c40SPavel Emelyanov return -ENOMEM; 46500242c40SPavel Emelyanov 466eb2b9311SLuis Carlos Cobo node = hlist_entry(p, struct mpath_node, list); 467eb2b9311SLuis Carlos Cobo mpath = node->mpath; 468eb2b9311SLuis Carlos Cobo new_node->mpath = mpath; 469f698d856SJasper Bryant-Greene hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl); 470eb2b9311SLuis Carlos Cobo hlist_add_head(&new_node->list, 471eb2b9311SLuis Carlos Cobo &newtbl->hash_buckets[hash_idx]); 4724caf86c6SPavel Emelyanov return 0; 473eb2b9311SLuis Carlos Cobo } 474eb2b9311SLuis Carlos Cobo 475eb2b9311SLuis Carlos Cobo int mesh_pathtbl_init(void) 476eb2b9311SLuis Carlos Cobo { 477eb2b9311SLuis Carlos Cobo mesh_paths = mesh_table_alloc(INIT_PATHS_SIZE_ORDER); 478eb2b9311SLuis Carlos Cobo mesh_paths->free_node = &mesh_path_node_free; 479eb2b9311SLuis Carlos Cobo mesh_paths->copy_node = &mesh_path_node_copy; 480eb2b9311SLuis Carlos Cobo mesh_paths->mean_chain_len = MEAN_CHAIN_LEN; 481eb2b9311SLuis Carlos Cobo if (!mesh_paths) 482eb2b9311SLuis Carlos Cobo return -ENOMEM; 483eb2b9311SLuis Carlos Cobo return 0; 484eb2b9311SLuis Carlos Cobo } 485eb2b9311SLuis Carlos Cobo 486f698d856SJasper Bryant-Greene void mesh_path_expire(struct ieee80211_sub_if_data *sdata) 487eb2b9311SLuis Carlos Cobo { 488eb2b9311SLuis Carlos Cobo struct mesh_path *mpath; 489eb2b9311SLuis Carlos Cobo struct mpath_node *node; 490eb2b9311SLuis Carlos Cobo struct hlist_node *p; 491eb2b9311SLuis Carlos Cobo int i; 492eb2b9311SLuis Carlos Cobo 493eb2b9311SLuis Carlos Cobo read_lock(&pathtbl_resize_lock); 494eb2b9311SLuis Carlos Cobo for_each_mesh_entry(mesh_paths, p, node, i) { 495f698d856SJasper Bryant-Greene if (node->mpath->sdata != sdata) 496eb2b9311SLuis Carlos Cobo continue; 497eb2b9311SLuis Carlos Cobo mpath = node->mpath; 498eb2b9311SLuis Carlos Cobo spin_lock_bh(&mpath->state_lock); 499eb2b9311SLuis Carlos Cobo if ((!(mpath->flags & MESH_PATH_RESOLVING)) && 500eb2b9311SLuis Carlos Cobo (!(mpath->flags & MESH_PATH_FIXED)) && 501eb2b9311SLuis Carlos Cobo time_after(jiffies, 502eb2b9311SLuis Carlos Cobo mpath->exp_time + MESH_PATH_EXPIRE)) { 503eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 504f698d856SJasper Bryant-Greene mesh_path_del(mpath->dst, mpath->sdata); 505eb2b9311SLuis Carlos Cobo } else 506eb2b9311SLuis Carlos Cobo spin_unlock_bh(&mpath->state_lock); 507eb2b9311SLuis Carlos Cobo } 508eb2b9311SLuis Carlos Cobo read_unlock(&pathtbl_resize_lock); 509eb2b9311SLuis Carlos Cobo } 510eb2b9311SLuis Carlos Cobo 511eb2b9311SLuis Carlos Cobo void mesh_pathtbl_unregister(void) 512eb2b9311SLuis Carlos Cobo { 513eb2b9311SLuis Carlos Cobo mesh_table_free(mesh_paths, true); 514eb2b9311SLuis Carlos Cobo } 515