mesh.h 10.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
/*
 * Copyright (c) 2008 open80211s Ltd.
 * Authors:    Luis Carlos Cobo <luisca@cozybit.com>
 *             Javier Cardona <javier@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.
 */

#ifndef IEEE80211S_H
#define IEEE80211S_H

Johannes Berg's avatar
Johannes Berg committed
14
#include <linux/types.h>
15
#include <linux/jhash.h>
16
#include <asm/unaligned.h>
Johannes Berg's avatar
Johannes Berg committed
17
#include "ieee80211_i.h"
18 19 20 21 22 23 24 25 26


/* Data structures */

/**
 * enum mesh_path_flags - mac80211 mesh path flags
 *
 *
 *
27 28
 * @MESH_PATH_ACTIVE: the mesh path can be used for forwarding
 * @MESH_PATH_RESOLVING: the discovery process is running for this mesh path
29 30 31 32 33 34
 * @MESH_PATH_DSN_VALID: the mesh path contains a valid destination sequence
 * 	number
 * @MESH_PATH_FIXED: the mesh path has been manually set and should not be
 * 	modified
 * @MESH_PATH_RESOLVED: the mesh path can has been resolved
 *
35
 * MESH_PATH_RESOLVED is used by the mesh path timer to
36 37 38 39 40 41 42 43 44 45 46 47 48 49
 * decide when to stop or cancel the mesh path discovery.
 */
enum mesh_path_flags {
	MESH_PATH_ACTIVE =	BIT(0),
	MESH_PATH_RESOLVING =	BIT(1),
	MESH_PATH_DSN_VALID =	BIT(2),
	MESH_PATH_FIXED	=	BIT(3),
	MESH_PATH_RESOLVED =	BIT(4),
};

/**
 * struct mesh_path - mac80211 mesh path structure
 *
 * @dst: mesh path destination mac address
50
 * @sdata: mesh subif
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
 * @next_hop: mesh neighbor to which frames for this destination will be
 * 	forwarded
 * @timer: mesh path discovery timer
 * @frame_queue: pending queue for frames sent to this destination while the
 * 	path is unresolved
 * @dsn: destination sequence number of the destination
 * @metric: current metric to this destination
 * @hop_count: hops to destination
 * @exp_time: in jiffies, when the path will expire or when it expired
 * @discovery_timeout: timeout (lapse in jiffies) used for the last discovery
 * 	retry
 * @discovery_retries: number of discovery retries
 * @flags: mesh path flags, as specified on &enum mesh_path_flags
 * @state_lock: mesh pat state lock
 *
 *
67
 * The combination of dst and sdata is unique in the mesh path table. Since the
68 69 70
 * next_hop STA is only protected by RCU as well, deleting the STA must also
 * remove/substitute the mesh_path structure and wait until that is no longer
 * reachable before destroying the STA completely.
71 72 73
 */
struct mesh_path {
	u8 dst[ETH_ALEN];
74
	u8 mpp[ETH_ALEN];	/* used for MPP or MAP */
75
	struct ieee80211_sub_if_data *sdata;
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
	struct sta_info *next_hop;
	struct timer_list timer;
	struct sk_buff_head frame_queue;
	struct rcu_head rcu;
	u32 dsn;
	u32 metric;
	u8 hop_count;
	unsigned long exp_time;
	u32 discovery_timeout;
	u8 discovery_retries;
	enum mesh_path_flags flags;
	spinlock_t state_lock;
};

/**
 * struct mesh_table
 *
 * @hash_buckets: array of hash buckets of the table
 * @hashwlock: array of locks to protect write operations, one per bucket
 * @hash_mask: 2^size_order - 1, used to compute hash idx
 * @hash_rnd: random value used for hash computations
 * @entries: number of entries in the table
 * @free_node: function to free nodes of the table
 * @copy_node: fuction to copy nodes of the table
 * @size_order: determines size of the table, there will be 2^size_order hash
 *	buckets
 * @mean_chain_len: maximum average length for the hash buckets' list, if it is
 *	reached, the table will grow
 */
struct mesh_table {
	/* Number of buckets will be 2^N */
	struct hlist_head *hash_buckets;
	spinlock_t *hashwlock;		/* One per bucket, for add/del */
	unsigned int hash_mask;		/* (2^size_order) - 1 */
	__u32 hash_rnd;			/* Used for hash generation */
	atomic_t entries;		/* Up to MAX_MESH_NEIGHBOURS */
	void (*free_node) (struct hlist_node *p, bool free_leafs);
113
	int (*copy_node) (struct hlist_node *p, struct mesh_table *newtbl);
114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
	int size_order;
	int mean_chain_len;
};

/* Recent multicast cache */
/* RMC_BUCKETS must be a power of 2, maximum 256 */
#define RMC_BUCKETS		256
#define RMC_QUEUE_MAX_LEN	4
#define RMC_TIMEOUT		(3 * HZ)

