mesh_hwmp.c 27.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11
/*
 * 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 "mesh.h"

12 13 14 15 16 17
#ifdef CONFIG_MAC80211_VERBOSE_MHWMP_DEBUG
#define mhwmp_dbg(fmt, args...)   printk(KERN_DEBUG "Mesh HWMP: " fmt, ##args)
#else
#define mhwmp_dbg(fmt, args...)   do { (void)(0); } while (0)
#endif

18 19 20 21 22 23 24 25 26 27 28 29
#define TEST_FRAME_LEN	8192
#define MAX_METRIC	0xffffffff
#define ARITH_SHIFT	8

/* Number of frames buffered per destination for unresolved destinations */
#define MESH_FRAME_QUEUE_LEN	10
#define MAX_PREQ_QUEUE_LEN	64

/* Destination only */
#define MP_F_DO	0x1
/* Reply and forward */
#define MP_F_RF	0x2
R
Rui Paulo 已提交
30 31 32 33
/* Unknown Sequence Number */
#define MP_F_USN    0x01
/* Reason code Present */
#define MP_F_RCODE  0x02
34

35 36
static void mesh_queue_preq(struct mesh_path *, u8);

37 38 39 40
static inline u32 u32_field_get(u8 *preq_elem, int offset, bool ae)
{
	if (ae)
		offset += 6;
41
	return get_unaligned_le32(preq_elem + offset);
42 43
}

R
Rui Paulo 已提交
44 45 46 47 48 49 50
static inline u32 u16_field_get(u8 *preq_elem, int offset, bool ae)
{
	if (ae)
		offset += 6;
	return get_unaligned_le16(preq_elem + offset);
}

51
/* HWMP IE processing macros */
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
#define AE_F			(1<<6)
#define AE_F_SET(x)		(*x & AE_F)
#define PREQ_IE_FLAGS(x)	(*(x))
#define PREQ_IE_HOPCOUNT(x)	(*(x + 1))
#define PREQ_IE_TTL(x)		(*(x + 2))
#define PREQ_IE_PREQ_ID(x)	u32_field_get(x, 3, 0)
#define PREQ_IE_ORIG_ADDR(x)	(x + 7)
#define PREQ_IE_ORIG_DSN(x)	u32_field_get(x, 13, 0);
#define PREQ_IE_LIFETIME(x)	u32_field_get(x, 17, AE_F_SET(x));
#define PREQ_IE_METRIC(x) 	u32_field_get(x, 21, AE_F_SET(x));
#define PREQ_IE_DST_F(x)	(*(AE_F_SET(x) ? x + 32 : x + 26))
#define PREQ_IE_DST_ADDR(x) 	(AE_F_SET(x) ? x + 33 : x + 27)
#define PREQ_IE_DST_DSN(x) 	u32_field_get(x, 33, AE_F_SET(x));


#define PREP_IE_FLAGS(x)	PREQ_IE_FLAGS(x)
#define PREP_IE_HOPCOUNT(x)	PREQ_IE_HOPCOUNT(x)
#define PREP_IE_TTL(x)		PREQ_IE_TTL(x)
#define PREP_IE_ORIG_ADDR(x)	(x + 3)
#define PREP_IE_ORIG_DSN(x)	u32_field_get(x, 9, 0);
#define PREP_IE_LIFETIME(x)	u32_field_get(x, 13, AE_F_SET(x));
#define PREP_IE_METRIC(x)	u32_field_get(x, 17, AE_F_SET(x));
#define PREP_IE_DST_ADDR(x)	(AE_F_SET(x) ? x + 27 : x + 21)
#define PREP_IE_DST_DSN(x)	u32_field_get(x, 27, AE_F_SET(x));

R
Rui Paulo 已提交
77 78 79 80 81
#define PERR_IE_TTL(x)		(*(x))
#define PERR_IE_DST_FLAGS(x)	(*(x + 2))
#define PERR_IE_DST_ADDR(x)	(x + 3)
#define PERR_IE_DST_DSN(x)	u32_field_get(x, 9, 0);
#define PERR_IE_DST_RCODE(x)	u16_field_get(x, 13, 0);
82 83 84 85 86 87

#define MSEC_TO_TU(x) (x*1000/1024)
#define DSN_GT(x, y) ((long) (y) - (long) (x) < 0)
#define DSN_LT(x, y) ((long) (x) - (long) (y) < 0)

#define net_traversal_jiffies(s) \
88
	msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPnetDiameterTraversalTime)
89
#define default_lifetime(s) \
90
	MSEC_TO_TU(s->u.mesh.mshcfg.dot11MeshHWMPactivePathTimeout)
91
#define min_preq_int_jiff(s) \
92 93
	(msecs_to_jiffies(s->u.mesh.mshcfg.dot11MeshHWMPpreqMinInterval))
#define max_preq_retries(s) (s->u.mesh.mshcfg.dot11MeshHWMPmaxPREQretries)
94
#define disc_timeout_jiff(s) \
95
	msecs_to_jiffies(sdata->u.mesh.mshcfg.min_discovery_timeout)
96 97 98 99

enum mpath_frame_type {
	MPATH_PREQ = 0,
	MPATH_PREP,
100 101
	MPATH_PERR,
	MPATH_RANN
102 103 104 105 106
};

static int mesh_path_sel_frame_tx(enum mpath_frame_type action, u8 flags,
		u8 *orig_addr, __le32 orig_dsn, u8 dst_flags, u8 *dst,
		__le32 dst_dsn, u8 *da, u8 hop_count, u8 ttl, __le32 lifetime,
107
		__le32 metric, __le32 preq_id, struct ieee80211_sub_if_data *sdata)
