[linux-2.6-block.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;
static struct mesh_table *mpp_paths; /* Store paths for MPP&MAP */

/* 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;
}

struct mesh_path *mpp_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(mpp_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.mesh.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.mesh.mpaths);
	return err;
}


int mpp_path_add(u8 *dst, u8 *mpp, 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;

	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);
	memcpy(new_mpath->mpp, mpp, 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->exp_time = jiffies;
	spin_lock_init(&new_mpath->state_lock);

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

	spin_lock(&mpp_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(&mpp_paths->entries) >=
		mpp_paths->mean_chain_len * (mpp_paths->hash_mask + 1))
		grow = 1;

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

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

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

err_exists:
	spin_unlock(&mpp_paths->hashwlock[hash_idx]);
	read_unlock(&pathtbl_resize_lock);
	kfree(new_node);
err_node_alloc:
	kfree(new_mpath);
err_path_alloc:
	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.mesh.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.mesh.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);
	if (!mesh_paths)
		return -ENOMEM;
	mesh_paths->free_node = &mesh_path_node_free;
	mesh_paths->copy_node = &mesh_path_node_copy;
	mesh_paths->mean_chain_len = MEAN_CHAIN_LEN;

	mpp_paths = mesh_table_alloc(INIT_PATHS_SIZE_ORDER);
	if (!mpp_paths) {
		mesh_table_free(mesh_paths, true);
		return -ENOMEM;
	}
	mpp_paths->free_node = &mesh_path_node_free;
	mpp_paths->copy_node = &mesh_path_node_copy;
	mpp_paths->mean_chain_len = MEAN_CHAIN_LEN;

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