[GitHub/mt8127/android_kernel_alcatel_ttab.git] / net / mac80211 / mesh_pathtbl.c

/*
 * Copyright (c) 2008 open80211s Ltd.
 * Author:     Luis Carlos Cobo <luisca@cozybit.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 */

#include <linux/etherdevice.h>
#include <linux/list.h>
#include <linux/random.h>
#include <linux/spinlock.h>
#include <linux/string.h>
#include <net/mac80211.h>
#include "ieee80211_i.h"
#include "mesh.h"

/* There will be initially 2^INIT_PATHS_SIZE_ORDER buckets */
#define INIT_PATHS_SIZE_ORDER	2

/* Keep the mean chain length below this constant */
#define MEAN_CHAIN_LEN		2

#define MPATH_EXPIRED(mpath) ((mpath->flags & MESH_PATH_ACTIVE) && \
				time_after(jiffies, mpath->exp_time) && \
				!(mpath->flags & MESH_PATH_FIXED))

struct mpath_node {
	struct hlist_node list;
	struct rcu_head rcu;
	/* This indirection allows two different tables to point to the same
	 * mesh_path structure, useful when resizing
	 */
	struct mesh_path *mpath;
};

static struct mesh_table *mesh_paths;

/* This lock will have the grow table function as writer and add / delete nodes
 * as readers. When reading the table (i.e. doing lookups) we are well protected
 * by RCU
 */
static DEFINE_RWLOCK(pathtbl_resize_lock);

/**
 *
 * mesh_path_assign_nexthop - update mesh path next hop
 *
 * @mpath: mesh path to update
 * @sta: next hop to assign
 *
 * Locking: mpath->state_lock must be held when calling this function
 */
void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta)
{
	rcu_assign_pointer(mpath->next_hop, sta);
}


/**
 * mesh_path_lookup - look up a path in the mesh path table
 * @dst: hardware address (ETH_ALEN length) of destination
 * @sdata: local subif
 *
 * Returns: pointer to the mesh path structure, or NULL if not found
 *
 * Locking: must be called within a read rcu section.
 */
struct mesh_path *mesh_path_lookup(u8 *dst, struct ieee80211_sub_if_data *sdata)
{
	struct mesh_path *mpath;
	struct hlist_node *n;
	struct hlist_head *bucket;
	struct mesh_table *tbl;
	struct mpath_node *node;

	tbl = rcu_dereference(mesh_paths);

	bucket = &tbl->hash_buckets[mesh_table_hash(dst, sdata, tbl)];
	hlist_for_each_entry_rcu(node, n, bucket, list) {
		mpath = node->mpath;
		if (mpath->sdata == sdata &&
				memcmp(dst, mpath->dst, ETH_ALEN) == 0) {
			if (MPATH_EXPIRED(mpath)) {
				spin_lock_bh(&mpath->state_lock);
				if (MPATH_EXPIRED(mpath))
					mpath->flags &= ~MESH_PATH_ACTIVE;
				spin_unlock_bh(&mpath->state_lock);
			}
			return mpath;
		}
	}
	return NULL;
}

/**
 * mesh_path_lookup_by_idx - look up a path in the mesh path table by its index
 * @idx: index
 * @sdata: local subif, or NULL for all entries
 *
 * Returns: pointer to the mesh path structure, or NULL if not found.
 *
 * Locking: must be called within a read rcu section.
 */
struct mesh_path *mesh_path_lookup_by_idx(int idx, struct ieee80211_sub_if_data *sdata)
{
	struct mpath_node *node;
	struct hlist_node *p;
	int i;
	int j = 0;

	for_each_mesh_entry(mesh_paths, p, node, i) {
		if (sdata && node->mpath->sdata != sdata)
			continue;
		if (j++ == idx) {
			if (MPATH_EXPIRED(node->mpath)) {
				spin_lock_bh(&node->mpath->state_lock);
				if (MPATH_EXPIRED(node->mpath))
					node->mpath->flags &= ~MESH_PATH_ACTIVE;
				spin_unlock_bh(&node->mpath->state_lock);
			}
			return node->mpath;
		}
	}

	return NULL;
}

/**
 * mesh_path_add - allocate and add a new path to the mesh path table
 * @addr: destination address of the path (ETH_ALEN length)
 * @sdata: local subif
 *
 * Returns: 0 on sucess
 *
 * State: the initial state of the new path is set to 0
 */