108
{
109
	struct ieee80211_local *local = sdata->local;
110 111 112 113 114 115 116 117 118 119 120 121 122 123
	struct sk_buff *skb = dev_alloc_skb(local->hw.extra_tx_headroom + 400);
	struct ieee80211_mgmt *mgmt;
	u8 *pos;
	int ie_len;

	if (!skb)
		return -1;
	skb_reserve(skb, local->hw.extra_tx_headroom);
	/* 25 is the size of the common mgmt part (24) plus the size of the
	 * common action part (1)
	 */
	mgmt = (struct ieee80211_mgmt *)
		skb_put(skb, 25 + sizeof(mgmt->u.action.u.mesh_action));
	memset(mgmt, 0, 25 + sizeof(mgmt->u.action.u.mesh_action));
124 125
	mgmt->frame_control = cpu_to_le16(IEEE80211_FTYPE_MGMT |
					  IEEE80211_STYPE_ACTION);
126 127

	memcpy(mgmt->da, da, ETH_ALEN);
128
	memcpy(mgmt->sa, sdata->dev->dev_addr, ETH_ALEN);
129 130
	/* BSSID == SA */
	memcpy(mgmt->bssid, sdata->dev->dev_addr, ETH_ALEN);
131
	mgmt->u.action.category = MESH_PATH_SEL_CATEGORY;
132
	mgmt->u.action.u.mesh_action.action_code = MESH_PATH_SEL_ACTION;
133 134 135

	switch (action) {
	case MPATH_PREQ:
R
Rui Paulo 已提交
136
		mhwmp_dbg("sending PREQ to %pM\n", dst);
137 138 139 140 141
		ie_len = 37;
		pos = skb_put(skb, 2 + ie_len);
		*pos++ = WLAN_EID_PREQ;
		break;
	case MPATH_PREP:
R
Rui Paulo 已提交
142
		mhwmp_dbg("sending PREP to %pM\n", dst);
143 144 145 146
		ie_len = 31;
		pos = skb_put(skb, 2 + ie_len);
		*pos++ = WLAN_EID_PREP;
		break;
147 148 149 150 151 152
	case MPATH_RANN:
		mhwmp_dbg("sending RANN from %pM\n", orig_addr);
		ie_len = sizeof(struct ieee80211_rann_ie);
		pos = skb_put(skb, 2 + ie_len);
		*pos++ = WLAN_EID_RANN;
		break;
153
	default:
154
		kfree_skb(skb);
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
		return -ENOTSUPP;
		break;
	}
	*pos++ = ie_len;
	*pos++ = flags;
	*pos++ = hop_count;
	*pos++ = ttl;
	if (action == MPATH_PREQ) {
		memcpy(pos, &preq_id, 4);
		pos += 4;
	}
	memcpy(pos, orig_addr, ETH_ALEN);
	pos += ETH_ALEN;
	memcpy(pos, &orig_dsn, 4);
	pos += 4;
170 171 172 173
	if (action != MPATH_RANN) {
		memcpy(pos, &lifetime, 4);
		pos += 4;
	}
174 175 176 177 178 179 180
	memcpy(pos, &metric, 4);
	pos += 4;
	if (action == MPATH_PREQ) {
		/* destination count */
		*pos++ = 1;
		*pos++ = dst_flags;
	}
181 182 183 184 185
	if (action != MPATH_RANN) {
		memcpy(pos, dst, ETH_ALEN);
		pos += ETH_ALEN;
		memcpy(pos, &dst_dsn, 4);
	}
186

187
	ieee80211_tx_skb(sdata, skb, 1);
188 189 190 191 192 193 194 195 196 197
	return 0;
}

/**
 * mesh_send_path error - Sends a PERR mesh management frame
 *
 * @dst: broken destination
 * @dst_dsn: dsn of the broken destination
 * @ra: node this frame is addressed to
 */
R
Rui Paulo 已提交
198 199
int mesh_path_error_tx(u8 ttl, u8 *dst, __le32 dst_dsn, __le16 dst_rcode,
		u8 *ra, struct ieee80211_sub_if_data *sdata)
200
{
201
	struct ieee80211_local *local = sdata->local;
202 203 204 205 206 207 208 209 210 211 212 213 214 215
	struct sk_buff *skb = dev_alloc_skb(local->hw.extra_tx_headroom + 400);
	struct ieee80211_mgmt *mgmt;
	u8 *pos;
	int ie_len;

	if (!skb)
		return -1;
	skb_reserve(skb, local->hw.extra_tx_headroom);
	/* 25 is the size of the common mgmt part (24) plus the size of the
	 * common action part (1)
	 */
	mgmt = (struct ieee80211_mgmt *)
		skb_put(skb, 25 + sizeof(mgmt->u.action.u.mesh_action));
	memset(mgmt, 0, 25 + sizeof(mgmt->u.action.u.mesh_action));
216 217
	mgmt->frame_control = cpu_to_le16(IEEE80211_FTYPE_MGMT |
					  IEEE80211_STYPE_ACTION);
218 219

	memcpy(mgmt->da, ra, ETH_ALEN);
220
	memcpy(mgmt->sa, sdata->dev->dev_addr, ETH_ALEN);
221 222
	/* BSSID is left zeroed, wildcard value */
	mgmt->u.action.category = MESH_PATH_SEL_CATEGORY;
223
	mgmt->u.action.u.mesh_action.action_code = MESH_PATH_SEL_ACTION;
R
Rui Paulo 已提交
224
	ie_len = 15;
225 226 227
	pos = skb_put(skb, 2 + ie_len);
	*pos++ = WLAN_EID_PERR;
	*pos++ = ie_len;
R
Rui Paulo 已提交
228 229
	/* ttl */
	*pos++ = MESH_TTL;
230 231
	/* number of destinations */
	*pos++ = 1;
R
Rui Paulo 已提交
232 233 234 235 236 237 238 239 240 241
	/*
	 * flags bit, bit 1 is unset if we know the sequence number and
	 * bit 2 is set if we have a reason code
	 */
	*pos = 0;
	if (!dst_dsn)
		*pos |= MP_F_USN;
	if (dst_rcode)
		*pos |= MP_F_RCODE;
	pos++;
242 243 244
	memcpy(pos, dst, ETH_ALEN);
	pos += ETH_ALEN;
	memcpy(pos, &dst_dsn, 4);
R
Rui Paulo 已提交
245 246
	pos += 4;
	memcpy(pos, &dst_rcode, 2);
247

248
	ieee80211_tx_skb(sdata, skb, 1);
249 250 251
	return 0;
}

