xref: /freebsd/sys/net80211/ieee80211_hwmp.c (revision 9268022b74279434ed6300244e3f977e56a8ceb5)
1 /*-
2  * Copyright (c) 2009 The FreeBSD Foundation
3  * All rights reserved.
4  *
5  * This software was developed by Rui Paulo under sponsorship from the
6  * FreeBSD Foundation.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in the
15  *    documentation and/or other materials provided with the distribution.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29 #include <sys/cdefs.h>
30 #ifdef __FreeBSD__
31 __FBSDID("$FreeBSD$");
32 #endif
33 
34 /*
35  * IEEE 802.11s Hybrid Wireless Mesh Protocol, HWMP.
36  *
37  * Based on March 2009, D3.0 802.11s draft spec.
38  */
39 #include "opt_inet.h"
40 #include "opt_wlan.h"
41 
42 #include <sys/param.h>
43 #include <sys/systm.h>
44 #include <sys/mbuf.h>
45 #include <sys/malloc.h>
46 #include <sys/kernel.h>
47 
48 #include <sys/socket.h>
49 #include <sys/sockio.h>
50 #include <sys/endian.h>
51 #include <sys/errno.h>
52 #include <sys/proc.h>
53 #include <sys/sysctl.h>
54 
55 #include <net/if.h>
56 #include <net/if_media.h>
57 #include <net/if_llc.h>
58 #include <net/ethernet.h>
59 
60 #include <net/bpf.h>
61 
62 #include <net80211/ieee80211_var.h>
63 #include <net80211/ieee80211_action.h>
64 #include <net80211/ieee80211_input.h>
65 #include <net80211/ieee80211_mesh.h>
66 
67 static void	hwmp_vattach(struct ieee80211vap *);
68 static void	hwmp_vdetach(struct ieee80211vap *);
69 static int	hwmp_newstate(struct ieee80211vap *,
70 		    enum ieee80211_state, int);
71 static int	hwmp_send_action(struct ieee80211vap *,
72 		    const uint8_t [IEEE80211_ADDR_LEN],
73 		    uint8_t *, size_t);
74 static uint8_t * hwmp_add_meshpreq(uint8_t *,
75 		    const struct ieee80211_meshpreq_ie *);
76 static uint8_t * hwmp_add_meshprep(uint8_t *,
77 		    const struct ieee80211_meshprep_ie *);
78 static uint8_t * hwmp_add_meshperr(uint8_t *,
79 		    const struct ieee80211_meshperr_ie *);
80 static uint8_t * hwmp_add_meshrann(uint8_t *,
81 		    const struct ieee80211_meshrann_ie *);
82 static void	hwmp_rootmode_setup(struct ieee80211vap *);
83 static void	hwmp_rootmode_cb(void *);
84 static void	hwmp_rootmode_rann_cb(void *);
85 static void	hwmp_recv_preq(struct ieee80211vap *, struct ieee80211_node *,
86 		    const struct ieee80211_frame *,
87 		    const struct ieee80211_meshpreq_ie *);
88 static int	hwmp_send_preq(struct ieee80211vap *,
89 		    const uint8_t [IEEE80211_ADDR_LEN],
90 		    struct ieee80211_meshpreq_ie *,
91 		    struct timeval *, struct timeval *);
92 static void	hwmp_recv_prep(struct ieee80211vap *, struct ieee80211_node *,
93 		    const struct ieee80211_frame *,
94 		    const struct ieee80211_meshprep_ie *);
95 static int	hwmp_send_prep(struct ieee80211vap *,
96 		    const uint8_t [IEEE80211_ADDR_LEN],
97 		    struct ieee80211_meshprep_ie *);
98 static void	hwmp_recv_perr(struct ieee80211vap *, struct ieee80211_node *,
99 		    const struct ieee80211_frame *,
100 		    const struct ieee80211_meshperr_ie *);
101 static int	hwmp_send_perr(struct ieee80211vap *,
102 		    const uint8_t [IEEE80211_ADDR_LEN],
103 		    struct ieee80211_meshperr_ie *);
104 static void	hwmp_senderror(struct ieee80211vap *,
105 		    const uint8_t [IEEE80211_ADDR_LEN],
106 		    struct ieee80211_mesh_route *, int);
107 static void	hwmp_recv_rann(struct ieee80211vap *, struct ieee80211_node *,
108 		   const struct ieee80211_frame *,
109 		   const struct ieee80211_meshrann_ie *);
110 static int	hwmp_send_rann(struct ieee80211vap *,
111 		    const uint8_t [IEEE80211_ADDR_LEN],
112 		    struct ieee80211_meshrann_ie *);
113 static struct ieee80211_node *
114 		hwmp_discover(struct ieee80211vap *,
115 		    const uint8_t [IEEE80211_ADDR_LEN], struct mbuf *);
116 static void	hwmp_peerdown(struct ieee80211_node *);
117 
118 static struct timeval ieee80211_hwmp_preqminint = { 0, 100000 };
119 static struct timeval ieee80211_hwmp_perrminint = { 0, 100000 };
120 
121 /* unalligned little endian access */
122 #define LE_WRITE_2(p, v) do {				\
123 	((uint8_t *)(p))[0] = (v) & 0xff;		\
124 	((uint8_t *)(p))[1] = ((v) >> 8) & 0xff;	\
125 } while (0)
126 #define LE_WRITE_4(p, v) do {				\
127 	((uint8_t *)(p))[0] = (v) & 0xff;		\
128 	((uint8_t *)(p))[1] = ((v) >> 8) & 0xff;	\
129 	((uint8_t *)(p))[2] = ((v) >> 16) & 0xff;	\
130 	((uint8_t *)(p))[3] = ((v) >> 24) & 0xff;	\
131 } while (0)
132 
133 
134 /* NB: the Target Address set in a Proactive PREQ is the broadcast address. */
135 static const uint8_t	broadcastaddr[IEEE80211_ADDR_LEN] =
136 	{ 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
137 
138 typedef uint32_t ieee80211_hwmp_seq;
139 #define	HWMP_SEQ_LT(a, b)	((int32_t)((a)-(b)) < 0)
140 #define	HWMP_SEQ_LEQ(a, b)	((int32_t)((a)-(b)) <= 0)
141 #define	HWMP_SEQ_EQ(a, b)	((int32_t)((a)-(b)) == 0)
142 #define	HWMP_SEQ_GT(a, b)	((int32_t)((a)-(b)) > 0)
143 #define	HWMP_SEQ_GEQ(a, b)	((int32_t)((a)-(b)) >= 0)
144 
145 #define HWMP_SEQ_MAX(a, b)	(a > b ? a : b)
146 
147 /*
148  * Private extension of ieee80211_mesh_route.
149  */
150 struct ieee80211_hwmp_route {
151 	ieee80211_hwmp_seq	hr_seq;		/* last HWMP seq seen from dst*/
152 	ieee80211_hwmp_seq	hr_preqid;	/* last PREQ ID seen from dst */
153 	ieee80211_hwmp_seq	hr_origseq;	/* seq. no. on our latest PREQ*/
154 	struct timeval		hr_lastpreq;	/* last time we sent a PREQ */
155 	struct timeval		hr_lastrootconf; /* last sent PREQ root conf */
156 	int			hr_preqretries;	/* number of discoveries */
157 	int			hr_lastdiscovery; /* last discovery in ticks */
158 };
159 struct ieee80211_hwmp_state {
160 	ieee80211_hwmp_seq	hs_seq;		/* next seq to be used */
161 	ieee80211_hwmp_seq	hs_preqid;	/* next PREQ ID to be used */
162 	int			hs_rootmode;	/* proactive HWMP */
163 	struct timeval		hs_lastperr;	/* last time we sent a PERR */
164 	struct callout		hs_roottimer;
165 	uint8_t			hs_maxhops;	/* max hop count */
166 };
167 
168 static SYSCTL_NODE(_net_wlan, OID_AUTO, hwmp, CTLFLAG_RD, 0,
169     "IEEE 802.11s HWMP parameters");
170 static int	ieee80211_hwmp_targetonly = 0;
171 SYSCTL_INT(_net_wlan_hwmp, OID_AUTO, targetonly, CTLFLAG_RW,
172     &ieee80211_hwmp_targetonly, 0, "Set TO bit on generated PREQs");
173 static int	ieee80211_hwmp_pathtimeout = -1;
174 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, pathlifetime, CTLTYPE_INT | CTLFLAG_RW,
175     &ieee80211_hwmp_pathtimeout, 0, ieee80211_sysctl_msecs_ticks, "I",
176     "path entry lifetime (ms)");
177 static int	ieee80211_hwmp_maxpreq_retries = -1;
178 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, maxpreq_retries, CTLTYPE_INT | CTLFLAG_RW,
179     &ieee80211_hwmp_maxpreq_retries, 0, ieee80211_sysctl_msecs_ticks, "I",
180     "maximum number of preq retries");
181 static int	ieee80211_hwmp_net_diameter_traversaltime = -1;
182 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, net_diameter_traversal_time,
183     CTLTYPE_INT | CTLFLAG_RW, &ieee80211_hwmp_net_diameter_traversaltime, 0,
184     ieee80211_sysctl_msecs_ticks, "I",
185     "estimate travelse time across the MBSS (ms)");
186 static int	ieee80211_hwmp_roottimeout = -1;
187 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, roottimeout, CTLTYPE_INT | CTLFLAG_RW,
188     &ieee80211_hwmp_roottimeout, 0, ieee80211_sysctl_msecs_ticks, "I",
189     "root PREQ timeout (ms)");
190 static int	ieee80211_hwmp_rootint = -1;
191 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, rootint, CTLTYPE_INT | CTLFLAG_RW,
192     &ieee80211_hwmp_rootint, 0, ieee80211_sysctl_msecs_ticks, "I",
193     "root interval (ms)");
194 static int	ieee80211_hwmp_rannint = -1;
195 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, rannint, CTLTYPE_INT | CTLFLAG_RW,
196     &ieee80211_hwmp_rannint, 0, ieee80211_sysctl_msecs_ticks, "I",
197     "root announcement interval (ms)");
198 static struct timeval ieee80211_hwmp_rootconfint = { 0, 0 };
199 static int	ieee80211_hwmp_rootconfint_internal = -1;
200 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, rootconfint, CTLTYPE_INT | CTLFLAG_RD,
201     &ieee80211_hwmp_rootconfint_internal, 0, ieee80211_sysctl_msecs_ticks, "I",
202     "root confirmation interval (ms) (read-only)");
203 
204 #define	IEEE80211_HWMP_DEFAULT_MAXHOPS	31
205 
206 static	ieee80211_recv_action_func hwmp_recv_action_meshpath;
207 
208 static struct ieee80211_mesh_proto_path mesh_proto_hwmp = {
209 	.mpp_descr	= "HWMP",
210 	.mpp_ie		= IEEE80211_MESHCONF_PATH_HWMP,
211 	.mpp_discover	= hwmp_discover,
212 	.mpp_peerdown	= hwmp_peerdown,
213 	.mpp_senderror	= hwmp_senderror,
214 	.mpp_vattach	= hwmp_vattach,
215 	.mpp_vdetach	= hwmp_vdetach,
216 	.mpp_newstate	= hwmp_newstate,
217 	.mpp_privlen	= sizeof(struct ieee80211_hwmp_route),
218 };
219 SYSCTL_PROC(_net_wlan_hwmp, OID_AUTO, inact, CTLTYPE_INT | CTLFLAG_RW,
220 	&mesh_proto_hwmp.mpp_inact, 0, ieee80211_sysctl_msecs_ticks, "I",
221 	"mesh route inactivity timeout (ms)");
222 
223 
224 static void
225 ieee80211_hwmp_init(void)
226 {
227 	/* Default values as per amendment */
228 	ieee80211_hwmp_pathtimeout = msecs_to_ticks(5*1000);
229 	ieee80211_hwmp_roottimeout = msecs_to_ticks(5*1000);
230 	ieee80211_hwmp_rootint = msecs_to_ticks(2*1000);
231 	ieee80211_hwmp_rannint = msecs_to_ticks(1*1000);
232 	ieee80211_hwmp_rootconfint_internal = msecs_to_ticks(2*1000);
233 	ieee80211_hwmp_maxpreq_retries = 3;
234 	/*
235 	 * (TU): A measurement of time equal to 1024 μs,
236 	 * 500 TU is 512 ms.
237 	 */
238 	ieee80211_hwmp_net_diameter_traversaltime = msecs_to_ticks(512);
239 
240 	/*
241 	 * NB: I dont know how to make SYSCTL_PROC that calls ms to ticks
242 	 * and return a struct timeval...
243 	 */
244 	ieee80211_hwmp_rootconfint.tv_usec =
245 	    ieee80211_hwmp_rootconfint_internal * 1000;
246 
247 	/*
248 	 * Register action frame handler.
249 	 */
250 	ieee80211_recv_action_register(IEEE80211_ACTION_CAT_MESH,
251 	    IEEE80211_ACTION_MESH_HWMP, hwmp_recv_action_meshpath);
252 
253 	/* NB: default is 5 secs per spec */
254 	mesh_proto_hwmp.mpp_inact = msecs_to_ticks(5*1000);
255 
256 	/*
257 	 * Register HWMP.
258 	 */
259 	ieee80211_mesh_register_proto_path(&mesh_proto_hwmp);
260 }
261 SYSINIT(wlan_hwmp, SI_SUB_DRIVERS, SI_ORDER_SECOND, ieee80211_hwmp_init, NULL);
262 
263 void
264 hwmp_vattach(struct ieee80211vap *vap)
265 {
266 	struct ieee80211_hwmp_state *hs;
267 
268 	KASSERT(vap->iv_opmode == IEEE80211_M_MBSS,
269 	    ("not a mesh vap, opmode %d", vap->iv_opmode));
270 
271 	hs = malloc(sizeof(struct ieee80211_hwmp_state), M_80211_VAP,
272 	    M_NOWAIT | M_ZERO);
273 	if (hs == NULL) {
274 		printf("%s: couldn't alloc HWMP state\n", __func__);
275 		return;
276 	}
277 	hs->hs_maxhops = IEEE80211_HWMP_DEFAULT_MAXHOPS;
278 	callout_init(&hs->hs_roottimer, CALLOUT_MPSAFE);
279 	vap->iv_hwmp = hs;
280 }
281 
282 void
283 hwmp_vdetach(struct ieee80211vap *vap)
284 {
285 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
286 
287 	callout_drain(&hs->hs_roottimer);
288 	free(vap->iv_hwmp, M_80211_VAP);
289 	vap->iv_hwmp = NULL;
290 }
291 
292 int
293 hwmp_newstate(struct ieee80211vap *vap, enum ieee80211_state ostate, int arg)
294 {
295 	enum ieee80211_state nstate = vap->iv_state;
296 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
297 
298 	IEEE80211_DPRINTF(vap, IEEE80211_MSG_STATE, "%s: %s -> %s (%d)\n",
299 	    __func__, ieee80211_state_name[ostate],
300 	    ieee80211_state_name[nstate], arg);
301 
302 	if (nstate != IEEE80211_S_RUN && ostate == IEEE80211_S_RUN)
303 		callout_drain(&hs->hs_roottimer);
304 	if (nstate == IEEE80211_S_RUN)
305 		hwmp_rootmode_setup(vap);
306 	return 0;
307 }
308 
309 /*
310  * Verify the length of an HWMP PREQ and return the number
311  * of destinations >= 1, if verification fails -1 is returned.
312  */
313 static int
314 verify_mesh_preq_len(struct ieee80211vap *vap,
315     const struct ieee80211_frame *wh, const uint8_t *iefrm)
316 {
317 	int alloc_sz = -1;
318 	int ndest = -1;
319 	if (iefrm[2] & IEEE80211_MESHPREQ_FLAGS_AE) {
320 		/* Originator External Address  present */
321 		alloc_sz =  IEEE80211_MESHPREQ_BASE_SZ_AE;
322 		ndest = iefrm[IEEE80211_MESHPREQ_TCNT_OFFSET_AE];
323 	} else {
324 		/* w/o Originator External Address */
325 		alloc_sz =  IEEE80211_MESHPREQ_BASE_SZ;
326 		ndest = iefrm[IEEE80211_MESHPREQ_TCNT_OFFSET];
327 	}
328 	alloc_sz += ndest * IEEE80211_MESHPREQ_TRGT_SZ;
329 
330 	if(iefrm[1] != (alloc_sz)) {
331 		IEEE80211_DISCARD(vap,
332 		    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
333 		    wh, NULL, "PREQ (AE=%s) with wrong len",
334 		    iefrm[2] & IEEE80211_MESHPREQ_FLAGS_AE ? "1" : "0");
335 		return (-1);
336 	}
337 	return ndest;
338 }
339 
340 /*
341  * Verify the length of an HWMP PREP and returns 1 on success,
342  * otherwise -1.
343  */
344 static int
345 verify_mesh_prep_len(struct ieee80211vap *vap,
346     const struct ieee80211_frame *wh, const uint8_t *iefrm)
347 {
348 	int alloc_sz = -1;
349 	if (iefrm[2] & IEEE80211_MESHPREP_FLAGS_AE) {
350 		if (iefrm[1] == IEEE80211_MESHPREP_BASE_SZ_AE)
351 			alloc_sz = IEEE80211_MESHPREP_BASE_SZ_AE;
352 	} else if (iefrm[1] == IEEE80211_MESHPREP_BASE_SZ)
353 		alloc_sz = IEEE80211_MESHPREP_BASE_SZ;
354 	if(alloc_sz < 0) {
355 		IEEE80211_DISCARD(vap,
356 		    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
357 		    wh, NULL, "PREP (AE=%s) with wrong len",
358 		    iefrm[2] & IEEE80211_MESHPREP_FLAGS_AE ? "1" : "0");
359 		return (-1);
360 	}
361 	return (1);
362 }
363 
364 /*
365  * Verify the length of an HWMP PERR and return the number
366  * of destinations >= 1, if verification fails -1 is returned.
367  */
368 static int
369 verify_mesh_perr_len(struct ieee80211vap *vap,
370     const struct ieee80211_frame *wh, const uint8_t *iefrm)
371 {
372 	int alloc_sz = -1;
373 	const uint8_t *iefrm_t = iefrm;
374 	uint8_t ndest = iefrm_t[IEEE80211_MESHPERR_NDEST_OFFSET];
375 	int i;
376 
377 	if(ndest > IEEE80211_MESHPERR_MAXDEST) {
378 		IEEE80211_DISCARD(vap,
379 		    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
380 		    wh, NULL, "PERR with wrong number of destionat (>19), %u",
381 		    ndest);
382 		return (-1);
383 	}
384 
385 	iefrm_t += IEEE80211_MESHPERR_NDEST_OFFSET + 1; /* flag is next field */
386 	/* We need to check each destionation flag to know size */
387 	for(i = 0; i<ndest; i++) {
388 		if ((*iefrm_t) & IEEE80211_MESHPERR_FLAGS_AE)
389 			iefrm_t += IEEE80211_MESHPERR_DEST_SZ_AE;
390 		else
391 			iefrm_t += IEEE80211_MESHPERR_DEST_SZ;
392 	}
393 
394 	alloc_sz = (iefrm_t - iefrm) - 2; /* action + code */
395 	if(alloc_sz !=  iefrm[1]) {
396 		IEEE80211_DISCARD(vap,
397 		    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
398 		    wh, NULL, "%s", "PERR with wrong len");
399 		return (-1);
400 	}
401 	return ndest;
402 }
403 
404 static int
405 hwmp_recv_action_meshpath(struct ieee80211_node *ni,
406 	const struct ieee80211_frame *wh,
407 	const uint8_t *frm, const uint8_t *efrm)
408 {
409 	struct ieee80211vap *vap = ni->ni_vap;
410 	struct ieee80211_meshpreq_ie *preq;
411 	struct ieee80211_meshprep_ie *prep;
412 	struct ieee80211_meshperr_ie *perr;
413 	struct ieee80211_meshrann_ie rann;
414 	const uint8_t *iefrm = frm + 2; /* action + code */
415 	const uint8_t *iefrm_t = iefrm; /* temporary pointer */
416 	int ndest = -1;
417 	int found = 0;
418 
419 	while (efrm - iefrm > 1) {
420 		IEEE80211_VERIFY_LENGTH(efrm - iefrm, iefrm[1] + 2, return 0);
421 		switch (*iefrm) {
422 		case IEEE80211_ELEMID_MESHPREQ:
423 		{
424 			int i = 0;
425 
426 			iefrm_t = iefrm;
427 			ndest = verify_mesh_preq_len(vap, wh, iefrm_t);
428 			if (ndest < 0) {
429 				vap->iv_stats.is_rx_mgtdiscard++;
430 				break;
431 			}
432 			preq = malloc(sizeof(*preq) +
433 			    (ndest - 1) * sizeof(*preq->preq_targets),
434 			    M_80211_MESH_PREQ, M_NOWAIT | M_ZERO);
435 			KASSERT(preq != NULL, ("preq == NULL"));
436 
437 			preq->preq_ie = *iefrm_t++;
438 			preq->preq_len = *iefrm_t++;
439 			preq->preq_flags = *iefrm_t++;
440 			preq->preq_hopcount = *iefrm_t++;
441 			preq->preq_ttl = *iefrm_t++;
442 			preq->preq_id = LE_READ_4(iefrm_t); iefrm_t += 4;
443 			IEEE80211_ADDR_COPY(preq->preq_origaddr, iefrm_t);
444 			iefrm_t += 6;
445 			preq->preq_origseq = LE_READ_4(iefrm_t); iefrm_t += 4;
446 			/* NB: may have Originator Proxied Address */
447 			if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE)  {
448 				IEEE80211_ADDR_COPY(
449 				    preq->preq_orig_ext_addr, iefrm_t);
450 				iefrm_t += 6;
451 			}
452 			preq->preq_lifetime = LE_READ_4(iefrm_t); iefrm_t += 4;
453 			preq->preq_metric = LE_READ_4(iefrm_t); iefrm_t += 4;
454 			preq->preq_tcount = *iefrm_t++;
455 
456 			for (i = 0; i < preq->preq_tcount; i++) {
457 				preq->preq_targets[i].target_flags = *iefrm_t++;
458 				IEEE80211_ADDR_COPY(
459 				    preq->preq_targets[i].target_addr, iefrm_t);
460 				iefrm_t += 6;
461 				preq->preq_targets[i].target_seq =
462 				    LE_READ_4(iefrm_t);
463 				iefrm_t += 4;
464 			}
465 
466 			hwmp_recv_preq(vap, ni, wh, preq);
467 			free(preq, M_80211_MESH_PREQ);
468 			found++;
469 			break;
470 		}
471 		case IEEE80211_ELEMID_MESHPREP:
472 		{
473 			iefrm_t = iefrm;
474 			ndest = verify_mesh_prep_len(vap, wh, iefrm_t);
475 			if (ndest < 0) {
476 				vap->iv_stats.is_rx_mgtdiscard++;
477 				break;
478 			}
479 			prep = malloc(sizeof(*prep),
480 			    M_80211_MESH_PREP, M_NOWAIT | M_ZERO);
481 			KASSERT(prep != NULL, ("prep == NULL"));
482 
483 			prep->prep_ie = *iefrm_t++;
484 			prep->prep_len = *iefrm_t++;
485 			prep->prep_flags = *iefrm_t++;
486 			prep->prep_hopcount = *iefrm_t++;
487 			prep->prep_ttl = *iefrm_t++;
488 			IEEE80211_ADDR_COPY(prep->prep_targetaddr, iefrm_t);
489 			iefrm_t += 6;
490 			prep->prep_targetseq = LE_READ_4(iefrm_t); iefrm_t += 4;
491 			/* NB: May have Target Proxied Address */
492 			if (prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE)  {
493 				IEEE80211_ADDR_COPY(
494 				    prep->prep_target_ext_addr, iefrm_t);
495 				iefrm_t += 6;
496 			}
497 			prep->prep_lifetime = LE_READ_4(iefrm_t); iefrm_t += 4;
498 			prep->prep_metric = LE_READ_4(iefrm_t); iefrm_t += 4;
499 			IEEE80211_ADDR_COPY(prep->prep_origaddr, iefrm_t);
500 			iefrm_t += 6;
501 			prep->prep_origseq = LE_READ_4(iefrm_t); iefrm_t += 4;
502 
503 			hwmp_recv_prep(vap, ni, wh, prep);
504 			free(prep, M_80211_MESH_PREP);
505 			found++;
506 			break;
507 		}
508 		case IEEE80211_ELEMID_MESHPERR:
509 		{
510 			int i = 0;
511 
512 			iefrm_t = iefrm;
513 			ndest = verify_mesh_perr_len(vap, wh, iefrm_t);
514 			if (ndest < 0) {
515 				vap->iv_stats.is_rx_mgtdiscard++;
516 				break;
517 			}
518 			perr = malloc(sizeof(*perr) +
519 			    (ndest - 1) * sizeof(*perr->perr_dests),
520 			    M_80211_MESH_PERR, M_NOWAIT | M_ZERO);
521 			KASSERT(perr != NULL, ("perr == NULL"));
522 
523 			perr->perr_ie = *iefrm_t++;
524 			perr->perr_len = *iefrm_t++;
525 			perr->perr_ttl = *iefrm_t++;
526 			perr->perr_ndests = *iefrm_t++;
527 
528 			for (i = 0; i<perr->perr_ndests; i++) {
529 				perr->perr_dests[i].dest_flags = *iefrm_t++;
530 				IEEE80211_ADDR_COPY(
531 				    perr->perr_dests[i].dest_addr, iefrm_t);
532 				iefrm_t += 6;
533 				perr->perr_dests[i].dest_seq = LE_READ_4(iefrm_t);
534 				iefrm_t += 4;
535 				/* NB: May have Target Proxied Address */
536 				if (perr->perr_dests[i].dest_flags &
537 				    IEEE80211_MESHPERR_FLAGS_AE) {
538 					IEEE80211_ADDR_COPY(
539 					    perr->perr_dests[i].dest_ext_addr,
540 					    iefrm_t);
541 					iefrm_t += 6;
542 				}
543 				perr->perr_dests[i].dest_rcode =
544 				    LE_READ_2(iefrm_t);
545 				iefrm_t += 2;
546 			}
547 
548 			hwmp_recv_perr(vap, ni, wh, perr);
549 			free(perr, M_80211_MESH_PERR);
550 			found++;
551 			break;
552 		}
553 		case IEEE80211_ELEMID_MESHRANN:
554 		{
555 			const struct ieee80211_meshrann_ie *mrann =
556 			    (const struct ieee80211_meshrann_ie *) iefrm;
557 			if (mrann->rann_len !=
558 			    sizeof(struct ieee80211_meshrann_ie) - 2) {
559 				IEEE80211_DISCARD(vap,
560 				    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
561 				    wh, NULL, "%s", "RAN with wrong len");
562 				    vap->iv_stats.is_rx_mgtdiscard++;
563 				return 1;
564 			}
565 			memcpy(&rann, mrann, sizeof(rann));
566 			rann.rann_seq = LE_READ_4(&mrann->rann_seq);
567 			rann.rann_interval = LE_READ_4(&mrann->rann_interval);
568 			rann.rann_metric = LE_READ_4(&mrann->rann_metric);
569 			hwmp_recv_rann(vap, ni, wh, &rann);
570 			found++;
571 			break;
572 		}
573 		}
574 		iefrm += iefrm[1] + 2;
575 	}
576 	if (!found) {
577 		IEEE80211_DISCARD(vap,
578 		    IEEE80211_MSG_ACTION | IEEE80211_MSG_HWMP,
579 		    wh, NULL, "%s", "PATH SEL action without IE");
580 		vap->iv_stats.is_rx_mgtdiscard++;
581 	}
582 	return 0;
583 }
584 
585 static int
586 hwmp_send_action(struct ieee80211vap *vap,
587     const uint8_t da[IEEE80211_ADDR_LEN],
588     uint8_t *ie, size_t len)
589 {
590 	struct ieee80211_node *ni;
591 	struct ieee80211com *ic;
592 	struct ieee80211_bpf_params params;
593 	struct mbuf *m;
594 	uint8_t *frm;
595 	int ret;
596 
597 	if (IEEE80211_IS_MULTICAST(da)) {
598 		ni = ieee80211_ref_node(vap->iv_bss);
599 #ifdef IEEE80211_DEBUG_REFCNT
600 		IEEE80211_DPRINTF(vap, IEEE80211_MSG_NODE,
601 		"ieee80211_ref_node (%s:%u) %p<%s> refcnt %d\n",
602 		__func__, __LINE__,
603 		ni, ether_sprintf(ni->ni_macaddr),
604 		ieee80211_node_refcnt(ni)+1);
605 #endif
606 		ieee80211_ref_node(ni);
607 	}
608 	else
609 		ni = ieee80211_mesh_find_txnode(vap, da);
610 
611 	if (vap->iv_state == IEEE80211_S_CAC) {
612 		IEEE80211_NOTE(vap, IEEE80211_MSG_OUTPUT, ni,
613 		    "block %s frame in CAC state", "HWMP action");
614 		vap->iv_stats.is_tx_badstate++;
615 		return EIO;	/* XXX */
616 	}
617 
618 	KASSERT(ni != NULL, ("null node"));
619 	ic = ni->ni_ic;
620 
621 	m = ieee80211_getmgtframe(&frm,
622 	    ic->ic_headroom + sizeof(struct ieee80211_frame),
623 	    sizeof(struct ieee80211_action) + len
624 	);
625 	if (m == NULL) {
626 		ieee80211_free_node(ni);
627 		vap->iv_stats.is_tx_nobuf++;
628 		return ENOMEM;
629 	}
630 	*frm++ = IEEE80211_ACTION_CAT_MESH;
631 	*frm++ = IEEE80211_ACTION_MESH_HWMP;
632 	switch (*ie) {
633 	case IEEE80211_ELEMID_MESHPREQ:
634 		frm = hwmp_add_meshpreq(frm,
635 		    (struct ieee80211_meshpreq_ie *)ie);
636 		break;
637 	case IEEE80211_ELEMID_MESHPREP:
638 		frm = hwmp_add_meshprep(frm,
639 		    (struct ieee80211_meshprep_ie *)ie);
640 		break;
641 	case IEEE80211_ELEMID_MESHPERR:
642 		frm = hwmp_add_meshperr(frm,
643 		    (struct ieee80211_meshperr_ie *)ie);
644 		break;
645 	case IEEE80211_ELEMID_MESHRANN:
646 		frm = hwmp_add_meshrann(frm,
647 		    (struct ieee80211_meshrann_ie *)ie);
648 		break;
649 	}
650 
651 	m->m_pkthdr.len = m->m_len = frm - mtod(m, uint8_t *);
652 	M_PREPEND(m, sizeof(struct ieee80211_frame), M_NOWAIT);
653 	if (m == NULL) {
654 		ieee80211_free_node(ni);
655 		vap->iv_stats.is_tx_nobuf++;
656 		return ENOMEM;
657 	}
658 
659 	IEEE80211_TX_LOCK(ic);
660 
661 	ieee80211_send_setup(ni, m,
662 	    IEEE80211_FC0_TYPE_MGT | IEEE80211_FC0_SUBTYPE_ACTION,
663 	    IEEE80211_NONQOS_TID, vap->iv_myaddr, da, vap->iv_myaddr);
664 
665 	m->m_flags |= M_ENCAP;		/* mark encapsulated */
666 	IEEE80211_NODE_STAT(ni, tx_mgmt);
667 
668 	memset(&params, 0, sizeof(params));
669 	params.ibp_pri = WME_AC_VO;
670 	params.ibp_rate0 = ni->ni_txparms->mgmtrate;
671 	if (IEEE80211_IS_MULTICAST(da))
672 		params.ibp_try0 = 1;
673 	else
674 		params.ibp_try0 = ni->ni_txparms->maxretry;
675 	params.ibp_power = ni->ni_txpower;
676 	ret = ieee80211_raw_output(vap, ni, m, &params);
677 	IEEE80211_TX_UNLOCK(ic);
678 	return (ret);
679 }
680 
681 #define ADDSHORT(frm, v) do {		\
682 	frm[0] = (v) & 0xff;		\
683 	frm[1] = (v) >> 8;		\
684 	frm += 2;			\
685 } while (0)
686 #define ADDWORD(frm, v) do {		\
687 	LE_WRITE_4(frm, v);		\
688 	frm += 4;			\
689 } while (0)
690 /*
691  * Add a Mesh Path Request IE to a frame.
692  */
693 #define	PREQ_TFLAGS(n)	preq->preq_targets[n].target_flags
694 #define	PREQ_TADDR(n)	preq->preq_targets[n].target_addr
695 #define	PREQ_TSEQ(n)	preq->preq_targets[n].target_seq
696 static uint8_t *
697 hwmp_add_meshpreq(uint8_t *frm, const struct ieee80211_meshpreq_ie *preq)
698 {
699 	int i;
700 
701 	*frm++ = IEEE80211_ELEMID_MESHPREQ;
702 	*frm++ = preq->preq_len;	/* len already calculated */
703 	*frm++ = preq->preq_flags;
704 	*frm++ = preq->preq_hopcount;
705 	*frm++ = preq->preq_ttl;
706 	ADDWORD(frm, preq->preq_id);
707 	IEEE80211_ADDR_COPY(frm, preq->preq_origaddr); frm += 6;
708 	ADDWORD(frm, preq->preq_origseq);
709 	if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE) {
710 		IEEE80211_ADDR_COPY(frm, preq->preq_orig_ext_addr);
711 		frm += 6;
712 	}
713 	ADDWORD(frm, preq->preq_lifetime);
714 	ADDWORD(frm, preq->preq_metric);
715 	*frm++ = preq->preq_tcount;
716 	for (i = 0; i < preq->preq_tcount; i++) {
717 		*frm++ = PREQ_TFLAGS(i);
718 		IEEE80211_ADDR_COPY(frm, PREQ_TADDR(i));
719 		frm += 6;
720 		ADDWORD(frm, PREQ_TSEQ(i));
721 	}
722 	return frm;
723 }
724 #undef	PREQ_TFLAGS
725 #undef	PREQ_TADDR
726 #undef	PREQ_TSEQ
727 
728 /*
729  * Add a Mesh Path Reply IE to a frame.
730  */
731 static uint8_t *
732 hwmp_add_meshprep(uint8_t *frm, const struct ieee80211_meshprep_ie *prep)
733 {
734 	*frm++ = IEEE80211_ELEMID_MESHPREP;
735 	*frm++ = prep->prep_len;	/* len already calculated */
736 	*frm++ = prep->prep_flags;
737 	*frm++ = prep->prep_hopcount;
738 	*frm++ = prep->prep_ttl;
739 	IEEE80211_ADDR_COPY(frm, prep->prep_targetaddr); frm += 6;
740 	ADDWORD(frm, prep->prep_targetseq);
741 	if (prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE) {
742 		IEEE80211_ADDR_COPY(frm, prep->prep_target_ext_addr);
743 		frm += 6;
744 	}
745 	ADDWORD(frm, prep->prep_lifetime);
746 	ADDWORD(frm, prep->prep_metric);
747 	IEEE80211_ADDR_COPY(frm, prep->prep_origaddr); frm += 6;
748 	ADDWORD(frm, prep->prep_origseq);
749 	return frm;
750 }
751 
752 /*
753  * Add a Mesh Path Error IE to a frame.
754  */
755 #define	PERR_DFLAGS(n)	perr->perr_dests[n].dest_flags
756 #define	PERR_DADDR(n)	perr->perr_dests[n].dest_addr
757 #define	PERR_DSEQ(n)	perr->perr_dests[n].dest_seq
758 #define	PERR_EXTADDR(n)	perr->perr_dests[n].dest_ext_addr
759 #define	PERR_DRCODE(n)	perr->perr_dests[n].dest_rcode
760 static uint8_t *
761 hwmp_add_meshperr(uint8_t *frm, const struct ieee80211_meshperr_ie *perr)
762 {
763 	int i;
764 
765 	*frm++ = IEEE80211_ELEMID_MESHPERR;
766 	*frm++ = perr->perr_len;	/* len already calculated */
767 	*frm++ = perr->perr_ttl;
768 	*frm++ = perr->perr_ndests;
769 	for (i = 0; i < perr->perr_ndests; i++) {
770 		*frm++ = PERR_DFLAGS(i);
771 		IEEE80211_ADDR_COPY(frm, PERR_DADDR(i));
772 		frm += 6;
773 		ADDWORD(frm, PERR_DSEQ(i));
774 		if (PERR_DFLAGS(i) & IEEE80211_MESHPERR_FLAGS_AE) {
775 			IEEE80211_ADDR_COPY(frm, PERR_EXTADDR(i));
776 			frm += 6;
777 		}
778 		ADDSHORT(frm, PERR_DRCODE(i));
779 	}
780 	return frm;
781 }
782 #undef	PERR_DFLAGS
783 #undef	PERR_DADDR
784 #undef	PERR_DSEQ
785 #undef	PERR_EXTADDR
786 #undef	PERR_DRCODE
787 
788 /*
789  * Add a Root Annoucement IE to a frame.
790  */
791 static uint8_t *
792 hwmp_add_meshrann(uint8_t *frm, const struct ieee80211_meshrann_ie *rann)
793 {
794 	*frm++ = IEEE80211_ELEMID_MESHRANN;
795 	*frm++ = rann->rann_len;
796 	*frm++ = rann->rann_flags;
797 	*frm++ = rann->rann_hopcount;
798 	*frm++ = rann->rann_ttl;
799 	IEEE80211_ADDR_COPY(frm, rann->rann_addr); frm += 6;
800 	ADDWORD(frm, rann->rann_seq);
801 	ADDWORD(frm, rann->rann_interval);
802 	ADDWORD(frm, rann->rann_metric);
803 	return frm;
804 }
805 
806 static void
807 hwmp_rootmode_setup(struct ieee80211vap *vap)
808 {
809 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
810 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
811 
812 	switch (hs->hs_rootmode) {
813 	case IEEE80211_HWMP_ROOTMODE_DISABLED:
814 		callout_drain(&hs->hs_roottimer);
815 		ms->ms_flags &= ~IEEE80211_MESHFLAGS_ROOT;
816 		break;
817 	case IEEE80211_HWMP_ROOTMODE_NORMAL:
818 	case IEEE80211_HWMP_ROOTMODE_PROACTIVE:
819 		callout_reset(&hs->hs_roottimer, ieee80211_hwmp_rootint,
820 		    hwmp_rootmode_cb, vap);
821 		ms->ms_flags |= IEEE80211_MESHFLAGS_ROOT;
822 		break;
823 	case IEEE80211_HWMP_ROOTMODE_RANN:
824 		callout_reset(&hs->hs_roottimer, ieee80211_hwmp_rannint,
825 		    hwmp_rootmode_rann_cb, vap);
826 		ms->ms_flags |= IEEE80211_MESHFLAGS_ROOT;
827 		break;
828 	}
829 }
830 
831 /*
832  * Send a broadcast Path Request to find all nodes on the mesh. We are
833  * called when the vap is configured as a HWMP root node.
834  */
835 #define	PREQ_TFLAGS(n)	preq.preq_targets[n].target_flags
836 #define	PREQ_TADDR(n)	preq.preq_targets[n].target_addr
837 #define	PREQ_TSEQ(n)	preq.preq_targets[n].target_seq
838 static void
839 hwmp_rootmode_cb(void *arg)
840 {
841 	struct ieee80211vap *vap = (struct ieee80211vap *)arg;
842 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
843 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
844 	struct ieee80211_meshpreq_ie preq;
845 
846 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, vap->iv_bss,
847 	    "%s", "send broadcast PREQ");
848 
849 	preq.preq_flags = 0;
850 	if (ms->ms_flags & IEEE80211_MESHFLAGS_GATE)
851 		preq.preq_flags |= IEEE80211_MESHPREQ_FLAGS_GATE;
852 	if (hs->hs_rootmode == IEEE80211_HWMP_ROOTMODE_PROACTIVE)
853 		preq.preq_flags |= IEEE80211_MESHPREQ_FLAGS_PP;
854 	preq.preq_hopcount = 0;
855 	preq.preq_ttl = ms->ms_ttl;
856 	preq.preq_id = ++hs->hs_preqid;
857 	IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
858 	preq.preq_origseq = ++hs->hs_seq;
859 	preq.preq_lifetime = ticks_to_msecs(ieee80211_hwmp_roottimeout);
860 	preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
861 	preq.preq_tcount = 1;
862 	IEEE80211_ADDR_COPY(PREQ_TADDR(0), broadcastaddr);
863 	PREQ_TFLAGS(0) = IEEE80211_MESHPREQ_TFLAGS_TO |
864 	    IEEE80211_MESHPREQ_TFLAGS_USN;
865 	PREQ_TSEQ(0) = 0;
866 	vap->iv_stats.is_hwmp_rootreqs++;
867 	/* NB: we enforce rate check ourself */
868 	hwmp_send_preq(vap, broadcastaddr, &preq, NULL, NULL);
869 	hwmp_rootmode_setup(vap);
870 }
871 #undef	PREQ_TFLAGS
872 #undef	PREQ_TADDR
873 #undef	PREQ_TSEQ
874 
875 /*
876  * Send a Root Annoucement (RANN) to find all the nodes on the mesh. We are
877  * called when the vap is configured as a HWMP RANN root node.
878  */
879 static void
880 hwmp_rootmode_rann_cb(void *arg)
881 {
882 	struct ieee80211vap *vap = (struct ieee80211vap *)arg;
883 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
884 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
885 	struct ieee80211_meshrann_ie rann;
886 
887 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, vap->iv_bss,
888 	    "%s", "send broadcast RANN");
889 
890 	rann.rann_flags = 0;
891 	if (ms->ms_flags & IEEE80211_MESHFLAGS_GATE)
892 		rann.rann_flags |= IEEE80211_MESHFLAGS_GATE;
893 	rann.rann_hopcount = 0;
894 	rann.rann_ttl = ms->ms_ttl;
895 	IEEE80211_ADDR_COPY(rann.rann_addr, vap->iv_myaddr);
896 	rann.rann_seq = ++hs->hs_seq;
897 	rann.rann_interval = ieee80211_hwmp_rannint;
898 	rann.rann_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
899 
900 	vap->iv_stats.is_hwmp_rootrann++;
901 	hwmp_send_rann(vap, broadcastaddr, &rann);
902 	hwmp_rootmode_setup(vap);
903 }
904 
905 /*
906  * Update forwarding information to TA if metric improves.
907  */
908 static void
909 hwmp_update_transmitter(struct ieee80211vap *vap, struct ieee80211_node *ni,
910     const char *hwmp_frame)
911 {
912 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
913 	struct ieee80211_mesh_route *rttran = NULL;	/* Transmitter */
914 	int metric = 0;
915 
916 	rttran = ieee80211_mesh_rt_find(vap, ni->ni_macaddr);
917 	if (rttran == NULL) {
918 		rttran = ieee80211_mesh_rt_add(vap, ni->ni_macaddr);
919 		if (rttran == NULL) {
920 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
921 			    "unable to add path to transmitter %6D of %s",
922 			    ni->ni_macaddr, ":", hwmp_frame);
923 			vap->iv_stats.is_mesh_rtaddfailed++;
924 			return;
925 		}
926 	}
927 	metric = ms->ms_pmetric->mpm_metric(ni);
928 	if (!(rttran->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) ||
929 	    rttran->rt_metric > metric)
930 	{
931 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
932 		    "%s path to transmiter %6D of %s, metric %d:%d",
933 		    rttran->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
934 		    "prefer" : "update", ni->ni_macaddr, ":", hwmp_frame,
935 		    rttran->rt_metric, metric);
936 		IEEE80211_ADDR_COPY(rttran->rt_nexthop, ni->ni_macaddr);
937 		rttran->rt_metric = metric;
938 		rttran->rt_nhops  = 1;
939 		ieee80211_mesh_rt_update(rttran, ms->ms_ppath->mpp_inact);
940 		rttran->rt_flags = IEEE80211_MESHRT_FLAGS_VALID;
941 	}
942 }
943 
944 #define	PREQ_TFLAGS(n)	preq->preq_targets[n].target_flags
945 #define	PREQ_TADDR(n)	preq->preq_targets[n].target_addr
946 #define	PREQ_TSEQ(n)	preq->preq_targets[n].target_seq
947 static void
948 hwmp_recv_preq(struct ieee80211vap *vap, struct ieee80211_node *ni,
949     const struct ieee80211_frame *wh, const struct ieee80211_meshpreq_ie *preq)
950 {
951 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
952 	struct ieee80211_mesh_route *rtorig = NULL;
953 	struct ieee80211_mesh_route *rtorig_ext = NULL;
954 	struct ieee80211_mesh_route *rttarg = NULL;
955 	struct ieee80211_hwmp_route *hrorig = NULL;
956 	struct ieee80211_hwmp_route *hrtarg = NULL;
957 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
958 	struct ieee80211_meshprep_ie prep;
959 	ieee80211_hwmp_seq preqid;	/* last seen preqid for orig */
960 	uint32_t metric = 0;
961 
962 	/*
963 	 * Ignore PREQs from us. Could happen because someone forward it
964 	 * back to us.
965 	 */
966 	if (IEEE80211_ADDR_EQ(vap->iv_myaddr, preq->preq_origaddr))
967 		return;
968 
969 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
970 	    "received PREQ, orig %6D, targ(0) %6D", preq->preq_origaddr, ":",
971 	    PREQ_TADDR(0), ":");
972 
973 	/*
974 	 * Acceptance criteria: (if the PREQ is not for us or not broadcast,
975 	 * or an external mac address not proxied by us),
976 	 * AND forwarding is disabled, discard this PREQ.
977 	 */
978 	rttarg = ieee80211_mesh_rt_find(vap, PREQ_TADDR(0));
979 	if (!(ms->ms_flags & IEEE80211_MESHFLAGS_FWD) &&
980 	    (!IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0)) ||
981 	    !IEEE80211_IS_MULTICAST(PREQ_TADDR(0)) ||
982 	    (rttarg != NULL &&
983 	    rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY &&
984 	    IEEE80211_ADDR_EQ(vap->iv_myaddr, rttarg->rt_mesh_gate)))) {
985 		IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
986 		    preq->preq_origaddr, NULL, "%s", "not accepting PREQ");
987 		return;
988 	}
989 	/*
990 	 * Acceptance criteria: if unicast addressed
991 	 * AND no valid forwarding for Target of PREQ, discard this PREQ.
992 	 */
993 	if(rttarg != NULL)
994 		hrtarg = IEEE80211_MESH_ROUTE_PRIV(rttarg,
995 		    struct ieee80211_hwmp_route);
996 	/* Address mode: ucast */
997 	if(preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AM &&
998 	    rttarg == NULL &&
999 	    !IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0))) {
1000 		IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
1001 		    preq->preq_origaddr, NULL,
1002 		    "unicast addressed PREQ of unknown target %6D",
1003 		    PREQ_TADDR(0), ":");
1004 		return;
1005 	}
1006 
1007 	/* PREQ ACCEPTED */
1008 
1009 	rtorig = ieee80211_mesh_rt_find(vap, preq->preq_origaddr);
1010 	if (rtorig == NULL) {
1011 		rtorig = ieee80211_mesh_rt_add(vap, preq->preq_origaddr);
1012 		if (rtorig == NULL) {
1013 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1014 			    "unable to add orig path to %6D",
1015 			    preq->preq_origaddr, ":");
1016 			vap->iv_stats.is_mesh_rtaddfailed++;
1017 			return;
1018 		}
1019 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1020 		    "adding originator %6D", preq->preq_origaddr, ":");
1021 	}
1022 	hrorig = IEEE80211_MESH_ROUTE_PRIV(rtorig, struct ieee80211_hwmp_route);
1023 
1024 	/* record last seen preqid */
1025 	preqid = hrorig->hr_preqid;
1026 	hrorig->hr_preqid = HWMP_SEQ_MAX(hrorig->hr_preqid, preq->preq_id);
1027 
1028 	/* Data creation and update of forwarding information
1029 	 * according to Table 11C-8 for originator mesh STA.
1030 	 */
1031 	metric = preq->preq_metric + ms->ms_pmetric->mpm_metric(ni);
1032 	if (HWMP_SEQ_GT(preq->preq_origseq, hrorig->hr_seq) ||
1033 	    (HWMP_SEQ_EQ(preq->preq_origseq, hrorig->hr_seq) &&
1034 	    metric < rtorig->rt_metric)) {
1035 		hrorig->hr_seq = preq->preq_origseq;
1036 		IEEE80211_ADDR_COPY(rtorig->rt_nexthop, wh->i_addr2);
1037 		rtorig->rt_metric = metric;
1038 		rtorig->rt_nhops  = preq->preq_hopcount + 1;
1039 		ieee80211_mesh_rt_update(rtorig, preq->preq_lifetime);
1040 		/* Path to orig is valid now.
1041 		 * NB: we know it can't be Proxy, and if it is GATE
1042 		 * it will be marked below.
1043 		 */
1044 		rtorig->rt_flags = IEEE80211_MESHRT_FLAGS_VALID;
1045 	} else if ((hrtarg != NULL &&
1046 	    !HWMP_SEQ_EQ(hrtarg->hr_seq, PREQ_TSEQ(0))) ||
1047 	    (rtorig->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1048 	    preqid >= preq->preq_id)) {
1049 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1050 		    "discard PREQ from %6D, old seqno %u <= %u,"
1051 		    " or old preqid %u < %u",
1052 		    preq->preq_origaddr, ":",
1053 		    preq->preq_origseq, hrorig->hr_seq,
1054 		    preq->preq_id, preqid);
1055 		return;
1056 	}
1057 
1058 	/* Update forwarding information to TA if metric improves. */
1059 	hwmp_update_transmitter(vap, ni, "PREQ");
1060 
1061 	/*
1062 	 * Check if the PREQ is addressed to us.
1063 	 * or a Proxy currently gated by us.
1064 	 */
1065 	if (IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0)) ||
1066 	    (ms->ms_flags & IEEE80211_MESHFLAGS_GATE &&
1067 	    rttarg != NULL &&
1068 	    IEEE80211_ADDR_EQ(vap->iv_myaddr, rttarg->rt_mesh_gate) &&
1069 	    rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY &&
1070 	    rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)) {
1071 		/*
1072 		 * When we are the target we shall update our own HWMP seq
1073 		 * number with max of (current and preq->seq) + 1
1074 		 */
1075 		hs->hs_seq = HWMP_SEQ_MAX(hs->hs_seq, PREQ_TSEQ(0)) + 1;
1076 
1077 		prep.prep_flags = 0;
1078 		prep.prep_hopcount = 0;
1079 		prep.prep_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1080 		IEEE80211_ADDR_COPY(prep.prep_targetaddr, vap->iv_myaddr);
1081 		if (rttarg != NULL && /* if NULL it means we are the target */
1082 		    rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY) {
1083 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1084 			    "reply for proxy %6D", rttarg->rt_dest, ":");
1085 			prep.prep_flags |= IEEE80211_MESHPREP_FLAGS_AE;
1086 			IEEE80211_ADDR_COPY(prep.prep_target_ext_addr,
1087 			    rttarg->rt_dest);
1088 			/* update proxy seqno to HWMP seqno */
1089 			rttarg->rt_ext_seq = hs->hs_seq;
1090 			prep.prep_hopcount = rttarg->rt_nhops;
1091 			prep.prep_metric = rttarg->rt_metric;
1092 			IEEE80211_ADDR_COPY(prep.prep_targetaddr, rttarg->rt_mesh_gate);
1093 		}
1094 		/*
1095 		 * Build and send a PREP frame.
1096 		 */
1097 		prep.prep_ttl = ms->ms_ttl;
1098 		prep.prep_targetseq = hs->hs_seq;
1099 		prep.prep_lifetime = preq->preq_lifetime;
1100 		IEEE80211_ADDR_COPY(prep.prep_origaddr, preq->preq_origaddr);
1101 		prep.prep_origseq = preq->preq_origseq;
1102 
1103 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1104 		    "reply to %6D", preq->preq_origaddr, ":");
1105 		hwmp_send_prep(vap, wh->i_addr2, &prep);
1106 		return;
1107 	}
1108 	/* we may update our proxy information for the orig external */
1109 	else if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE) {
1110 		rtorig_ext =
1111 		    ieee80211_mesh_rt_find(vap, preq->preq_orig_ext_addr);
1112 		if (rtorig_ext == NULL) {
1113 			rtorig_ext = ieee80211_mesh_rt_add(vap,
1114 			    preq->preq_orig_ext_addr);
1115 			if (rtorig_ext == NULL) {
1116 				IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1117 				    "unable to add orig ext proxy to %6D",
1118 				    preq->preq_orig_ext_addr, ":");
1119 				vap->iv_stats.is_mesh_rtaddfailed++;
1120 				return;
1121 			}
1122 			IEEE80211_ADDR_COPY(rtorig_ext->rt_mesh_gate,
1123 			    preq->preq_origaddr);
1124 		}
1125 		rtorig_ext->rt_ext_seq = preq->preq_origseq;
1126 		ieee80211_mesh_rt_update(rtorig_ext, preq->preq_lifetime);
1127 	}
1128 	/*
1129 	 * Proactive PREQ: reply with a proactive PREP to the
1130 	 * root STA if requested.
1131 	 */
1132 	if (IEEE80211_ADDR_EQ(PREQ_TADDR(0), broadcastaddr) &&
1133 	    (PREQ_TFLAGS(0) & IEEE80211_MESHPREQ_TFLAGS_TO)) {
1134 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1135 		    "root mesh station @ %6D", preq->preq_origaddr, ":");
1136 
1137 		/* Check if root is a mesh gate, mark it */
1138 		if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_GATE) {
1139 			struct ieee80211_mesh_gate_route *gr;
1140 
1141 			rtorig->rt_flags |= IEEE80211_MESHRT_FLAGS_GATE;
1142 			gr = ieee80211_mesh_mark_gate(vap, preq->preq_origaddr,
1143 			    rtorig);
1144 			gr->gr_lastseq = 0; /* NOT GANN */
1145 		}
1146 
1147 		/*
1148 		 * Reply with a PREP if we don't have a path to the root
1149 		 * or if the root sent us a proactive PREQ.
1150 		 */
1151 		if ((rtorig->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) == 0 ||
1152 		    (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_PP)) {
1153 			prep.prep_flags = 0;
1154 			prep.prep_hopcount = 0;
1155 			prep.prep_ttl = ms->ms_ttl;
1156 			IEEE80211_ADDR_COPY(prep.prep_origaddr,
1157 			    preq->preq_origaddr);
1158 			prep.prep_origseq = preq->preq_origseq;
1159 			prep.prep_lifetime = preq->preq_lifetime;
1160 			prep.prep_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1161 			IEEE80211_ADDR_COPY(prep.prep_targetaddr,
1162 			    vap->iv_myaddr);
1163 			prep.prep_targetseq = ++hs->hs_seq;
1164 			hwmp_send_prep(vap, rtorig->rt_nexthop, &prep);
1165 		}
1166 	}
1167 
1168 	/*
1169 	 * Forwarding and Intermediate reply for PREQs with 1 target.
1170 	 */
1171 	if ((preq->preq_tcount == 1) && (preq->preq_ttl > 1) &&
1172 	    (ms->ms_flags & IEEE80211_MESHFLAGS_FWD)) {
1173 		struct ieee80211_meshpreq_ie ppreq; /* propagated PREQ */
1174 
1175 		memcpy(&ppreq, preq, sizeof(ppreq));
1176 
1177 		/*
1178 		 * We have a valid route to this node.
1179 		 * NB: if target is proxy dont reply.
1180 		 */
1181 		if (rttarg != NULL &&
1182 		    rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1183 		    !(rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY)) {
1184 			/*
1185 			 * Check if we can send an intermediate Path Reply,
1186 			 * i.e., Target Only bit is not set and target is not
1187 			 * the MAC broadcast address.
1188 			 */
1189 			if (!(PREQ_TFLAGS(0) & IEEE80211_MESHPREQ_TFLAGS_TO) &&
1190 			    !IEEE80211_ADDR_EQ(PREQ_TADDR(0), broadcastaddr)) {
1191 				struct ieee80211_meshprep_ie prep;
1192 
1193 				IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1194 				    "intermediate reply for PREQ from %6D",
1195 				    preq->preq_origaddr, ":");
1196 				prep.prep_flags = 0;
1197 				prep.prep_hopcount = rttarg->rt_nhops;
1198 				prep.prep_ttl = ms->ms_ttl;
1199 				IEEE80211_ADDR_COPY(&prep.prep_targetaddr,
1200 				    PREQ_TADDR(0));
1201 				prep.prep_targetseq = hrtarg->hr_seq;
1202 				prep.prep_lifetime = preq->preq_lifetime;
1203 				prep.prep_metric =rttarg->rt_metric;
1204 				IEEE80211_ADDR_COPY(&prep.prep_origaddr,
1205 				    preq->preq_origaddr);
1206 				prep.prep_origseq = hrorig->hr_seq;
1207 				hwmp_send_prep(vap, rtorig->rt_nexthop, &prep);
1208 
1209 				/*
1210 				 * Set TO and unset RF bits because we have
1211 				 * sent a PREP.
1212 				 */
1213 				ppreq.preq_targets[0].target_flags |=
1214 				    IEEE80211_MESHPREQ_TFLAGS_TO;
1215 			}
1216 		}
1217 
1218 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1219 		    "forward PREQ from %6D",
1220 		    preq->preq_origaddr, ":");
1221 		ppreq.preq_hopcount += 1;
1222 		ppreq.preq_ttl -= 1;
1223 		ppreq.preq_metric += ms->ms_pmetric->mpm_metric(ni);
1224 
1225 		/* don't do PREQ ratecheck when we propagate */
1226 		hwmp_send_preq(vap, broadcastaddr, &ppreq, NULL, NULL);
1227 	}
1228 }
1229 #undef	PREQ_TFLAGS
1230 #undef	PREQ_TADDR
1231 #undef	PREQ_TSEQ
1232 
1233 static int
1234 hwmp_send_preq(struct ieee80211vap *vap,
1235     const uint8_t da[IEEE80211_ADDR_LEN],
1236     struct ieee80211_meshpreq_ie *preq,
1237     struct timeval *last, struct timeval *minint)
1238 {
1239 
1240 	/*
1241 	 * Enforce PREQ interval.
1242 	 * NB: Proactive ROOT PREQs rate is handled by cb task.
1243 	 */
1244 	if (last != NULL && minint != NULL) {
1245 		if (ratecheck(last, minint) == 0)
1246 			return EALREADY; /* XXX: we should postpone */
1247 		getmicrouptime(last);
1248 	}
1249 
1250 	/*
1251 	 * mesh preq action frame format
1252 	 *     [6] da
1253 	 *     [6] sa
1254 	 *     [6] addr3 = sa
1255 	 *     [1] action
1256 	 *     [1] category
1257 	 *     [tlv] mesh path request
1258 	 */
1259 	preq->preq_ie = IEEE80211_ELEMID_MESHPREQ;
1260 	preq->preq_len = (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE ?
1261 	    IEEE80211_MESHPREQ_BASE_SZ_AE : IEEE80211_MESHPREQ_BASE_SZ) +
1262 	    preq->preq_tcount * IEEE80211_MESHPREQ_TRGT_SZ;
1263 	return hwmp_send_action(vap, da, (uint8_t *)preq, preq->preq_len+2);
1264 }
1265 
1266 static void
1267 hwmp_recv_prep(struct ieee80211vap *vap, struct ieee80211_node *ni,
1268     const struct ieee80211_frame *wh, const struct ieee80211_meshprep_ie *prep)
1269 {
1270 #define	IS_PROXY(rt)	(rt->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY)
1271 #define	PROXIED_BY_US(rt)		\
1272     (IEEE80211_ADDR_EQ(vap->iv_myaddr, rt->rt_mesh_gate))
1273 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1274 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1275 	struct ieee80211_mesh_route *rt = NULL;
1276 	struct ieee80211_mesh_route *rtorig = NULL;
1277 	struct ieee80211_mesh_route *rtext = NULL;
1278 	struct ieee80211_hwmp_route *hr;
1279 	struct ieee80211com *ic = vap->iv_ic;
1280 	struct mbuf *m, *next;
1281 	uint32_t metric = 0;
1282 	const uint8_t *addr;
1283 
1284 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1285 	    "received PREP, orig %6D, targ %6D", prep->prep_origaddr, ":",
1286 	    prep->prep_targetaddr, ":");
1287 
1288 	/*
1289 	 * Acceptance criteria: (If the corresponding PREP was not generated
1290 	 * by us OR not generated by an external mac that is not proxied by us)
1291 	 * AND forwarding is disabled, discard this PREP.
1292 	 */
1293 	rtorig = ieee80211_mesh_rt_find(vap, prep->prep_origaddr);
1294 	if ((!IEEE80211_ADDR_EQ(vap->iv_myaddr, prep->prep_origaddr) ||
1295 	    (rtorig != NULL && IS_PROXY(rtorig) && !PROXIED_BY_US(rtorig))) &&
1296 	    !(ms->ms_flags & IEEE80211_MESHFLAGS_FWD)){
1297 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1298 		    "discard PREP, orig(%6D) not proxied or generated by us",
1299 		    prep->prep_origaddr, ":");
1300 		return;
1301 	}
1302 
1303 	/* PREP ACCEPTED */
1304 
1305 	/*
1306 	 * If accepted shall create or update the active forwarding information
1307 	 * it maintains for the target mesh STA of the PREP (according to the
1308 	 * rules defined in 13.10.8.4). If the conditions for creating or
1309 	 * updating the forwarding information have not been met in those
1310 	 * rules, no further steps are applied to the PREP.
1311 	 */
1312 	rt = ieee80211_mesh_rt_find(vap, prep->prep_targetaddr);
1313 	if (rt == NULL) {
1314 		rt = ieee80211_mesh_rt_add(vap, prep->prep_targetaddr);
1315 		if (rt == NULL) {
1316 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1317 			    "unable to add PREP path to %6D",
1318 			    prep->prep_targetaddr, ":");
1319 			vap->iv_stats.is_mesh_rtaddfailed++;
1320 			return;
1321 		}
1322 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1323 		    "adding target %6D", prep->prep_targetaddr, ":");
1324 	}
1325 	hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1326 	/* update path metric */
1327 	metric = prep->prep_metric + ms->ms_pmetric->mpm_metric(ni);
1328 	if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)) {
1329 		if (HWMP_SEQ_LT(prep->prep_targetseq, hr->hr_seq)) {
1330 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1331 			    "discard PREP from %6D, old seq no %u < %u",
1332 			    prep->prep_targetaddr, ":",
1333 			    prep->prep_targetseq, hr->hr_seq);
1334 			return;
1335 		} else if (HWMP_SEQ_LEQ(prep->prep_targetseq, hr->hr_seq) &&
1336 		    metric > rt->rt_metric) {
1337 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1338 			    "discard PREP from %6D, new metric %u > %u",
1339 			    prep->prep_targetaddr, ":",
1340 			    metric, rt->rt_metric);
1341 			return;
1342 		}
1343 	}
1344 
1345 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1346 	    "%s path to %6D, hopcount %d:%d metric %d:%d",
1347 	    rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
1348 	    "prefer" : "update",
1349 	    prep->prep_targetaddr, ":",
1350 	    rt->rt_nhops, prep->prep_hopcount + 1,
1351 	    rt->rt_metric, metric);
1352 
1353 	hr->hr_seq = prep->prep_targetseq;
1354 	hr->hr_preqretries = 0;
1355 	IEEE80211_ADDR_COPY(rt->rt_nexthop, ni->ni_macaddr);
1356 	rt->rt_metric = metric;
1357 	rt->rt_nhops = prep->prep_hopcount + 1;
1358 	ieee80211_mesh_rt_update(rt, prep->prep_lifetime);
1359 	if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_DISCOVER) {
1360 		/* discovery complete */
1361 		rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_DISCOVER;
1362 	}
1363 	rt->rt_flags |= IEEE80211_MESHRT_FLAGS_VALID; /* mark valid */
1364 
1365 	/* Update forwarding information to TA if metric improves */
1366 	hwmp_update_transmitter(vap, ni, "PREP");
1367 
1368 	/*
1369 	 * If it's NOT for us, propagate the PREP
1370 	 */
1371 	if (!IEEE80211_ADDR_EQ(vap->iv_myaddr, prep->prep_origaddr) &&
1372 	    prep->prep_ttl > 1 &&
1373 	    prep->prep_hopcount < hs->hs_maxhops) {
1374 		struct ieee80211_meshprep_ie pprep; /* propagated PREP */
1375 		/*
1376 		 * NB: We should already have setup the path to orig
1377 		 * mesh STA when we propagated PREQ to target mesh STA,
1378 		 * no PREP is generated without a corresponding PREQ.
1379 		 * XXX: for now just ignore.
1380 		 */
1381 		if (rtorig == NULL) {
1382 			IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1383 			    "received PREP for an unknown orig(%6D)",
1384 			    prep->prep_origaddr, ":");
1385 			return;
1386 		}
1387 
1388 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1389 		    "propagate PREP from %6D",
1390 		    prep->prep_targetaddr, ":");
1391 
1392 		memcpy(&pprep, prep, sizeof(pprep));
1393 		pprep.prep_hopcount += 1;
1394 		pprep.prep_ttl -= 1;
1395 		pprep.prep_metric += ms->ms_pmetric->mpm_metric(ni);
1396 		hwmp_send_prep(vap, rtorig->rt_nexthop, &pprep);
1397 
1398 		/* precursor list for the Target Mesh STA Address is updated */
1399 	}
1400 
1401 	/*
1402 	 * Check if we received a PREP w/ AE and store target external address.
1403 	 * We may store target external address if recevied PREP w/ AE
1404 	 * and we are not final destination
1405 	 */
1406 	if (prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE) {
1407 		rtext = ieee80211_mesh_rt_find(vap,
1408 			prep->prep_target_ext_addr);
1409 		if (rtext == NULL) {
1410 			rtext = ieee80211_mesh_rt_add(vap,
1411 				prep->prep_target_ext_addr);
1412 			if (rtext == NULL) {
1413 				IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1414 				    "unable to add PREP path to proxy %6D",
1415 				    prep->prep_targetaddr, ":");
1416 				vap->iv_stats.is_mesh_rtaddfailed++;
1417 				return;
1418 			}
1419 		}
1420 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1421 		    "%s path to %6D, hopcount %d:%d metric %d:%d",
1422 		    rtext->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
1423 		    "prefer" : "update",
1424 		    prep->prep_target_ext_addr, ":",
1425 		    rtext->rt_nhops, prep->prep_hopcount + 1,
1426 		    rtext->rt_metric, metric);
1427 
1428 		rtext->rt_flags = IEEE80211_MESHRT_FLAGS_PROXY |
1429 			IEEE80211_MESHRT_FLAGS_VALID;
1430 		IEEE80211_ADDR_COPY(rtext->rt_dest,
1431 		    prep->prep_target_ext_addr);
1432 		IEEE80211_ADDR_COPY(rtext->rt_mesh_gate,
1433 		    prep->prep_targetaddr);
1434 		IEEE80211_ADDR_COPY(rtext->rt_nexthop, wh->i_addr2);
1435 		rtext->rt_metric = metric;
1436 		rtext->rt_lifetime = prep->prep_lifetime;
1437 		rtext->rt_nhops = prep->prep_hopcount + 1;
1438 		rtext->rt_ext_seq = prep->prep_origseq; /* new proxy seq */
1439 		/*
1440 		 * XXX: proxy entries have no HWMP priv data,
1441 		 * nullify them to be sure?
1442 		 */
1443 	}
1444 	/*
1445 	 * Check for frames queued awaiting path discovery.
1446 	 * XXX probably can tell exactly and avoid remove call
1447 	 * NB: hash may have false matches, if so they will get
1448 	 *     stuck back on the stageq because there won't be
1449 	 *     a path.
1450 	 */
1451 	addr = prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE ?
1452 	    prep->prep_target_ext_addr : prep->prep_targetaddr;
1453 	m = ieee80211_ageq_remove(&ic->ic_stageq,
1454 	    (struct ieee80211_node *)(uintptr_t)
1455 	    ieee80211_mac_hash(ic, addr)); /* either dest or ext_dest */
1456 
1457 	/*
1458 	 * All frames in the stageq here should be non-M_ENCAP; or things
1459 	 * will get very unhappy.
1460 	 */
1461 	for (; m != NULL; m = next) {
1462 		next = m->m_nextpkt;
1463 		m->m_nextpkt = NULL;
1464 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1465 		    "flush queued frame %p len %d", m, m->m_pkthdr.len);
1466 		/*
1467 		 * If the mbuf has M_ENCAP set, ensure we free it.
1468 		 * Note that after if_transmit() is called, m is invalid.
1469 		 */
1470 		(void) ieee80211_vap_xmitpkt(vap, m);
1471 	}
1472 #undef	IS_PROXY
1473 #undef	PROXIED_BY_US
1474 }
1475 
1476 static int
1477 hwmp_send_prep(struct ieee80211vap *vap,
1478     const uint8_t da[IEEE80211_ADDR_LEN],
1479     struct ieee80211_meshprep_ie *prep)
1480 {
1481 	/* NB: there's no PREP minimum interval. */
1482 
1483 	/*
1484 	 * mesh prep action frame format
1485 	 *     [6] da
1486 	 *     [6] sa
1487 	 *     [6] addr3 = sa
1488 	 *     [1] action
1489 	 *     [1] category
1490 	 *     [tlv] mesh path reply
1491 	 */
1492 	prep->prep_ie = IEEE80211_ELEMID_MESHPREP;
1493 	prep->prep_len = prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE ?
1494 	    IEEE80211_MESHPREP_BASE_SZ_AE : IEEE80211_MESHPREP_BASE_SZ;
1495 	return hwmp_send_action(vap, da, (uint8_t *)prep, prep->prep_len + 2);
1496 }
1497 
1498 #define	PERR_DFLAGS(n)	perr.perr_dests[n].dest_flags
1499 #define	PERR_DADDR(n)	perr.perr_dests[n].dest_addr
1500 #define	PERR_DSEQ(n)	perr.perr_dests[n].dest_seq
1501 #define	PERR_DRCODE(n)	perr.perr_dests[n].dest_rcode
1502 static void
1503 hwmp_peerdown(struct ieee80211_node *ni)
1504 {
1505 	struct ieee80211vap *vap = ni->ni_vap;
1506 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1507 	struct ieee80211_meshperr_ie perr;
1508 	struct ieee80211_mesh_route *rt;
1509 	struct ieee80211_hwmp_route *hr;
1510 
1511 	rt = ieee80211_mesh_rt_find(vap, ni->ni_macaddr);
1512 	if (rt == NULL)
1513 		return;
1514 	hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1515 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1516 	    "%s", "delete route entry");
1517 	perr.perr_ttl = ms->ms_ttl;
1518 	perr.perr_ndests = 1;
1519 	PERR_DFLAGS(0) = 0;
1520 	if (hr->hr_seq == 0)
1521 		PERR_DFLAGS(0) |= IEEE80211_MESHPERR_DFLAGS_USN;
1522 	PERR_DFLAGS(0) |= IEEE80211_MESHPERR_DFLAGS_RC;
1523 	IEEE80211_ADDR_COPY(PERR_DADDR(0), rt->rt_dest);
1524 	PERR_DSEQ(0) = ++hr->hr_seq;
1525 	PERR_DRCODE(0) = IEEE80211_REASON_MESH_PERR_DEST_UNREACH;
1526 	/* NB: flush everything passing through peer */
1527 	ieee80211_mesh_rt_flush_peer(vap, ni->ni_macaddr);
1528 	hwmp_send_perr(vap, broadcastaddr, &perr);
1529 }
1530 #undef	PERR_DFLAGS
1531 #undef	PERR_DADDR
1532 #undef	PERR_DSEQ
1533 #undef	PERR_DRCODE
1534 
1535 #define	PERR_DFLAGS(n)		perr->perr_dests[n].dest_flags
1536 #define	PERR_DADDR(n)		perr->perr_dests[n].dest_addr
1537 #define	PERR_DSEQ(n)		perr->perr_dests[n].dest_seq
1538 #define	PERR_DEXTADDR(n)	perr->perr_dests[n].dest_ext_addr
1539 #define	PERR_DRCODE(n)		perr->perr_dests[n].dest_rcode
1540 static void
1541 hwmp_recv_perr(struct ieee80211vap *vap, struct ieee80211_node *ni,
1542     const struct ieee80211_frame *wh, const struct ieee80211_meshperr_ie *perr)
1543 {
1544 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1545 	struct ieee80211_mesh_route *rt = NULL;
1546 	struct ieee80211_mesh_route *rt_ext = NULL;
1547 	struct ieee80211_hwmp_route *hr;
1548 	struct ieee80211_meshperr_ie *pperr = NULL;
1549 	int i, j = 0, forward = 0;
1550 
1551 	IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1552 	    "received PERR from %6D", wh->i_addr2, ":");
1553 
1554 	/*
1555 	 * if forwarding is true, prepare pperr
1556 	 */
1557 	if (ms->ms_flags & IEEE80211_MESHFLAGS_FWD) {
1558 		forward = 1;
1559 		pperr = malloc(sizeof(*perr) + 31*sizeof(*perr->perr_dests),
1560 		    M_80211_MESH_PERR, M_NOWAIT); /* XXX: magic number, 32 err dests */
1561 	}
1562 
1563 	/*
1564 	 * Acceptance criteria: check if we have forwarding information
1565 	 * stored about destination, and that nexthop == TA of this PERR.
1566 	 * NB: we also build a new PERR to propagate in case we should forward.
1567 	 */
1568 	for (i = 0; i < perr->perr_ndests; i++) {
1569 		rt = ieee80211_mesh_rt_find(vap, PERR_DADDR(i));
1570 		if (rt == NULL)
1571 			continue;
1572 		if (!IEEE80211_ADDR_EQ(rt->rt_nexthop, wh->i_addr2))
1573 			continue;
1574 
1575 		/* found and accepted a PERR ndest element, process it... */
1576 		if (forward)
1577 			memcpy(&pperr->perr_dests[j], &perr->perr_dests[i],
1578 			    sizeof(*perr->perr_dests));
1579 		hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1580 		switch(PERR_DFLAGS(i)) {
1581 		case (IEEE80211_REASON_MESH_PERR_NO_FI):
1582 			if (PERR_DSEQ(i) == 0) {
1583 				hr->hr_seq++;
1584 				if (forward) {
1585 					pperr->perr_dests[j].dest_seq =
1586 					    hr->hr_seq;
1587 				}
1588 			} else {
1589 				hr->hr_seq = PERR_DSEQ(i);
1590 			}
1591 			rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_VALID;
1592 			j++;
1593 			break;
1594 		case (IEEE80211_REASON_MESH_PERR_DEST_UNREACH):
1595 			if(HWMP_SEQ_GT(PERR_DSEQ(i), hr->hr_seq)) {
1596 				hr->hr_seq = PERR_DSEQ(i);
1597 				rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_VALID;
1598 				j++;
1599 			}
1600 			break;
1601 		case (IEEE80211_REASON_MESH_PERR_NO_PROXY):
1602 			rt_ext = ieee80211_mesh_rt_find(vap, PERR_DEXTADDR(i));
1603 			if (rt_ext != NULL) {
1604 				rt_ext->rt_flags &=
1605 				    ~IEEE80211_MESHRT_FLAGS_VALID;
1606 				j++;
1607 			}
1608 			break;
1609 		default:
1610 			IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1611 			    "PERR, unknown reason code %u\n", PERR_DFLAGS(i));
1612 			goto done; /* XXX: stats?? */
1613 		}
1614 		ieee80211_mesh_rt_flush_peer(vap, PERR_DADDR(i));
1615 		KASSERT(j < 32, ("PERR, error ndest >= 32 (%u)", j));
1616 	}
1617 	if (j == 0) {
1618 		IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL, "%s",
1619 		    "PERR not accepted");
1620 		goto done; /* XXX: stats?? */
1621 	}
1622 
1623 	/*
1624 	 * Propagate the PERR if we previously found it on our routing table.
1625 	 */
1626 	if (forward && perr->perr_ttl > 1) {
1627 		IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1628 		    "propagate PERR from %6D", wh->i_addr2, ":");
1629 		pperr->perr_ndests = j;
1630 		pperr->perr_ttl--;
1631 		hwmp_send_perr(vap, broadcastaddr, pperr);
1632 	}
1633 done:
1634 	if (pperr != NULL)
1635 		free(pperr, M_80211_MESH_PERR);
1636 }
1637 #undef	PERR_DFLAGS
1638 #undef	PERR_DADDR
1639 #undef	PERR_DSEQ
1640 #undef	PERR_DEXTADDR
1641 #undef	PERR_DRCODE
1642 
1643 static int
1644 hwmp_send_perr(struct ieee80211vap *vap,
1645     const uint8_t da[IEEE80211_ADDR_LEN],
1646     struct ieee80211_meshperr_ie *perr)
1647 {
1648 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1649 	int i;
1650 	uint8_t length = 0;
1651 
1652 	/*
1653 	 * Enforce PERR interval.
1654 	 */
1655 	if (ratecheck(&hs->hs_lastperr, &ieee80211_hwmp_perrminint) == 0)
1656 		return EALREADY;
1657 	getmicrouptime(&hs->hs_lastperr);
1658 
1659 	/*
1660 	 * mesh perr action frame format
1661 	 *     [6] da
1662 	 *     [6] sa
1663 	 *     [6] addr3 = sa
1664 	 *     [1] action
1665 	 *     [1] category
1666 	 *     [tlv] mesh path error
1667 	 */
1668 	perr->perr_ie = IEEE80211_ELEMID_MESHPERR;
1669 	length = IEEE80211_MESHPERR_BASE_SZ;
1670 	for (i = 0; i<perr->perr_ndests; i++) {
1671 		if (perr->perr_dests[i].dest_flags &
1672 		    IEEE80211_MESHPERR_FLAGS_AE) {
1673 			length += IEEE80211_MESHPERR_DEST_SZ_AE;
1674 			continue ;
1675 		}
1676 		length += IEEE80211_MESHPERR_DEST_SZ;
1677 	}
1678 	perr->perr_len =length;
1679 	return hwmp_send_action(vap, da, (uint8_t *)perr, perr->perr_len+2);
1680 }
1681 
1682 /*
1683  * Called from the rest of the net80211 code (mesh code for example).
1684  * NB: IEEE80211_REASON_MESH_PERR_DEST_UNREACH can be trigger by the fact that
1685  * a mesh STA is unable to forward an MSDU/MMPDU to a next-hop mesh STA.
1686  */
1687 #define	PERR_DFLAGS(n)		perr.perr_dests[n].dest_flags
1688 #define	PERR_DADDR(n)		perr.perr_dests[n].dest_addr
1689 #define	PERR_DSEQ(n)		perr.perr_dests[n].dest_seq
1690 #define	PERR_DEXTADDR(n)	perr.perr_dests[n].dest_ext_addr
1691 #define	PERR_DRCODE(n)		perr.perr_dests[n].dest_rcode
1692 static void
1693 hwmp_senderror(struct ieee80211vap *vap,
1694     const uint8_t addr[IEEE80211_ADDR_LEN],
1695     struct ieee80211_mesh_route *rt, int rcode)
1696 {
1697 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1698 	struct ieee80211_hwmp_route *hr = NULL;
1699 	struct ieee80211_meshperr_ie perr;
1700 
1701 	if (rt != NULL)
1702 		hr = IEEE80211_MESH_ROUTE_PRIV(rt,
1703 		    struct ieee80211_hwmp_route);
1704 
1705 	perr.perr_ndests = 1;
1706 	perr.perr_ttl = ms->ms_ttl;
1707 	PERR_DFLAGS(0) = 0;
1708 	PERR_DRCODE(0) = rcode;
1709 
1710 	switch (rcode) {
1711 	case IEEE80211_REASON_MESH_PERR_NO_FI:
1712 		IEEE80211_ADDR_COPY(PERR_DADDR(0), addr);
1713 		PERR_DSEQ(0) = 0; /* reserved */
1714 		break;
1715 	case IEEE80211_REASON_MESH_PERR_NO_PROXY:
1716 		KASSERT(rt != NULL, ("no proxy info for sending PERR"));
1717 		KASSERT(rt->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY,
1718 		    ("route is not marked proxy"));
1719 		PERR_DFLAGS(0) |= IEEE80211_MESHPERR_FLAGS_AE;
1720 		IEEE80211_ADDR_COPY(PERR_DADDR(0), vap->iv_myaddr);
1721 		PERR_DSEQ(0) = rt->rt_ext_seq;
1722 		IEEE80211_ADDR_COPY(PERR_DEXTADDR(0), addr);
1723 		break;
1724 	case IEEE80211_REASON_MESH_PERR_DEST_UNREACH:
1725 		KASSERT(rt != NULL, ("no route info for sending PERR"));
1726 		IEEE80211_ADDR_COPY(PERR_DADDR(0), addr);
1727 		PERR_DSEQ(0) = hr->hr_seq;
1728 		break;
1729 	default:
1730 		KASSERT(0, ("unknown reason code for HWMP PERR (%u)", rcode));
1731 	}
1732 	hwmp_send_perr(vap, broadcastaddr, &perr);
1733 }
1734 #undef	PERR_DFLAGS
1735 #undef	PEER_DADDR
1736 #undef	PERR_DSEQ
1737 #undef	PERR_DEXTADDR
1738 #undef	PERR_DRCODE
1739 
1740 static void
1741 hwmp_recv_rann(struct ieee80211vap *vap, struct ieee80211_node *ni,
1742     const struct ieee80211_frame *wh, const struct ieee80211_meshrann_ie *rann)
1743 {
1744 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1745 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1746 	struct ieee80211_mesh_route *rt = NULL;
1747 	struct ieee80211_hwmp_route *hr;
1748 	struct ieee80211_meshpreq_ie preq;
1749 	struct ieee80211_meshrann_ie prann;
1750 	uint32_t metric = 0;
1751 
1752 	if (IEEE80211_ADDR_EQ(rann->rann_addr, vap->iv_myaddr))
1753 		return;
1754 
1755 	rt = ieee80211_mesh_rt_find(vap, rann->rann_addr);
1756 	if (rt != NULL && rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) {
1757 		hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1758 
1759 		/* Acceptance criteria: if RANN.seq < stored seq, discard RANN */
1760 		if (HWMP_SEQ_LT(rann->rann_seq, hr->hr_seq)) {
1761 			IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1762 			"RANN seq %u < %u", rann->rann_seq, hr->hr_seq);
1763 			return;
1764 		}
1765 
1766 		/* Acceptance criteria: if RANN.seq == stored seq AND
1767 		* RANN.metric > stored metric, discard RANN */
1768 		if (HWMP_SEQ_EQ(rann->rann_seq, hr->hr_seq) &&
1769 		rann->rann_metric > rt->rt_metric) {
1770 			IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1771 			"RANN metric %u > %u", rann->rann_metric, rt->rt_metric);
1772 			return;
1773 		}
1774 	}
1775 
1776 	/* RANN ACCEPTED */
1777 
1778 	ieee80211_hwmp_rannint = rann->rann_interval; /* XXX: mtx lock? */
1779 	metric = rann->rann_metric + ms->ms_pmetric->mpm_metric(ni);
1780 
1781 	if (rt == NULL) {
1782 		rt = ieee80211_mesh_rt_add(vap, rann->rann_addr);
1783 		if (rt == NULL) {
1784 			IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1785 			    "unable to add mac for RANN root %6D",
1786 			    rann->rann_addr, ":");
1787 			    vap->iv_stats.is_mesh_rtaddfailed++;
1788 			return;
1789 		}
1790 	}
1791 	hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1792 	/* Check if root is a mesh gate, mark it */
1793 	if (rann->rann_flags & IEEE80211_MESHRANN_FLAGS_GATE) {
1794 		struct ieee80211_mesh_gate_route *gr;
1795 
1796 		rt->rt_flags |= IEEE80211_MESHRT_FLAGS_GATE;
1797 		gr = ieee80211_mesh_mark_gate(vap, rann->rann_addr,
1798 			rt);
1799 		gr->gr_lastseq = 0; /* NOT GANN */
1800 	}
1801 	/* discovery timeout */
1802 	ieee80211_mesh_rt_update(rt,
1803 	    ticks_to_msecs(ieee80211_hwmp_roottimeout));
1804 
1805 	preq.preq_flags = IEEE80211_MESHPREQ_FLAGS_AM;
1806 	preq.preq_hopcount = 0;
1807 	preq.preq_ttl = ms->ms_ttl;
1808 	preq.preq_id = 0; /* reserved */
1809 	IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1810 	preq.preq_origseq = ++hs->hs_seq;
1811 	preq.preq_lifetime = ieee80211_hwmp_roottimeout;
1812 	preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1813 	preq.preq_tcount = 1;
1814 	preq.preq_targets[0].target_flags = IEEE80211_MESHPREQ_TFLAGS_TO;
1815 	/* NB: IEEE80211_MESHPREQ_TFLAGS_USN = 0 implicitly implied */
1816 	IEEE80211_ADDR_COPY(preq.preq_targets[0].target_addr, rann->rann_addr);
1817 	preq.preq_targets[0].target_seq = rann->rann_seq;
1818 	/* XXX: if rootconfint have not passed, we built this preq in vain */
1819 	hwmp_send_preq(vap, wh->i_addr2, &preq, &hr->hr_lastrootconf,
1820 	    &ieee80211_hwmp_rootconfint);
1821 
1822 	/* propagate a RANN */
1823 	if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1824 	    rann->rann_ttl > 1 &&
1825 	    ms->ms_flags & IEEE80211_MESHFLAGS_FWD) {
1826 		hr->hr_seq = rann->rann_seq;
1827 		memcpy(&prann, rann, sizeof(prann));
1828 		prann.rann_hopcount += 1;
1829 		prann.rann_ttl -= 1;
1830 		prann.rann_metric += ms->ms_pmetric->mpm_metric(ni);
1831 		hwmp_send_rann(vap, broadcastaddr, &prann);
1832 	}
1833 }
1834 
1835 static int
1836 hwmp_send_rann(struct ieee80211vap *vap,
1837     const uint8_t da[IEEE80211_ADDR_LEN],
1838     struct ieee80211_meshrann_ie *rann)
1839 {
1840 	/*
1841 	 * mesh rann action frame format
1842 	 *     [6] da
1843 	 *     [6] sa
1844 	 *     [6] addr3 = sa
1845 	 *     [1] action
1846 	 *     [1] category
1847 	 *     [tlv] root annoucement
1848 	 */
1849 	rann->rann_ie = IEEE80211_ELEMID_MESHRANN;
1850 	rann->rann_len = IEEE80211_MESHRANN_BASE_SZ;
1851 	return hwmp_send_action(vap, da, (uint8_t *)rann, rann->rann_len + 2);
1852 }
1853 
1854 #define	PREQ_TFLAGS(n)	preq.preq_targets[n].target_flags
1855 #define	PREQ_TADDR(n)	preq.preq_targets[n].target_addr
1856 #define	PREQ_TSEQ(n)	preq.preq_targets[n].target_seq
1857 static void
1858 hwmp_rediscover_cb(void *arg)
1859 {
1860 	struct ieee80211_mesh_route *rt = arg;
1861 	struct ieee80211vap *vap = rt->rt_vap;
1862 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1863 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1864 	struct ieee80211_hwmp_route *hr;
1865 	struct ieee80211_meshpreq_ie preq; /* Optimize: storing first preq? */
1866 
1867 	if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID))
1868 		return ; /* nothing to do */
1869 
1870 	hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1871 	if (hr->hr_preqretries >=
1872 		ieee80211_hwmp_maxpreq_retries) {
1873 		IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_ANY,
1874 			rt->rt_dest, "%s",
1875 			"max number of discovery, send queued frames to GATE");
1876 		ieee80211_mesh_forward_to_gates(vap, rt);
1877 		vap->iv_stats.is_mesh_fwd_nopath++;
1878 		return ; /* XXX: flush queue? */
1879 	}
1880 
1881 	hr->hr_preqretries++;
1882 
1883 
1884 	IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, rt->rt_dest,
1885 	    "start path rediscovery , target seq %u", hr->hr_seq);
1886 	/*
1887 	 * Try to discover the path for this node.
1888 	 * Group addressed PREQ Case A
1889 	 */
1890 	preq.preq_flags = 0;
1891 	preq.preq_hopcount = 0;
1892 	preq.preq_ttl = ms->ms_ttl;
1893 	preq.preq_id = ++hs->hs_preqid;
1894 	IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1895 	preq.preq_origseq = hr->hr_origseq;
1896 	preq.preq_lifetime = ticks_to_msecs(ieee80211_hwmp_pathtimeout);
1897 	preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1898 	preq.preq_tcount = 1;
1899 	IEEE80211_ADDR_COPY(PREQ_TADDR(0), rt->rt_dest);
1900 	PREQ_TFLAGS(0) = 0;
1901 	if (ieee80211_hwmp_targetonly)
1902 		PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_TO;
1903 	PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_USN;
1904 	PREQ_TSEQ(0) = 0; /* RESERVED when USN flag is set */
1905 	/* XXX check return value */
1906 	hwmp_send_preq(vap, broadcastaddr, &preq, &hr->hr_lastpreq,
1907 	    &ieee80211_hwmp_preqminint);
1908 	callout_reset(&rt->rt_discovery,
1909 		ieee80211_hwmp_net_diameter_traversaltime * 2,
1910 		hwmp_rediscover_cb, rt);
1911 }
1912 
1913 static struct ieee80211_node *
1914 hwmp_discover(struct ieee80211vap *vap,
1915     const uint8_t dest[IEEE80211_ADDR_LEN], struct mbuf *m)
1916 {
1917 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1918 	struct ieee80211_mesh_state *ms = vap->iv_mesh;
1919 	struct ieee80211_mesh_route *rt = NULL;
1920 	struct ieee80211_hwmp_route *hr;
1921 	struct ieee80211_meshpreq_ie preq;
1922 	struct ieee80211_node *ni;
1923 	int sendpreq = 0;
1924 
1925 	KASSERT(vap->iv_opmode == IEEE80211_M_MBSS,
1926 	    ("not a mesh vap, opmode %d", vap->iv_opmode));
1927 
1928 	KASSERT(!IEEE80211_ADDR_EQ(vap->iv_myaddr, dest),
1929 	    ("%s: discovering self!", __func__));
1930 
1931 	ni = NULL;
1932 	if (!IEEE80211_IS_MULTICAST(dest)) {
1933 		rt = ieee80211_mesh_rt_find(vap, dest);
1934 		if (rt == NULL) {
1935 			rt = ieee80211_mesh_rt_add(vap, dest);
1936 			if (rt == NULL) {
1937 				IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP,
1938 				    ni, "unable to add discovery path to %6D",
1939 				    dest, ":");
1940 				vap->iv_stats.is_mesh_rtaddfailed++;
1941 				goto done;
1942 			}
1943 		}
1944 		hr = IEEE80211_MESH_ROUTE_PRIV(rt,
1945 		    struct ieee80211_hwmp_route);
1946 		if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_DISCOVER) {
1947 			IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
1948 			    "%s", "already discovering queue frame until path found");
1949 			sendpreq = 1;
1950 			goto done;
1951 		}
1952 		if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) == 0) {
1953 			if (hr->hr_lastdiscovery != 0 &&
1954 			    (ticks - hr->hr_lastdiscovery <
1955 			    (ieee80211_hwmp_net_diameter_traversaltime * 2))) {
1956 				IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_ANY,
1957 			            dest, NULL, "%s",
1958 				    "too frequent discovery requeust");
1959 				sendpreq = 1;
1960 				goto done;
1961 			}
1962 			hr->hr_lastdiscovery = ticks;
1963 			if (hr->hr_preqretries >=
1964 			    ieee80211_hwmp_maxpreq_retries) {
1965 				IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_ANY,
1966 			            dest, NULL, "%s",
1967 				    "no valid path , max number of discovery");
1968 				vap->iv_stats.is_mesh_fwd_nopath++;
1969 				goto done;
1970 			}
1971 			rt->rt_flags = IEEE80211_MESHRT_FLAGS_DISCOVER;
1972 			hr->hr_preqretries++;
1973 			if (hr->hr_origseq == 0)
1974 				hr->hr_origseq = ++hs->hs_seq;
1975 			rt->rt_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1976 			sendpreq = 1;
1977 			IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
1978 			    "start path discovery (src %s), target seq %u",
1979 			    m == NULL ? "<none>" : ether_sprintf(
1980 			    mtod(m, struct ether_header *)->ether_shost),
1981 			    hr->hr_seq);
1982 			/*
1983 			 * Try to discover the path for this node.
1984 			 * Group addressed PREQ Case A
1985 			 */
1986 			preq.preq_flags = 0;
1987 			preq.preq_hopcount = 0;
1988 			preq.preq_ttl = ms->ms_ttl;
1989 			preq.preq_id = ++hs->hs_preqid;
1990 			IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1991 			preq.preq_origseq = hr->hr_origseq;
1992 			preq.preq_lifetime =
1993 			    ticks_to_msecs(ieee80211_hwmp_pathtimeout);
1994 			preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1995 			preq.preq_tcount = 1;
1996 			IEEE80211_ADDR_COPY(PREQ_TADDR(0), dest);
1997 			PREQ_TFLAGS(0) = 0;
1998 			if (ieee80211_hwmp_targetonly)
1999 				PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_TO;
2000 			PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_USN;
2001 			PREQ_TSEQ(0) = 0; /* RESERVED when USN flag is set */
2002 			/* XXX check return value */
2003 			hwmp_send_preq(vap, broadcastaddr, &preq,
2004 			    &hr->hr_lastpreq, &ieee80211_hwmp_preqminint);
2005 			callout_reset(&rt->rt_discovery,
2006 			    ieee80211_hwmp_net_diameter_traversaltime * 2,
2007 			    hwmp_rediscover_cb, rt);
2008 		}
2009 		if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)
2010 			ni = ieee80211_find_txnode(vap, rt->rt_nexthop);
2011 	} else {
2012 		ni = ieee80211_find_txnode(vap, dest);
2013 		/* NB: if null then we leak mbuf */
2014 		KASSERT(ni != NULL, ("leak mcast frame"));
2015 		return ni;
2016 	}
2017 done:
2018 	if (ni == NULL && m != NULL) {
2019 		if (sendpreq) {
2020 			struct ieee80211com *ic = vap->iv_ic;
2021 			/*
2022 			 * Queue packet for transmit when path discovery
2023 			 * completes.  If discovery never completes the
2024 			 * frame will be flushed by way of the aging timer.
2025 			 */
2026 			IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
2027 			    "%s", "queue frame until path found");
2028 			m->m_pkthdr.rcvif = (void *)(uintptr_t)
2029 			    ieee80211_mac_hash(ic, dest);
2030 			/* XXX age chosen randomly */
2031 			ieee80211_ageq_append(&ic->ic_stageq, m,
2032 			    IEEE80211_INACT_WAIT);
2033 		} else {
2034 			IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
2035 			    dest, NULL, "%s", "no valid path to this node");
2036 			m_freem(m);
2037 		}
2038 	}
2039 	return ni;
2040 }
2041 #undef	PREQ_TFLAGS
2042 #undef	PREQ_TADDR
2043 #undef	PREQ_TSEQ
2044 
2045 static int
2046 hwmp_ioctl_get80211(struct ieee80211vap *vap, struct ieee80211req *ireq)
2047 {
2048 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
2049 	int error;
2050 
2051 	if (vap->iv_opmode != IEEE80211_M_MBSS)
2052 		return ENOSYS;
2053 	error = 0;
2054 	switch (ireq->i_type) {
2055 	case IEEE80211_IOC_HWMP_ROOTMODE:
2056 		ireq->i_val = hs->hs_rootmode;
2057 		break;
2058 	case IEEE80211_IOC_HWMP_MAXHOPS:
2059 		ireq->i_val = hs->hs_maxhops;
2060 		break;
2061 	default:
2062 		return ENOSYS;
2063 	}
2064 	return error;
2065 }
2066 IEEE80211_IOCTL_GET(hwmp, hwmp_ioctl_get80211);
2067 
2068 static int
2069 hwmp_ioctl_set80211(struct ieee80211vap *vap, struct ieee80211req *ireq)
2070 {
2071 	struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
2072 	int error;
2073 
2074 	if (vap->iv_opmode != IEEE80211_M_MBSS)
2075 		return ENOSYS;
2076 	error = 0;
2077 	switch (ireq->i_type) {
2078 	case IEEE80211_IOC_HWMP_ROOTMODE:
2079 		if (ireq->i_val < 0 || ireq->i_val > 3)
2080 			return EINVAL;
2081 		hs->hs_rootmode = ireq->i_val;
2082 		hwmp_rootmode_setup(vap);
2083 		break;
2084 	case IEEE80211_IOC_HWMP_MAXHOPS:
2085 		if (ireq->i_val <= 0 || ireq->i_val > 255)
2086 			return EINVAL;
2087 		hs->hs_maxhops = ireq->i_val;
2088 		break;
2089 	default:
2090 		return ENOSYS;
2091 	}
2092 	return error;
2093 }
2094 IEEE80211_IOCTL_SET(hwmp, hwmp_ioctl_set80211);
2095