int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata)
{
	struct mesh_path *mpath, *new_mpath;
	struct mpath_node *node, *new_node;
	struct hlist_head *bucket;
	struct hlist_node *n;
	int grow = 0;
	int err = 0;
	u32 hash_idx;

	if (memcmp(dst, sdata->dev->dev_addr, ETH_ALEN) == 0)
		/* never add ourselves as neighbours */
		return -ENOTSUPP;

	if (is_multicast_ether_addr(dst))
		return -ENOTSUPP;

	if (atomic_add_unless(&sdata->u.sta.mpaths, 1, MESH_MAX_MPATHS) == 0)
		return -ENOSPC;

	err = -ENOMEM;
	new_mpath = kzalloc(sizeof(struct mesh_path), GFP_KERNEL);
	if (!new_mpath)
		goto err_path_alloc;

	new_node = kmalloc(sizeof(struct mpath_node), GFP_KERNEL);
	if (!new_node)
		goto err_node_alloc;

	read_lock(&pathtbl_resize_lock);
	memcpy(new_mpath->dst, dst, ETH_ALEN);
	new_mpath->sdata = sdata;
	new_mpath->flags = 0;
	skb_queue_head_init(&new_mpath->frame_queue);
	new_node->mpath = new_mpath;
	new_mpath->timer.data = (unsigned long) new_mpath;
	new_mpath->timer.function = mesh_path_timer;
	new_mpath->exp_time = jiffies;
	spin_lock_init(&new_mpath->state_lock);
	init_timer(&new_mpath->timer);

	hash_idx = mesh_table_hash(dst, sdata, mesh_paths);
	bucket = &mesh_paths->hash_buckets[hash_idx];

	spin_lock(&mesh_paths->hashwlock[hash_idx]);

	err = -EEXIST;
	hlist_for_each_entry(node, n, bucket, list) {
		mpath = node->mpath;
		if (mpath->sdata == sdata && memcmp(dst, mpath->dst, ETH_ALEN) == 0)
			goto err_exists;
	}

	hlist_add_head_rcu(&new_node->list, bucket);
	if (atomic_inc_return(&mesh_paths->entries) >=
		mesh_paths->mean_chain_len * (mesh_paths->hash_mask + 1))
		grow = 1;

	spin_unlock(&mesh_paths->hashwlock[hash_idx]);
	read_unlock(&pathtbl_resize_lock);
	if (grow) {
		struct mesh_table *oldtbl, *newtbl;

		write_lock(&pathtbl_resize_lock);
		oldtbl = mesh_paths;
		newtbl = mesh_table_grow(mesh_paths);
		if (!newtbl) {
			write_unlock(&pathtbl_resize_lock);
			return 0;
		}
		rcu_assign_pointer(mesh_paths, newtbl);
		write_unlock(&pathtbl_resize_lock);

		synchronize_rcu();
		mesh_table_free(oldtbl, false);
	}
	return 0;

err_exists:
	spin_unlock(&mesh_paths->hashwlock[hash_idx]);
	read_unlock(&pathtbl_resize_lock);
	kfree(new_node);
err_node_alloc:
	kfree(new_mpath);
err_path_alloc:
	atomic_dec(&sdata->u.sta.mpaths);
	return err;
}


/**
 * mesh_plink_broken - deactivates paths and sends perr when a link breaks
 *
 * @sta: broken peer link
 *
 * This function must be called from the rate control algorithm if enough
 * delivery errors suggest that a peer link is no longer usable.
 */
void mesh_plink_broken(struct sta_info *sta)
{
	struct mesh_path *mpath;
	struct mpath_node *node;
	struct hlist_node *p;
	struct ieee80211_sub_if_data *sdata = sta->sdata;
	int i;

	rcu_read_lock();
	for_each_mesh_entry(mesh_paths, p, node, i) {
		mpath = node->mpath;
		spin_lock_bh(&mpath->state_lock);
		if (mpath->next_hop == sta &&
		    mpath->flags & MESH_PATH_ACTIVE &&
		    !(mpath->flags & MESH_PATH_FIXED)) {
			mpath->flags &= ~MESH_PATH_ACTIVE;
			++mpath->dsn;
			spin_unlock_bh(&mpath->state_lock);
			mesh_path_error_tx(mpath->dst,
					cpu_to_le32(mpath->dsn),
					sdata->dev->broadcast, sdata);
		} else
		spin_unlock_bh(&mpath->state_lock);
	}
	rcu_read_unlock();
}