252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269
void ieee80211s_update_metric(struct ieee80211_local *local,
		struct sta_info *stainfo, struct sk_buff *skb)
{
	struct ieee80211_tx_info *txinfo = IEEE80211_SKB_CB(skb);
	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
	int failed;

	if (!ieee80211_is_data(hdr->frame_control))
		return;

	failed = !(txinfo->flags & IEEE80211_TX_STAT_ACK);

	/* moving average, scaled to 100 */
	stainfo->fail_avg = ((80 * stainfo->fail_avg + 5) / 100 + 20 * failed);
	if (stainfo->fail_avg > 95)
		mesh_plink_broken(stainfo);
}

270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285
static u32 airtime_link_metric_get(struct ieee80211_local *local,
				   struct sta_info *sta)
{
	struct ieee80211_supported_band *sband;
	/* This should be adjusted for each device */
	int device_constant = 1 << ARITH_SHIFT;
	int test_frame_len = TEST_FRAME_LEN << ARITH_SHIFT;
	int s_unit = 1 << ARITH_SHIFT;
	int rate, err;
	u32 tx_time, estimated_retx;
	u64 result;

	sband = local->hw.wiphy->bands[local->hw.conf.channel->band];

	if (sta->fail_avg >= 100)
		return MAX_METRIC;
286 287 288 289

	if (sta->last_tx_rate.flags & IEEE80211_TX_RC_MCS)
		return MAX_METRIC;

290 291 292 293 294
	err = (sta->fail_avg << ARITH_SHIFT) / 100;

	/* bitrate is in units of 100 Kbps, while we need rate in units of
	 * 1Mbps. This will be corrected on tx_time computation.
	 */
295
	rate = sband->bitrates[sta->last_tx_rate.idx].bitrate;
296 297 298 299 300 301 302 303 304
	tx_time = (device_constant + 10 * test_frame_len / rate);
	estimated_retx = ((1 << (2 * ARITH_SHIFT)) / (s_unit - err));
	result = (tx_time * estimated_retx) >> (2 * ARITH_SHIFT) ;
	return (u32)result;
}

/**
 * hwmp_route_info_get - Update routing info to originator and transmitter
 *
305
 * @sdata: local mesh subif
306 307 308 309
 * @mgmt: mesh management frame
 * @hwmp_ie: hwmp information element (PREP or PREQ)
 *
 * This function updates the path routing information to the originator and the
310
 * transmitter of a HWMP PREQ or PREP frame.
311 312 313 314 315 316 317
 *
 * Returns: metric to frame originator or 0 if the frame should not be further
 * processed
 *
 * Notes: this function is the only place (besides user-provided info) where
 * path routing information is updated.
 */
318
static u32 hwmp_route_info_get(struct ieee80211_sub_if_data *sdata,
319
			    struct ieee80211_mgmt *mgmt,
320
			    u8 *hwmp_ie, enum mpath_frame_type action)