/**
 * struct rmc_entry - entry in the Recent Multicast Cache
 *
 * @seqnum: mesh sequence number of the frame
 * @exp_time: expiration time of the entry, in jiffies
 * @sa: source address of the frame
 *
 * The Recent Multicast Cache keeps track of the latest multicast frames that
 * have been received by a mesh interface and discards received multicast frames
 * that are found in the cache.
 */
struct rmc_entry {
	struct list_head list;
	u32 seqnum;
	unsigned long exp_time;
	u8 sa[ETH_ALEN];
};

struct mesh_rmc {
	struct rmc_entry bucket[RMC_BUCKETS];
144
	u32 idx_mask;
145 146 147 148 149 150 151 152 153 154 155 156
};


/*
 * MESH_CFG_COMP_LEN Includes:
 * 	- Active path selection protocol ID.
 * 	- Active path selection metric ID.
 * 	- Congestion control mode identifier.
 * 	- Channel precedence.
 * Does not include mesh capabilities, which may vary across nodes in the same
 * mesh
 */
157
#define MESH_CFG_CMP_LEN 	(IEEE80211_MESH_CONFIG_LEN - 2)
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198

/* Default values, timeouts in ms */
#define MESH_TTL 		5
#define MESH_MAX_RETR	 	3
#define MESH_RET_T 		100
#define MESH_CONF_T 		100
#define MESH_HOLD_T 		100

#define MESH_PATH_TIMEOUT	5000
/* Minimum interval between two consecutive PREQs originated by the same
 * interface
 */
#define MESH_PREQ_MIN_INT	10
#define MESH_DIAM_TRAVERSAL_TIME 50
/* Paths will be refreshed if they are closer than PATH_REFRESH_TIME to their
 * expiration
 */
#define MESH_PATH_REFRESH_TIME			1000
#define MESH_MIN_DISCOVERY_TIMEOUT (2 * MESH_DIAM_TRAVERSAL_TIME)

#define MESH_MAX_PREQ_RETRIES 4
#define MESH_PATH_EXPIRE (600 * HZ)

/* Default maximum number of established plinks per interface */
#define MESH_MAX_ESTAB_PLINKS	32

/* Default maximum number of plinks per interface */
#define MESH_MAX_PLINKS		256

/* Maximum number of paths per interface */
#define MESH_MAX_MPATHS		1024

/* Pending ANA approval */
#define PLINK_CATEGORY		30
#define MESH_PATH_SEL_CATEGORY	32

/* Public interfaces */
/* Various */
int ieee80211_new_mesh_header(struct ieee80211s_hdr *meshhdr,
		struct ieee80211_sub_if_data *sdata);
int mesh_rmc_check(u8 *addr, struct ieee80211s_hdr *mesh_hdr,
199 200 201
		struct ieee80211_sub_if_data *sdata);
bool mesh_matches_local(struct ieee802_11_elems *ie,
		struct ieee80211_sub_if_data *sdata);
202
void mesh_ids_set_default(struct ieee80211_if_mesh *mesh);
203 204 205 206
void mesh_mgmt_ies_add(struct sk_buff *skb,
		struct ieee80211_sub_if_data *sdata);
void mesh_rmc_free(struct ieee80211_sub_if_data *sdata);
int mesh_rmc_init(struct ieee80211_sub_if_data *sdata);
207 208
void ieee80211s_init(void);
void ieee80211s_stop(void);
Johannes Berg's avatar
Johannes Berg committed
209
void ieee80211_mesh_init_sdata(struct ieee80211_sub_if_data *sdata);
210
ieee80211_rx_result
211
ieee80211_mesh_rx_mgmt(struct ieee80211_sub_if_data *sdata, struct sk_buff *skb);
212 213
void ieee80211_start_mesh(struct ieee80211_sub_if_data *sdata);
void ieee80211_stop_mesh(struct ieee80211_sub_if_data *sdata);
Johannes Berg's avatar
Johannes Berg committed
214

215
/* Mesh paths */
216 217 218 219 220
int mesh_nexthop_lookup(struct sk_buff *skb,
		struct ieee80211_sub_if_data *sdata);
void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata);
struct mesh_path *mesh_path_lookup(u8 *dst,
		struct ieee80211_sub_if_data *sdata);
221 222 223
struct mesh_path *mpp_path_lookup(u8 *dst,
				  struct ieee80211_sub_if_data *sdata);
int mpp_path_add(u8 *dst, u8 *mpp, struct ieee80211_sub_if_data *sdata);
224 225
struct mesh_path *mesh_path_lookup_by_idx(int idx,
		struct ieee80211_sub_if_data *sdata);