/**
 * mesh_path_flush_by_nexthop - Deletes mesh paths if their next hop matches
 *
 * @sta - mesh peer to match
 *
 * RCU notes: this function is called when a mesh plink transitions from
 * PLINK_ESTAB to any other state, since PLINK_ESTAB state is the only one that
 * allows path creation. This will happen before the sta can be freed (because
 * sta_info_destroy() calls this) so any reader in a rcu read block will be
 * protected against the plink disappearing.
 */
void mesh_path_flush_by_nexthop(struct sta_info *sta)
{
	struct mesh_path *mpath;
	struct mpath_node *node;
	struct hlist_node *p;
	int i;

	for_each_mesh_entry(mesh_paths, p, node, i) {
		mpath = node->mpath;
		if (mpath->next_hop == sta)
			mesh_path_del(mpath->dst, mpath->sdata);
	}
}

void mesh_path_flush(struct ieee80211_sub_if_data *sdata)
{
	struct mesh_path *mpath;
	struct mpath_node *node;
	struct hlist_node *p;
	int i;

	for_each_mesh_entry(mesh_paths, p, node, i) {
		mpath = node->mpath;
		if (mpath->sdata == sdata)
			mesh_path_del(mpath->dst, mpath->sdata);
	}
}

static void mesh_path_node_reclaim(struct rcu_head *rp)
{
	struct mpath_node *node = container_of(rp, struct mpath_node, rcu);
	struct ieee80211_sub_if_data *sdata = node->mpath->sdata;

	del_timer_sync(&node->mpath->timer);
	atomic_dec(&sdata->u.sta.mpaths);
	kfree(node->mpath);
	kfree(node);
}

/**
 * mesh_path_del - delete a mesh path from the table
 *
 * @addr: dst address (ETH_ALEN length)
 * @sdata: local subif
 *
 * Returns: 0 if succesful
 */
int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata)
{
	struct mesh_path *mpath;
	struct mpath_node *node;
	struct hlist_head *bucket;
	struct hlist_node *n;
	int hash_idx;
	int err = 0;

	read_lock(&pathtbl_resize_lock);
	hash_idx = mesh_table_hash(addr, sdata, mesh_paths);
	bucket = &mesh_paths->hash_buckets[hash_idx];

	spin_lock(&mesh_paths->hashwlock[hash_idx]);
	hlist_for_each_entry(node, n, bucket, list) {
		mpath = node->mpath;
		if (mpath->sdata == sdata &&
				memcmp(addr, mpath->dst, ETH_ALEN) == 0) {
			spin_lock_bh(&mpath->state_lock);
			mpath->flags |= MESH_PATH_RESOLVING;
			hlist_del_rcu(&node->list);
			call_rcu(&node->rcu, mesh_path_node_reclaim);
			atomic_dec(&mesh_paths->entries);
			spin_unlock_bh(&mpath->state_lock);
			goto enddel;
		}
	}

	err = -ENXIO;
enddel:
	spin_unlock(&mesh_paths->hashwlock[hash_idx]);
	read_unlock(&pathtbl_resize_lock);
	return err;
}

/**
 * mesh_path_tx_pending - sends pending frames in a mesh path queue
 *
 * @mpath: mesh path to activate
 *
 * Locking: the state_lock of the mpath structure must NOT be held when calling
 * this function.
 */
void mesh_path_tx_pending(struct mesh_path *mpath)
{
	struct sk_buff *skb;

	while ((skb = skb_dequeue(&mpath->frame_queue)) &&
			(mpath->flags & MESH_PATH_ACTIVE))
		dev_queue_xmit(skb);
}

/**
 * mesh_path_discard_frame - discard a frame whose path could not be resolved
 *
 * @skb: frame to discard
 * @sdata: network subif the frame was to be sent through
 *
 * If the frame was beign forwarded from another MP, a PERR frame will be sent
 * to the precursor.
 *
 * Locking: the function must me called within a rcu_read_lock region
 */