321
{
322
	struct ieee80211_local *local = sdata->local;
323 324 325 326 327 328 329 330 331 332 333
	struct mesh_path *mpath;
	struct sta_info *sta;
	bool fresh_info;
	u8 *orig_addr, *ta;
	u32 orig_dsn, orig_metric;
	unsigned long orig_lifetime, exp_time;
	u32 last_hop_metric, new_metric;
	bool process = true;

	rcu_read_lock();
	sta = sta_info_get(local, mgmt->sa);
334 335
	if (!sta) {
		rcu_read_unlock();
336
		return 0;
337
	}
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363

	last_hop_metric = airtime_link_metric_get(local, sta);
	/* Update and check originator routing info */
	fresh_info = true;

	switch (action) {
	case MPATH_PREQ:
		orig_addr = PREQ_IE_ORIG_ADDR(hwmp_ie);
		orig_dsn = PREQ_IE_ORIG_DSN(hwmp_ie);
		orig_lifetime = PREQ_IE_LIFETIME(hwmp_ie);
		orig_metric = PREQ_IE_METRIC(hwmp_ie);
		break;
	case MPATH_PREP:
		/* Originator here refers to the MP that was the destination in
		 * the Path Request. The draft refers to that MP as the
		 * destination address, even though usually it is the origin of
		 * the PREP frame. We divert from the nomenclature in the draft
		 * so that we can easily use a single function to gather path
		 * information from both PREQ and PREP frames.
		 */
		orig_addr = PREP_IE_ORIG_ADDR(hwmp_ie);
		orig_dsn = PREP_IE_ORIG_DSN(hwmp_ie);
		orig_lifetime = PREP_IE_LIFETIME(hwmp_ie);
		orig_metric = PREP_IE_METRIC(hwmp_ie);
		break;
	default:
364
		rcu_read_unlock();
365 366 367 368 369 370 371
		return 0;
	}
	new_metric = orig_metric + last_hop_metric;
	if (new_metric < orig_metric)
		new_metric = MAX_METRIC;
	exp_time = TU_TO_EXP_TIME(orig_lifetime);

372
	if (memcmp(orig_addr, sdata->dev->dev_addr, ETH_ALEN) == 0) {
373 374 375 376 377 378
		/* This MP is the originator, we are not interested in this
		 * frame, except for updating transmitter's path info.
		 */
		process = false;
		fresh_info = false;
	} else {
379
		mpath = mesh_path_lookup(orig_addr, sdata);
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394
		if (mpath) {
			spin_lock_bh(&mpath->state_lock);
			if (mpath->flags & MESH_PATH_FIXED)
				fresh_info = false;
			else if ((mpath->flags & MESH_PATH_ACTIVE) &&
			    (mpath->flags & MESH_PATH_DSN_VALID)) {
				if (DSN_GT(mpath->dsn, orig_dsn) ||
				    (mpath->dsn == orig_dsn &&
				     action == MPATH_PREQ &&
				     new_metric > mpath->metric)) {
					process = false;
					fresh_info = false;
				}
			}
		} else {
395 396
			mesh_path_add(orig_addr, sdata);
			mpath = mesh_path_lookup(orig_addr, sdata);
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427
			if (!mpath) {
				rcu_read_unlock();
				return 0;
			}
			spin_lock_bh(&mpath->state_lock);
		}

		if (fresh_info) {
			mesh_path_assign_nexthop(mpath, sta);
			mpath->flags |= MESH_PATH_DSN_VALID;
			mpath->metric = new_metric;
			mpath->dsn = orig_dsn;
			mpath->exp_time = time_after(mpath->exp_time, exp_time)
					  ?  mpath->exp_time : exp_time;
			mesh_path_activate(mpath);
			spin_unlock_bh(&mpath->state_lock);
			mesh_path_tx_pending(mpath);
			/* draft says preq_id should be saved to, but there does
			 * not seem to be any use for it, skipping by now
			 */
		} else
			spin_unlock_bh(&mpath->state_lock);
	}

	/* Update and check transmitter routing info */
	ta = mgmt->sa;
	if (memcmp(orig_addr, ta, ETH_ALEN) == 0)
		fresh_info = false;
	else {
		fresh_info = true;

428
		mpath = mesh_path_lookup(ta, sdata);
429 430 431 432 433 434 435
		if (mpath) {
			spin_lock_bh(&mpath->state_lock);
			if ((mpath->flags & MESH_PATH_FIXED) ||
				((mpath->flags & MESH_PATH_ACTIVE) &&
					(last_hop_metric > mpath->metric)))
				fresh_info = false;
		} else {
436 437
			mesh_path_add(ta, sdata);
			mpath = mesh_path_lookup(ta, sdata);
438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462
			if (!mpath) {
				rcu_read_unlock();
				return 0;
			}
			spin_lock_bh(&mpath->state_lock);
		}

		if (fresh_info) {
			mesh_path_assign_nexthop(mpath, sta);
			mpath->flags &= ~MESH_PATH_DSN_VALID;
			mpath->metric = last_hop_metric;
			mpath->exp_time = time_after(mpath->exp_time, exp_time)
					  ?  mpath->exp_time : exp_time;
			mesh_path_activate(mpath);
			spin_unlock_bh(&mpath->state_lock);
			mesh_path_tx_pending(mpath);
		} else
			spin_unlock_bh(&mpath->state_lock);
	}

	rcu_read_unlock();

	return process ? new_metric : 0;
}