226
void mesh_path_fix_nexthop(struct mesh_path *mpath, struct sta_info *next_hop);
227 228 229 230 231
void mesh_path_expire(struct ieee80211_sub_if_data *sdata);
void mesh_path_flush(struct ieee80211_sub_if_data *sdata);
void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
		struct ieee80211_mgmt *mgmt, size_t len);
int mesh_path_add(u8 *dst, struct ieee80211_sub_if_data *sdata);
232
/* Mesh plinks */
233
void mesh_neighbour_update(u8 *hw_addr, u32 rates,
234 235
		struct ieee80211_sub_if_data *sdata, bool add);
bool mesh_peer_accepts_plinks(struct ieee802_11_elems *ie);
236
void mesh_accept_plinks_update(struct ieee80211_sub_if_data *sdata);
237 238 239 240
void mesh_plink_broken(struct sta_info *sta);
void mesh_plink_deactivate(struct sta_info *sta);
int mesh_plink_open(struct sta_info *sta);
void mesh_plink_block(struct sta_info *sta);
241 242 243
void mesh_rx_plink_frame(struct ieee80211_sub_if_data *sdata,
			 struct ieee80211_mgmt *mgmt, size_t len,
			 struct ieee80211_rx_status *rx_status);
244 245 246 247 248 249

/* Private interfaces */
/* Mesh tables */
struct mesh_table *mesh_table_alloc(int size_order);
void mesh_table_free(struct mesh_table *tbl, bool free_leafs);
struct mesh_table *mesh_table_grow(struct mesh_table *tbl);
250 251
u32 mesh_table_hash(u8 *addr, struct ieee80211_sub_if_data *sdata,
		struct mesh_table *tbl);
252 253
/* Mesh paths */
int mesh_path_error_tx(u8 *dest, __le32 dest_dsn, u8 *ra,
254
		struct ieee80211_sub_if_data *sdata);
255 256 257 258 259
void mesh_path_assign_nexthop(struct mesh_path *mpath, struct sta_info *sta);
void mesh_path_flush_pending(struct mesh_path *mpath);
void mesh_path_tx_pending(struct mesh_path *mpath);
int mesh_pathtbl_init(void);
void mesh_pathtbl_unregister(void);
260
int mesh_path_del(u8 *addr, struct ieee80211_sub_if_data *sdata);
261 262
void mesh_path_timer(unsigned long data);
void mesh_path_flush_by_nexthop(struct sta_info *sta);
263 264
void mesh_path_discard_frame(struct sk_buff *skb,
		struct ieee80211_sub_if_data *sdata);
265 266
void mesh_path_quiesce(struct ieee80211_sub_if_data *sdata);
void mesh_path_restart(struct ieee80211_sub_if_data *sdata);
267

Johannes Berg's avatar
Johannes Berg committed
268 269 270
#ifdef CONFIG_MAC80211_MESH
extern int mesh_allocated;

271 272
static inline int mesh_plink_free_count(struct ieee80211_sub_if_data *sdata)
{
273 274
	return sdata->u.mesh.mshcfg.dot11MeshMaxPeerLinks -
	       atomic_read(&sdata->u.mesh.mshstats.estab_plinks);
275 276 277 278
}

static inline bool mesh_plink_availables(struct ieee80211_sub_if_data *sdata)
{
279
	return (min_t(long, mesh_plink_free_count(sdata),
280 281 282 283 284 285 286 287 288 289 290 291
		   MESH_MAX_PLINKS - sdata->local->num_sta)) > 0;
}

static inline void mesh_path_activate(struct mesh_path *mpath)
{
	mpath->flags |= MESH_PATH_ACTIVE | MESH_PATH_RESOLVED;
}

#define for_each_mesh_entry(x, p, node, i) \
	for (i = 0; i <= x->hash_mask; i++) \
		hlist_for_each_entry_rcu(node, p, &x->hash_buckets[i], list)

292 293
void ieee80211_mesh_notify_scan_completed(struct ieee80211_local *local);

294 295 296 297
void ieee80211_mesh_quiesce(struct ieee80211_sub_if_data *sdata);
void ieee80211_mesh_restart(struct ieee80211_sub_if_data *sdata);
void mesh_plink_quiesce(struct sta_info *sta);
void mesh_plink_restart(struct sta_info *sta);
Johannes Berg's avatar
Johannes Berg committed
298 299
#else
#define mesh_allocated	0
300 301
static inline void
ieee80211_mesh_notify_scan_completed(struct ieee80211_local *local) {}
302 303 304 305 306 307
static inline void ieee80211_mesh_quiesce(struct ieee80211_sub_if_data *sdata)
{}
static inline void ieee80211_mesh_restart(struct ieee80211_sub_if_data *sdata)
{}
static inline void mesh_plink_quiesce(struct sta_info *sta) {}
static inline void mesh_plink_restart(struct sta_info *sta) {}
Johannes Berg's avatar
Johannes Berg committed
308 309
#endif

310
#endif /* IEEE80211S_H */