void mesh_path_discard_frame(struct sk_buff *skb,
			     struct ieee80211_sub_if_data *sdata)
{
	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
	struct mesh_path *mpath;
	u32 dsn = 0;

	if (memcmp(hdr->addr4, sdata->dev->dev_addr, ETH_ALEN) != 0) {
		u8 *ra, *da;

		da = hdr->addr3;
		ra = hdr->addr2;
		mpath = mesh_path_lookup(da, sdata);
		if (mpath)
			dsn = ++mpath->dsn;
		mesh_path_error_tx(skb->data, cpu_to_le32(dsn), ra, sdata);
	}

	kfree_skb(skb);
	sdata->u.sta.mshstats.dropped_frames_no_route++;
}

/**
 * mesh_path_flush_pending - free the pending queue of a mesh path
 *
 * @mpath: mesh path whose queue has to be freed
 *
 * Locking: the function must me called withing a rcu_read_lock region
 */
void mesh_path_flush_pending(struct mesh_path *mpath)
{
	struct sk_buff *skb;

	while ((skb = skb_dequeue(&mpath->frame_queue)) &&
			(mpath->flags & MESH_PATH_ACTIVE))
		mesh_path_discard_frame(skb, mpath->sdata);
}

/**
 * mesh_path_fix_nexthop - force a specific next hop for a mesh path
 *
 * @mpath: the mesh path to modify
 * @next_hop: the next hop to force
 *
 * Locking: this function must be called holding mpath->state_lock
 */
void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop)
{
	spin_lock_bh(&mpath->state_lock);
	mesh_path_assign_nexthop(mpath, next_hop);
	mpath->dsn = 0xffff;
	mpath->metric = 0;
	mpath->hop_count = 0;
	mpath->exp_time = 0;
	mpath->flags |= MESH_PATH_FIXED;
	mesh_path_activate(mpath);
	spin_unlock_bh(&mpath->state_lock);
	mesh_path_tx_pending(mpath);
}

static void mesh_path_node_free(struct hlist_node *p, bool free_leafs)
{
	struct mesh_path *mpath;
	struct mpath_node *node = hlist_entry(p, struct mpath_node, list);
	mpath = node->mpath;
	hlist_del_rcu(p);
	if (free_leafs)
		kfree(mpath);
	kfree(node);
}

static int mesh_path_node_copy(struct hlist_node *p, struct mesh_table *newtbl)
{
	struct mesh_path *mpath;
	struct mpath_node *node, *new_node;
	u32 hash_idx;

	new_node = kmalloc(sizeof(struct mpath_node), GFP_ATOMIC);
	if (new_node == NULL)
		return -ENOMEM;

	node = hlist_entry(p, struct mpath_node, list);
	mpath = node->mpath;
	new_node->mpath = mpath;
	hash_idx = mesh_table_hash(mpath->dst, mpath->sdata, newtbl);
	hlist_add_head(&new_node->list,
			&newtbl->hash_buckets[hash_idx]);
	return 0;
}

int mesh_pathtbl_init(void)
{
	mesh_paths = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
	mesh_paths->free_node = &mesh_path_node_free;
	mesh_paths->copy_node = &mesh_path_node_copy;
	mesh_paths->mean_chain_len = MEAN_CHAIN_LEN;
	if (!mesh_paths)
		return -ENOMEM;
	return 0;
}

void mesh_path_expire(struct ieee80211_sub_if_data *sdata)
{
	struct mesh_path *mpath;
	struct mpath_node *node;
	struct hlist_node *p;
	int i;

	read_lock(&pathtbl_resize_lock);
	for_each_mesh_entry(mesh_paths, p, node, i) {
		if (node->mpath->sdata != sdata)
			continue;
		mpath = node->mpath;
		spin_lock_bh(&mpath->state_lock);
		if ((!(mpath->flags & MESH_PATH_RESOLVING)) &&
		    (!(mpath->flags & MESH_PATH_FIXED)) &&
			time_after(jiffies,
			 mpath->exp_time + MESH_PATH_EXPIRE)) {
			spin_unlock_bh(&mpath->state_lock);
			mesh_path_del(mpath->dst, mpath->sdata);
		} else
			spin_unlock_bh(&mpath->state_lock);
	}
	read_unlock(&pathtbl_resize_lock);
}

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