463
static void hwmp_preq_frame_process(struct ieee80211_sub_if_data *sdata,
464
				    struct ieee80211_mgmt *mgmt,
465 466
				    u8 *preq_elem, u32 metric)
{
467
	struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
468 469 470 471 472 473 474 475 476 477 478 479 480 481
	struct mesh_path *mpath;
	u8 *dst_addr, *orig_addr;
	u8 dst_flags, ttl;
	u32 orig_dsn, dst_dsn, lifetime;
	bool reply = false;
	bool forward = true;

	/* Update destination DSN, if present */
	dst_addr = PREQ_IE_DST_ADDR(preq_elem);
	orig_addr = PREQ_IE_ORIG_ADDR(preq_elem);
	dst_dsn = PREQ_IE_DST_DSN(preq_elem);
	orig_dsn = PREQ_IE_ORIG_DSN(preq_elem);
	dst_flags = PREQ_IE_DST_F(preq_elem);

R
Rui Paulo 已提交
482
	mhwmp_dbg("received PREQ from %pM\n", orig_addr);
483

484
	if (memcmp(dst_addr, sdata->dev->dev_addr, ETH_ALEN) == 0) {
485
		mhwmp_dbg("PREQ is for us\n");
486 487 488
		forward = false;
		reply = true;
		metric = 0;
489
		if (time_after(jiffies, ifmsh->last_dsn_update +
490
					net_traversal_jiffies(sdata)) ||
491 492 493
		    time_before(jiffies, ifmsh->last_dsn_update)) {
			dst_dsn = ++ifmsh->dsn;
			ifmsh->last_dsn_update = jiffies;
494 495 496
		}
	} else {
		rcu_read_lock();
497
		mpath = mesh_path_lookup(dst_addr, sdata);
498 499 500 501
		if (mpath) {
			if ((!(mpath->flags & MESH_PATH_DSN_VALID)) ||
					DSN_LT(mpath->dsn, dst_dsn)) {
				mpath->dsn = dst_dsn;
502
				mpath->flags |= MESH_PATH_DSN_VALID;
503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518
			} else if ((!(dst_flags & MP_F_DO)) &&
					(mpath->flags & MESH_PATH_ACTIVE)) {
				reply = true;
				metric = mpath->metric;
				dst_dsn = mpath->dsn;
				if (dst_flags & MP_F_RF)
					dst_flags |= MP_F_DO;
				else
					forward = false;
			}
		}
		rcu_read_unlock();
	}

	if (reply) {
		lifetime = PREQ_IE_LIFETIME(preq_elem);
519
		ttl = ifmsh->mshcfg.dot11MeshTTL;
520 521
		if (ttl != 0) {
			mhwmp_dbg("replying to the PREQ\n");
522
			mesh_path_sel_frame_tx(MPATH_PREP, 0, dst_addr,
523 524 525
				cpu_to_le32(dst_dsn), 0, orig_addr,
				cpu_to_le32(orig_dsn), mgmt->sa, 0, ttl,
				cpu_to_le32(lifetime), cpu_to_le32(metric),
526
				0, sdata);
527
		} else
528
			ifmsh->mshstats.dropped_frames_ttl++;
529 530 531 532 533 534 535 536 537
	}

	if (forward) {
		u32 preq_id;
		u8 hopcount, flags;

		ttl = PREQ_IE_TTL(preq_elem);
		lifetime = PREQ_IE_LIFETIME(preq_elem);
		if (ttl <= 1) {
538
			ifmsh->mshstats.dropped_frames_ttl++;
539 540
			return;
		}
R
Rui Paulo 已提交
541
		mhwmp_dbg("forwarding the PREQ from %pM\n", orig_addr);
542 543 544 545 546
		--ttl;
		flags = PREQ_IE_FLAGS(preq_elem);
		preq_id = PREQ_IE_PREQ_ID(preq_elem);
		hopcount = PREQ_IE_HOPCOUNT(preq_elem) + 1;
		mesh_path_sel_frame_tx(MPATH_PREQ, flags, orig_addr,
547
				cpu_to_le32(orig_dsn), dst_flags, dst_addr,
548
				cpu_to_le32(dst_dsn), sdata->dev->broadcast,
549 550
				hopcount, ttl, cpu_to_le32(lifetime),
				cpu_to_le32(metric), cpu_to_le32(preq_id),
551
				sdata);
552
		ifmsh->mshstats.fwded_mcast++;
553
		ifmsh->mshstats.fwded_frames++;
554 555 556 557
	}
}


558
static void hwmp_prep_frame_process(struct ieee80211_sub_if_data *sdata,
559 560 561 562 563 564 565 566 567
				    struct ieee80211_mgmt *mgmt,
				    u8 *prep_elem, u32 metric)
{
	struct mesh_path *mpath;
	u8 *dst_addr, *orig_addr;
	u8 ttl, hopcount, flags;
	u8 next_hop[ETH_ALEN];
	u32 dst_dsn, orig_dsn, lifetime;

R
Rui Paulo 已提交
568
	mhwmp_dbg("received PREP from %pM\n", PREP_IE_ORIG_ADDR(prep_elem));
569

570 571 572 573 574 575 576
	/* Note that we divert from the draft nomenclature and denominate
	 * destination to what the draft refers to as origininator. So in this
	 * function destnation refers to the final destination of the PREP,
	 * which corresponds with the originator of the PREQ which this PREP
	 * replies
	 */
	dst_addr = PREP_IE_DST_ADDR(prep_elem);
577
	if (memcmp(dst_addr, sdata->dev->dev_addr, ETH_ALEN) == 0)
578 579 580 581 582
		/* destination, no forwarding required */
		return;

	ttl = PREP_IE_TTL(prep_elem);
	if (ttl <= 1) {
583
		sdata->u.mesh.mshstats.dropped_frames_ttl++;
584 585 586 587
		return;
	}

	rcu_read_lock();
588
	mpath = mesh_path_lookup(dst_addr, sdata);
589 590 591 592 593 594 595 596
	if (mpath)
		spin_lock_bh(&mpath->state_lock);
	else
		goto fail;
	if (!(mpath->flags & MESH_PATH_ACTIVE)) {
		spin_unlock_bh(&mpath->state_lock);
		goto fail;
	}
597
	memcpy(next_hop, mpath->next_hop->sta.addr, ETH_ALEN);
598 599 600 601 602 603 604 605 606 607
	spin_unlock_bh(&mpath->state_lock);
	--ttl;
	flags = PREP_IE_FLAGS(prep_elem);
	lifetime = PREP_IE_LIFETIME(prep_elem);
	hopcount = PREP_IE_HOPCOUNT(prep_elem) + 1;
	orig_addr = PREP_IE_ORIG_ADDR(prep_elem);
	dst_dsn = PREP_IE_DST_DSN(prep_elem);
	orig_dsn = PREP_IE_ORIG_DSN(prep_elem);

	mesh_path_sel_frame_tx(MPATH_PREP, flags, orig_addr,
608
		cpu_to_le32(orig_dsn), 0, dst_addr,
609
		cpu_to_le32(dst_dsn), mpath->next_hop->sta.addr, hopcount, ttl,
610
		cpu_to_le32(lifetime), cpu_to_le32(metric),
611
		0, sdata);
612
	rcu_read_unlock();
613 614

	sdata->u.mesh.mshstats.fwded_unicast++;
615
	sdata->u.mesh.mshstats.fwded_frames++;
616 617 618 619
	return;

fail:
	rcu_read_unlock();
620
	sdata->u.mesh.mshstats.dropped_frames_no_route++;
621 622 623
	return;
}

624
static void hwmp_perr_frame_process(struct ieee80211_sub_if_data *sdata,
625 626
			     struct ieee80211_mgmt *mgmt, u8 *perr_elem)
{
R
Rui Paulo 已提交
627
	struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
628
	struct mesh_path *mpath;
R
Rui Paulo 已提交
629
	u8 ttl;
630
	u8 *ta, *dst_addr;
R
Rui Paulo 已提交
631
	u8 dst_flags;
632
	u32 dst_dsn;
R
Rui Paulo 已提交
633
	u16 dst_rcode;
634 635

	ta = mgmt->sa;
R
Rui Paulo 已提交
636 637 638 639 640 641 642
	ttl = PERR_IE_TTL(perr_elem);
	if (ttl <= 1) {
		ifmsh->mshstats.dropped_frames_ttl++;
		return;
	}
	ttl--;
	dst_flags = PERR_IE_DST_FLAGS(perr_elem);
643 644
	dst_addr = PERR_IE_DST_ADDR(perr_elem);
	dst_dsn = PERR_IE_DST_DSN(perr_elem);
R
Rui Paulo 已提交
645 646
	dst_rcode = PERR_IE_DST_RCODE(perr_elem);

647
	rcu_read_lock();
648
	mpath = mesh_path_lookup(dst_addr, sdata);
649 650 651
	if (mpath) {
		spin_lock_bh(&mpath->state_lock);
		if (mpath->flags & MESH_PATH_ACTIVE &&
652
		    memcmp(ta, mpath->next_hop->sta.addr, ETH_ALEN) == 0 &&
653 654 655 656 657
		    (!(mpath->flags & MESH_PATH_DSN_VALID) ||
		    DSN_GT(dst_dsn, mpath->dsn))) {
			mpath->flags &= ~MESH_PATH_ACTIVE;
			mpath->dsn = dst_dsn;
			spin_unlock_bh(&mpath->state_lock);
R
Rui Paulo 已提交
658 659
			mesh_path_error_tx(ttl, dst_addr, cpu_to_le32(dst_dsn),
					   cpu_to_le16(dst_rcode),
660
					   sdata->dev->broadcast, sdata);
661 662 663 664 665 666
		} else
			spin_unlock_bh(&mpath->state_lock);
	}
	rcu_read_unlock();
}

667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
static void hwmp_rann_frame_process(struct ieee80211_sub_if_data *sdata,
				struct ieee80211_mgmt *mgmt,
				struct ieee80211_rann_ie *rann)
{
	struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
	struct mesh_path *mpath;
	u8 *ta;
	u8 ttl, flags, hopcount;
	u8 *orig_addr;
	u32 orig_dsn, metric;

	ta = mgmt->sa;
	ttl = rann->rann_ttl;
	if (ttl <= 1) {
		ifmsh->mshstats.dropped_frames_ttl++;
		return;
	}
	ttl--;
	flags = rann->rann_flags;
	orig_addr = rann->rann_addr;
	orig_dsn = rann->rann_seq;
	hopcount = rann->rann_hopcount;
	metric = rann->rann_metric;
	mhwmp_dbg("received RANN from %pM\n", orig_addr);

	rcu_read_lock();
	mpath = mesh_path_lookup(orig_addr, sdata);
	if (!mpath) {
		mesh_path_add(orig_addr, sdata);
		mpath = mesh_path_lookup(orig_addr, sdata);
		if (!mpath) {
			rcu_read_unlock();
			sdata->u.mesh.mshstats.dropped_frames_no_route++;
			return;
		}
		mesh_queue_preq(mpath,
				PREQ_Q_F_START | PREQ_Q_F_REFRESH);
	}
	if (mpath->dsn < orig_dsn) {
		mesh_path_sel_frame_tx(MPATH_RANN, flags, orig_addr,
				       cpu_to_le32(orig_dsn),
				       0, NULL, 0, sdata->dev->broadcast,
				       hopcount, ttl, 0, cpu_to_le32(metric),
				       0, sdata);
		mpath->dsn = orig_dsn;
	}
	rcu_read_unlock();
}
715 716


717
void mesh_rx_path_sel_frame(struct ieee80211_sub_if_data *sdata,
718 719 720 721 722 723 724
			    struct ieee80211_mgmt *mgmt,
			    size_t len)
{
	struct ieee802_11_elems elems;
	size_t baselen;
	u32 last_hop_metric;

725 726 727 728
	/* need action_code */
	if (len < IEEE80211_MIN_ACTION_SIZE + 1)
		return;

729 730 731 732
	baselen = (u8 *) mgmt->u.action.u.mesh_action.variable - (u8 *) mgmt;
	ieee802_11_parse_elems(mgmt->u.action.u.mesh_action.variable,
			len - baselen, &elems);

733 734
	if (elems.preq) {
		if (elems.preq_len != 37)
735 736
			/* Right now we support just 1 destination and no AE */
			return;
737 738 739 740 741 742 743 744
		last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.preq,
						      MPATH_PREQ);
		if (last_hop_metric)
			hwmp_preq_frame_process(sdata, mgmt, elems.preq,
						last_hop_metric);
	}
	if (elems.prep) {
		if (elems.prep_len != 31)
745 746
			/* Right now we support no AE */
			return;
747 748 749 750 751 752 753
		last_hop_metric = hwmp_route_info_get(sdata, mgmt, elems.prep,
						      MPATH_PREP);
		if (last_hop_metric)
			hwmp_prep_frame_process(sdata, mgmt, elems.prep,
						last_hop_metric);
	}
	if (elems.perr) {
R
Rui Paulo 已提交
754
		if (elems.perr_len != 15)
755 756
			/* Right now we support only one destination per PERR */
			return;
757
		hwmp_perr_frame_process(sdata, mgmt, elems.perr);
758
	}
759 760
	if (elems.rann)
		hwmp_rann_frame_process(sdata, mgmt, elems.rann);
761 762 763 764 765 766 767 768 769 770 771 772 773
}

/**
 * mesh_queue_preq - queue a PREQ to a given destination
 *
 * @mpath: mesh path to discover
 * @flags: special attributes of the PREQ to be sent
 *
 * Locking: the function must be called from within a rcu read lock block.
 *
 */
static void mesh_queue_preq(struct mesh_path *mpath, u8 flags)
{
774
	struct ieee80211_sub_if_data *sdata = mpath->sdata;
775
	struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
776 777
	struct mesh_preq_queue *preq_node;

778
	preq_node = kmalloc(sizeof(struct mesh_preq_queue), GFP_ATOMIC);
779
	if (!preq_node) {
780
		mhwmp_dbg("could not allocate PREQ node\n");
781 782 783
		return;
	}

784 785 786
	spin_lock(&ifmsh->mesh_preq_queue_lock);
	if (ifmsh->preq_queue_len == MAX_PREQ_QUEUE_LEN) {
		spin_unlock(&ifmsh->mesh_preq_queue_lock);
787 788
		kfree(preq_node);
		if (printk_ratelimit())
789
			mhwmp_dbg("PREQ node queue full\n");
790 791 792 793 794 795
		return;
	}

	memcpy(preq_node->dst, mpath->dst, ETH_ALEN);
	preq_node->flags = flags;

796 797 798
	list_add_tail(&preq_node->list, &ifmsh->preq_queue.list);
	++ifmsh->preq_queue_len;
	spin_unlock(&ifmsh->mesh_preq_queue_lock);
799

800
	if (time_after(jiffies, ifmsh->last_preq + min_preq_int_jiff(sdata)))
801
		ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
802

803
	else if (time_before(jiffies, ifmsh->last_preq)) {
804 805 806
		/* avoid long wait if did not send preqs for a long time
		 * and jiffies wrapped around
		 */
807
		ifmsh->last_preq = jiffies - min_preq_int_jiff(sdata) - 1;
808
		ieee80211_queue_work(&sdata->local->hw, &ifmsh->work);
809
	} else
810
		mod_timer(&ifmsh->mesh_path_timer, ifmsh->last_preq +
811 812 813 814 815 816
						min_preq_int_jiff(sdata));
}

/**
 * mesh_path_start_discovery - launch a path discovery from the PREQ queue
 *
817
 * @sdata: local mesh subif
818
 */
819
void mesh_path_start_discovery(struct ieee80211_sub_if_data *sdata)
820
{
821
	struct ieee80211_if_mesh *ifmsh = &sdata->u.mesh;
822 823 824 825 826
	struct mesh_preq_queue *preq_node;
	struct mesh_path *mpath;
	u8 ttl, dst_flags;
	u32 lifetime;

827
	spin_lock_bh(&ifmsh->mesh_preq_queue_lock);
828 829
	if (!ifmsh->preq_queue_len ||
		time_before(jiffies, ifmsh->last_preq +
830
				min_preq_int_jiff(sdata))) {
831
		spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
832 833 834
		return;
	}

835
	preq_node = list_first_entry(&ifmsh->preq_queue.list,
836 837
			struct mesh_preq_queue, list);
	list_del(&preq_node->list);
838
	--ifmsh->preq_queue_len;
839
	spin_unlock_bh(&ifmsh->mesh_preq_queue_lock);
840 841

	rcu_read_lock();
842
	mpath = mesh_path_lookup(preq_node->dst, sdata);
843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863
	if (!mpath)
		goto enddiscovery;

	spin_lock_bh(&mpath->state_lock);
	if (preq_node->flags & PREQ_Q_F_START) {
		if (mpath->flags & MESH_PATH_RESOLVING) {
			spin_unlock_bh(&mpath->state_lock);
			goto enddiscovery;
		} else {
			mpath->flags &= ~MESH_PATH_RESOLVED;
			mpath->flags |= MESH_PATH_RESOLVING;
			mpath->discovery_retries = 0;
			mpath->discovery_timeout = disc_timeout_jiff(sdata);
		}
	} else if (!(mpath->flags & MESH_PATH_RESOLVING) ||
			mpath->flags & MESH_PATH_RESOLVED) {
		mpath->flags &= ~MESH_PATH_RESOLVING;
		spin_unlock_bh(&mpath->state_lock);
		goto enddiscovery;
	}

864
	ifmsh->last_preq = jiffies;
865

866
	if (time_after(jiffies, ifmsh->last_dsn_update +
867
				net_traversal_jiffies(sdata)) ||
868 869 870
	    time_before(jiffies, ifmsh->last_dsn_update)) {
		++ifmsh->dsn;
		sdata->u.mesh.last_dsn_update = jiffies;
871 872
	}
	lifetime = default_lifetime(sdata);
873
	ttl = sdata->u.mesh.mshcfg.dot11MeshTTL;
874
	if (ttl == 0) {
875
		sdata->u.mesh.mshstats.dropped_frames_ttl++;
876 877 878 879 880 881 882 883 884 885
		spin_unlock_bh(&mpath->state_lock);
		goto enddiscovery;
	}

	if (preq_node->flags & PREQ_Q_F_REFRESH)
		dst_flags = MP_F_DO;
	else
		dst_flags = MP_F_RF;

	spin_unlock_bh(&mpath->state_lock);
886
	mesh_path_sel_frame_tx(MPATH_PREQ, 0, sdata->dev->dev_addr,
887
			cpu_to_le32(ifmsh->dsn), dst_flags, mpath->dst,
888
			cpu_to_le32(mpath->dsn), sdata->dev->broadcast, 0,
889
			ttl, cpu_to_le32(lifetime), 0,
890
			cpu_to_le32(ifmsh->preq_id++), sdata);
891 892 893 894 895 896 897 898
	mod_timer(&mpath->timer, jiffies + mpath->discovery_timeout);

enddiscovery:
	rcu_read_unlock();
	kfree(preq_node);
}

/**
899
 * mesh_nexthop_lookup - put the appropriate next hop on a mesh frame
900
 *
901
 * @skb: 802.11 frame to be sent
902
 * @sdata: network subif the frame will be sent through
903 904 905 906 907 908
 *
 * Returns: 0 if the next hop was found. Nonzero otherwise. If no next hop is
 * found, the function will start a path discovery and queue the frame so it is
 * sent when the path is resolved. This means the caller must not free the skb
 * in this case.
 */
909 910
int mesh_nexthop_lookup(struct sk_buff *skb,
			struct ieee80211_sub_if_data *sdata)
911 912 913
{
	struct sk_buff *skb_to_free = NULL;
	struct mesh_path *mpath;
914 915
	struct ieee80211_hdr *hdr = (struct ieee80211_hdr *) skb->data;
	u8 *dst_addr = hdr->addr3;
916 917 918
	int err = 0;

	rcu_read_lock();
919
	mpath = mesh_path_lookup(dst_addr, sdata);
920 921

	if (!mpath) {
922 923
		mesh_path_add(dst_addr, sdata);
		mpath = mesh_path_lookup(dst_addr, sdata);
924
		if (!mpath) {
925
			sdata->u.mesh.mshstats.dropped_frames_no_route++;
926 927 928 929 930 931
			err = -ENOSPC;
			goto endlookup;
		}
	}

	if (mpath->flags & MESH_PATH_ACTIVE) {
932
		if (time_after(jiffies, mpath->exp_time +
933
			msecs_to_jiffies(sdata->u.mesh.mshcfg.path_refresh_time))
934 935
				&& !memcmp(sdata->dev->dev_addr, hdr->addr4,
					   ETH_ALEN)
936 937 938 939 940
				&& !(mpath->flags & MESH_PATH_RESOLVING)
				&& !(mpath->flags & MESH_PATH_FIXED)) {
			mesh_queue_preq(mpath,
					PREQ_Q_F_START | PREQ_Q_F_REFRESH);
		}
941
		memcpy(hdr->addr1, mpath->next_hop->sta.addr,
942 943
				ETH_ALEN);
	} else {
944
		struct ieee80211_tx_info *info = IEEE80211_SKB_CB(skb);
945 946 947 948 949 950
		if (!(mpath->flags & MESH_PATH_RESOLVING)) {
			/* Start discovery only if it is not running yet */
			mesh_queue_preq(mpath, PREQ_Q_F_START);
		}

		if (skb_queue_len(&mpath->frame_queue) >=
951 952
				MESH_FRAME_QUEUE_LEN)
			skb_to_free = skb_dequeue(&mpath->frame_queue);
953

954
		info->flags |= IEEE80211_TX_INTFL_NEED_TXPROCESSING;
955 956
		skb_queue_tail(&mpath->frame_queue, skb);
		if (skb_to_free)
957
			mesh_path_discard_frame(skb_to_free, sdata);
958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975
		err = -ENOENT;
	}

endlookup:
	rcu_read_unlock();
	return err;
}

void mesh_path_timer(unsigned long data)
{
	struct ieee80211_sub_if_data *sdata;
	struct mesh_path *mpath;

	rcu_read_lock();
	mpath = (struct mesh_path *) data;
	mpath = rcu_dereference(mpath);
	if (!mpath)
		goto endmpathtimer;
976
	sdata = mpath->sdata;
977 978 979 980 981 982 983

	if (sdata->local->quiescing) {
		rcu_read_unlock();
		return;
	}

	spin_lock_bh(&mpath->state_lock);
984
	if (mpath->flags & MESH_PATH_RESOLVED ||
985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000
			(!(mpath->flags & MESH_PATH_RESOLVING)))
		mpath->flags &= ~(MESH_PATH_RESOLVING | MESH_PATH_RESOLVED);
	else if (mpath->discovery_retries < max_preq_retries(sdata)) {
		++mpath->discovery_retries;
		mpath->discovery_timeout *= 2;
		mesh_queue_preq(mpath, 0);
	} else {
		mpath->flags = 0;
		mpath->exp_time = jiffies;
		mesh_path_flush_pending(mpath);
	}

	spin_unlock_bh(&mpath->state_lock);
endmpathtimer:
	rcu_read_unlock();
}