sys/netproto/802_11/wlan/ieee80211_hwmp.c

   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 <netproto/802_11/ieee80211_var.h>
  63 #include <netproto/802_11/ieee80211_action.h>
  64 #include <netproto/802_11/ieee80211_input.h>
  65 #include <netproto/802_11/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 = kmalloc(sizeof(struct ieee80211_hwmp_state), M_80211_VAP,
 272             M_INTWAIT | M_ZERO);
 273         if (hs == NULL) {
 274                 kprintf("%s: couldn't alloc HWMP state\n", __func__);
 275                 return;
 276         }
 277         hs->hs_maxhops = IEEE80211_HWMP_DEFAULT_MAXHOPS;
 278         callout_init_mp(&hs->hs_roottimer);
 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         kfree(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 = kmalloc(sizeof(*preq) +
 433                             (ndest - 1) * sizeof(*preq->preq_targets),
 434                             M_80211_MESH_PREQ, M_INTWAIT | 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                         kfree(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 = kmalloc(sizeof(*prep),
 480                             M_80211_MESH_PREP, M_INTWAIT | 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                         kfree(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 = kmalloc(sizeof(*perr) +
 519                             (ndest - 1) * sizeof(*perr->perr_dests),
 520                             M_80211_MESH_PERR, M_INTWAIT | 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                         kfree(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 %s of %s",
 922                             ether_sprintf(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 transmitter %s of %s, metric %d:%d",
 933                     rttran->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
 934                     "prefer" : "update", ether_sprintf(ni->ni_macaddr),
 935                     hwmp_frame,
 936                     rttran->rt_metric, metric);
 937                 IEEE80211_ADDR_COPY(rttran->rt_nexthop, ni->ni_macaddr);
 938                 rttran->rt_metric = metric;
 939                 rttran->rt_nhops  = 1;
 940                 ieee80211_mesh_rt_update(rttran, ms->ms_ppath->mpp_inact);
 941                 rttran->rt_flags = IEEE80211_MESHRT_FLAGS_VALID;
 942         }
 943 }
 944
 945 #define PREQ_TFLAGS(n)  preq->preq_targets[n].target_flags
 946 #define PREQ_TADDR(n)   preq->preq_targets[n].target_addr
 947 #define PREQ_TSEQ(n)    preq->preq_targets[n].target_seq
 948 static void
 949 hwmp_recv_preq(struct ieee80211vap *vap, struct ieee80211_node *ni,
 950     const struct ieee80211_frame *wh, const struct ieee80211_meshpreq_ie *preq)
 951 {
 952         struct ieee80211_mesh_state *ms = vap->iv_mesh;
 953         struct ieee80211_mesh_route *rtorig = NULL;
 954         struct ieee80211_mesh_route *rtorig_ext = NULL;
 955         struct ieee80211_mesh_route *rttarg = NULL;
 956         struct ieee80211_hwmp_route *hrorig = NULL;
 957         struct ieee80211_hwmp_route *hrtarg = NULL;
 958         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
 959         struct ieee80211_meshprep_ie prep;
 960         ieee80211_hwmp_seq preqid;      /* last seen preqid for orig */
 961         uint32_t metric = 0;
 962
 963         /*
 964          * Ignore PREQs from us. Could happen because someone forward it
 965          * back to us.
 966          */
 967         if (IEEE80211_ADDR_EQ(vap->iv_myaddr, preq->preq_origaddr))
 968                 return;
 969
 970         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
 971             "received PREQ, orig %s, targ(0) %s",
 972             ether_sprintf(preq->preq_origaddr),
 973             ether_sprintf(PREQ_TADDR(0)));
 974
 975         /*
 976          * Acceptance criteria: (if the PREQ is not for us or not broadcast,
 977          * or an external mac address not proxied by us),
 978          * AND forwarding is disabled, discard this PREQ.
 979          */
 980         rttarg = ieee80211_mesh_rt_find(vap, PREQ_TADDR(0));
 981         if (!(ms->ms_flags & IEEE80211_MESHFLAGS_FWD) &&
 982             (!IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0)) ||
 983             !IEEE80211_IS_MULTICAST(PREQ_TADDR(0)) ||
 984             (rttarg != NULL &&
 985             rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY &&
 986             IEEE80211_ADDR_EQ(vap->iv_myaddr, rttarg->rt_mesh_gate)))) {
 987                 IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
 988                     preq->preq_origaddr, NULL, "%s", "not accepting PREQ");
 989                 return;
 990         }
 991         /*
 992          * Acceptance criteria: if unicast addressed
 993          * AND no valid forwarding for Target of PREQ, discard this PREQ.
 994          */
 995         if(rttarg != NULL)
 996                 hrtarg = IEEE80211_MESH_ROUTE_PRIV(rttarg,
 997                     struct ieee80211_hwmp_route);
 998         /* Address mode: ucast */
 999         if(preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AM &&
1000             rttarg == NULL &&
1001             !IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0))) {
1002                 IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
1003                     preq->preq_origaddr, NULL,
1004                     "unicast addressed PREQ of unknown target %s",
1005                     ether_sprintf(PREQ_TADDR(0)));
1006                 return;
1007         }
1008
1009         /* PREQ ACCEPTED */
1010
1011         rtorig = ieee80211_mesh_rt_find(vap, preq->preq_origaddr);
1012         if (rtorig == NULL) {
1013                 rtorig = ieee80211_mesh_rt_add(vap, preq->preq_origaddr);
1014                 if (rtorig == NULL) {
1015                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1016                             "unable to add orig path to %s",
1017                             ether_sprintf(preq->preq_origaddr));
1018                         vap->iv_stats.is_mesh_rtaddfailed++;
1019                         return;
1020                 }
1021                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1022                     "adding originator %s",
1023                     ether_sprintf(preq->preq_origaddr));
1024         }
1025         hrorig = IEEE80211_MESH_ROUTE_PRIV(rtorig, struct ieee80211_hwmp_route);
1026
1027         /* record last seen preqid */
1028         preqid = hrorig->hr_preqid;
1029         hrorig->hr_preqid = HWMP_SEQ_MAX(hrorig->hr_preqid, preq->preq_id);
1030
1031         /* Data creation and update of forwarding information
1032          * according to Table 11C-8 for originator mesh STA.
1033          */
1034         metric = preq->preq_metric + ms->ms_pmetric->mpm_metric(ni);
1035         if (HWMP_SEQ_GT(preq->preq_origseq, hrorig->hr_seq) ||
1036             (HWMP_SEQ_EQ(preq->preq_origseq, hrorig->hr_seq) &&
1037             metric < rtorig->rt_metric)) {
1038                 hrorig->hr_seq = preq->preq_origseq;
1039                 IEEE80211_ADDR_COPY(rtorig->rt_nexthop, wh->i_addr2);
1040                 rtorig->rt_metric = metric;
1041                 rtorig->rt_nhops  = preq->preq_hopcount + 1;
1042                 ieee80211_mesh_rt_update(rtorig, preq->preq_lifetime);
1043                 /* Path to orig is valid now.
1044                  * NB: we know it can't be Proxy, and if it is GATE
1045                  * it will be marked below.
1046                  */
1047                 rtorig->rt_flags = IEEE80211_MESHRT_FLAGS_VALID;
1048         } else if ((hrtarg != NULL &&
1049             !HWMP_SEQ_EQ(hrtarg->hr_seq, PREQ_TSEQ(0))) ||
1050             (rtorig->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1051             preqid >= preq->preq_id)) {
1052                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1053                     "discard PREQ from %s, old seqno %u <= %u,"
1054                     " or old preqid %u < %u",
1055                     ether_sprintf(preq->preq_origaddr),
1056                     preq->preq_origseq, hrorig->hr_seq,
1057                     preq->preq_id, preqid);
1058                 return;
1059         }
1060
1061         /* Update forwarding information to TA if metric improves. */
1062         hwmp_update_transmitter(vap, ni, "PREQ");
1063
1064         /*
1065          * Check if the PREQ is addressed to us.
1066          * or a Proxy currently gated by us.
1067          */
1068         if (IEEE80211_ADDR_EQ(vap->iv_myaddr, PREQ_TADDR(0)) ||
1069             (ms->ms_flags & IEEE80211_MESHFLAGS_GATE &&
1070             rttarg != NULL &&
1071             IEEE80211_ADDR_EQ(vap->iv_myaddr, rttarg->rt_mesh_gate) &&
1072             rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY &&
1073             rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)) {
1074                 /*
1075                  * When we are the target we shall update our own HWMP seq
1076                  * number with max of (current and preq->seq) + 1
1077                  */
1078                 hs->hs_seq = HWMP_SEQ_MAX(hs->hs_seq, PREQ_TSEQ(0)) + 1;
1079
1080                 prep.prep_flags = 0;
1081                 prep.prep_hopcount = 0;
1082                 prep.prep_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1083                 IEEE80211_ADDR_COPY(prep.prep_targetaddr, vap->iv_myaddr);
1084                 if (rttarg != NULL && /* if NULL it means we are the target */
1085                     rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY) {
1086                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1087                             "reply for proxy %s",
1088                             ether_sprintf(rttarg->rt_dest));
1089                         prep.prep_flags |= IEEE80211_MESHPREP_FLAGS_AE;
1090                         IEEE80211_ADDR_COPY(prep.prep_target_ext_addr,
1091                             rttarg->rt_dest);
1092                         /* update proxy seqno to HWMP seqno */
1093                         rttarg->rt_ext_seq = hs->hs_seq;
1094                         prep.prep_hopcount = rttarg->rt_nhops;
1095                         prep.prep_metric = rttarg->rt_metric;
1096                         IEEE80211_ADDR_COPY(prep.prep_targetaddr, rttarg->rt_mesh_gate);
1097                 }
1098                 /*
1099                  * Build and send a PREP frame.
1100                  */
1101                 prep.prep_ttl = ms->ms_ttl;
1102                 prep.prep_targetseq = hs->hs_seq;
1103                 prep.prep_lifetime = preq->preq_lifetime;
1104                 IEEE80211_ADDR_COPY(prep.prep_origaddr, preq->preq_origaddr);
1105                 prep.prep_origseq = preq->preq_origseq;
1106
1107                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1108                     "reply to %s", ether_sprintf(preq->preq_origaddr));
1109                 hwmp_send_prep(vap, wh->i_addr2, &prep);
1110                 return;
1111         }
1112         /* we may update our proxy information for the orig external */
1113         else if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE) {
1114                 rtorig_ext =
1115                     ieee80211_mesh_rt_find(vap, preq->preq_orig_ext_addr);
1116                 if (rtorig_ext == NULL) {
1117                         rtorig_ext = ieee80211_mesh_rt_add(vap,
1118                             preq->preq_orig_ext_addr);
1119                         if (rtorig_ext == NULL) {
1120                                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1121                                     "unable to add orig ext proxy to %s",
1122                                     ether_sprintf(preq->preq_orig_ext_addr));
1123                                 vap->iv_stats.is_mesh_rtaddfailed++;
1124                                 return;
1125                         }
1126                         IEEE80211_ADDR_COPY(rtorig_ext->rt_mesh_gate,
1127                             preq->preq_origaddr);
1128                 }
1129                 rtorig_ext->rt_ext_seq = preq->preq_origseq;
1130                 ieee80211_mesh_rt_update(rtorig_ext, preq->preq_lifetime);
1131         }
1132         /*
1133          * Proactive PREQ: reply with a proactive PREP to the
1134          * root STA if requested.
1135          */
1136         if (IEEE80211_ADDR_EQ(PREQ_TADDR(0), broadcastaddr) &&
1137             (PREQ_TFLAGS(0) & IEEE80211_MESHPREQ_TFLAGS_TO)) {
1138                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1139                     "root mesh station @ %s",
1140                     ether_sprintf(preq->preq_origaddr));
1141
1142                 /* Check if root is a mesh gate, mark it */
1143                 if (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_GATE) {
1144                         struct ieee80211_mesh_gate_route *gr;
1145
1146                         rtorig->rt_flags |= IEEE80211_MESHRT_FLAGS_GATE;
1147                         gr = ieee80211_mesh_mark_gate(vap, preq->preq_origaddr,
1148                             rtorig);
1149                         gr->gr_lastseq = 0; /* NOT GANN */
1150                 }
1151
1152                 /*
1153                  * Reply with a PREP if we don't have a path to the root
1154                  * or if the root sent us a proactive PREQ.
1155                  */
1156                 if ((rtorig->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) == 0 ||
1157                     (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_PP)) {
1158                         prep.prep_flags = 0;
1159                         prep.prep_hopcount = 0;
1160                         prep.prep_ttl = ms->ms_ttl;
1161                         IEEE80211_ADDR_COPY(prep.prep_origaddr,
1162                             preq->preq_origaddr);
1163                         prep.prep_origseq = preq->preq_origseq;
1164                         prep.prep_lifetime = preq->preq_lifetime;
1165                         prep.prep_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1166                         IEEE80211_ADDR_COPY(prep.prep_targetaddr,
1167                             vap->iv_myaddr);
1168                         prep.prep_targetseq = ++hs->hs_seq;
1169                         hwmp_send_prep(vap, rtorig->rt_nexthop, &prep);
1170                 }
1171         }
1172
1173         /*
1174          * Forwarding and Intermediate reply for PREQs with 1 target.
1175          */
1176         if ((preq->preq_tcount == 1) && (preq->preq_ttl > 1) &&
1177             (ms->ms_flags & IEEE80211_MESHFLAGS_FWD)) {
1178                 struct ieee80211_meshpreq_ie ppreq; /* propagated PREQ */
1179
1180                 memcpy(&ppreq, preq, sizeof(ppreq));
1181
1182                 /*
1183                  * We have a valid route to this node.
1184                  * NB: if target is proxy dont reply.
1185                  */
1186                 if (rttarg != NULL &&
1187                     rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1188                     !(rttarg->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY)) {
1189                         /*
1190                          * Check if we can send an intermediate Path Reply,
1191                          * i.e., Target Only bit is not set and target is not
1192                          * the MAC broadcast address.
1193                          */
1194                         if (!(PREQ_TFLAGS(0) & IEEE80211_MESHPREQ_TFLAGS_TO) &&
1195                             !IEEE80211_ADDR_EQ(PREQ_TADDR(0), broadcastaddr)) {
1196                                 struct ieee80211_meshprep_ie prep;
1197
1198                                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1199                                     "intermediate reply for PREQ from %s",
1200                                     ether_sprintf(preq->preq_origaddr));
1201                                 prep.prep_flags = 0;
1202                                 prep.prep_hopcount = rttarg->rt_nhops;
1203                                 prep.prep_ttl = ms->ms_ttl;
1204                                 IEEE80211_ADDR_COPY(&prep.prep_targetaddr,
1205                                     PREQ_TADDR(0));
1206                                 prep.prep_targetseq = hrtarg->hr_seq;
1207                                 prep.prep_lifetime = preq->preq_lifetime;
1208                                 prep.prep_metric =rttarg->rt_metric;
1209                                 IEEE80211_ADDR_COPY(&prep.prep_origaddr,
1210                                     preq->preq_origaddr);
1211                                 prep.prep_origseq = hrorig->hr_seq;
1212                                 hwmp_send_prep(vap, rtorig->rt_nexthop, &prep);
1213
1214                                 /*
1215                                  * Set TO and unset RF bits because we have
1216                                  * sent a PREP.
1217                                  */
1218                                 ppreq.preq_targets[0].target_flags |=
1219                                     IEEE80211_MESHPREQ_TFLAGS_TO;
1220                         }
1221                 }
1222
1223                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1224                     "forward PREQ from %s",
1225                     ether_sprintf(preq->preq_origaddr));
1226                 ppreq.preq_hopcount += 1;
1227                 ppreq.preq_ttl -= 1;
1228                 ppreq.preq_metric += ms->ms_pmetric->mpm_metric(ni);
1229
1230                 /* don't do PREQ ratecheck when we propagate */
1231                 hwmp_send_preq(vap, broadcastaddr, &ppreq, NULL, NULL);
1232         }
1233 }
1234 #undef  PREQ_TFLAGS
1235 #undef  PREQ_TADDR
1236 #undef  PREQ_TSEQ
1237
1238 static int
1239 hwmp_send_preq(struct ieee80211vap *vap,
1240     const uint8_t da[IEEE80211_ADDR_LEN],
1241     struct ieee80211_meshpreq_ie *preq,
1242     struct timeval *last, struct timeval *minint)
1243 {
1244
1245         /*
1246          * Enforce PREQ interval.
1247          * NB: Proactive ROOT PREQs rate is handled by cb task.
1248          */
1249         if (last != NULL && minint != NULL) {
1250                 if (ratecheck(last, minint) == 0)
1251                         return EALREADY; /* XXX: we should postpone */
1252                 getmicrouptime(last);
1253         }
1254
1255         /*
1256          * mesh preq action frame format
1257          *     [6] da
1258          *     [6] sa
1259          *     [6] addr3 = sa
1260          *     [1] action
1261          *     [1] category
1262          *     [tlv] mesh path request
1263          */
1264         preq->preq_ie = IEEE80211_ELEMID_MESHPREQ;
1265         preq->preq_len = (preq->preq_flags & IEEE80211_MESHPREQ_FLAGS_AE ?
1266             IEEE80211_MESHPREQ_BASE_SZ_AE : IEEE80211_MESHPREQ_BASE_SZ) +
1267             preq->preq_tcount * IEEE80211_MESHPREQ_TRGT_SZ;
1268         return hwmp_send_action(vap, da, (uint8_t *)preq, preq->preq_len+2);
1269 }
1270
1271 static void
1272 hwmp_recv_prep(struct ieee80211vap *vap, struct ieee80211_node *ni,
1273     const struct ieee80211_frame *wh, const struct ieee80211_meshprep_ie *prep)
1274 {
1275 #define IS_PROXY(rt)    (rt->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY)
1276 #define PROXIED_BY_US(rt)               \
1277     (IEEE80211_ADDR_EQ(vap->iv_myaddr, rt->rt_mesh_gate))
1278         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1279         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1280         struct ieee80211_mesh_route *rt = NULL;
1281         struct ieee80211_mesh_route *rtorig = NULL;
1282         struct ieee80211_mesh_route *rtext = NULL;
1283         struct ieee80211_hwmp_route *hr;
1284         struct ieee80211com *ic = vap->iv_ic;
1285         struct mbuf *m, *next;
1286         uint32_t metric = 0;
1287         const uint8_t *addr;
1288
1289         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1290             "received PREP, orig %s, targ %s",
1291             ether_sprintf(prep->prep_origaddr),
1292             ether_sprintf(prep->prep_targetaddr));
1293
1294         /*
1295          * Acceptance criteria: (If the corresponding PREP was not generated
1296          * by us OR not generated by an external mac that is not proxied by us)
1297          * AND forwarding is disabled, discard this PREP.
1298          */
1299         rtorig = ieee80211_mesh_rt_find(vap, prep->prep_origaddr);
1300         if ((!IEEE80211_ADDR_EQ(vap->iv_myaddr, prep->prep_origaddr) ||
1301             (rtorig != NULL && IS_PROXY(rtorig) && !PROXIED_BY_US(rtorig))) &&
1302             !(ms->ms_flags & IEEE80211_MESHFLAGS_FWD)){
1303                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1304                     "discard PREP, orig(%s) not proxied or generated by us",
1305                     ether_sprintf(prep->prep_origaddr));
1306                 return;
1307         }
1308
1309         /* PREP ACCEPTED */
1310
1311         /*
1312          * If accepted shall create or update the active forwarding information
1313          * it maintains for the target mesh STA of the PREP (according to the
1314          * rules defined in 13.10.8.4). If the conditions for creating or
1315          * updating the forwarding information have not been met in those
1316          * rules, no further steps are applied to the PREP.
1317          */
1318         rt = ieee80211_mesh_rt_find(vap, prep->prep_targetaddr);
1319         if (rt == NULL) {
1320                 rt = ieee80211_mesh_rt_add(vap, prep->prep_targetaddr);
1321                 if (rt == NULL) {
1322                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1323                             "unable to add PREP path to %s",
1324                             ether_sprintf(prep->prep_targetaddr));
1325                         vap->iv_stats.is_mesh_rtaddfailed++;
1326                         return;
1327                 }
1328                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1329                     "adding target %s", ether_sprintf(prep->prep_targetaddr));
1330         }
1331         hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1332         /* update path metric */
1333         metric = prep->prep_metric + ms->ms_pmetric->mpm_metric(ni);
1334         if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)) {
1335                 if (HWMP_SEQ_LT(prep->prep_targetseq, hr->hr_seq)) {
1336                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1337                             "discard PREP from %s, old seq no %u < %u",
1338                             ether_sprintf(prep->prep_targetaddr),
1339                             prep->prep_targetseq, hr->hr_seq);
1340                         return;
1341                 } else if (HWMP_SEQ_LEQ(prep->prep_targetseq, hr->hr_seq) &&
1342                     metric > rt->rt_metric) {
1343                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1344                             "discard PREP from %s, new metric %u > %u",
1345                             ether_sprintf(prep->prep_targetaddr),
1346                             metric, rt->rt_metric);
1347                         return;
1348                 }
1349         }
1350
1351         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1352             "%s path to %s, hopcount %d:%d metric %d:%d",
1353             rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
1354             "prefer" : "update",
1355             ether_sprintf(prep->prep_targetaddr),
1356             rt->rt_nhops, prep->prep_hopcount + 1,
1357             rt->rt_metric, metric);
1358
1359         hr->hr_seq = prep->prep_targetseq;
1360         hr->hr_preqretries = 0;
1361         IEEE80211_ADDR_COPY(rt->rt_nexthop, ni->ni_macaddr);
1362         rt->rt_metric = metric;
1363         rt->rt_nhops = prep->prep_hopcount + 1;
1364         ieee80211_mesh_rt_update(rt, prep->prep_lifetime);
1365         if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_DISCOVER) {
1366                 /* discovery complete */
1367                 rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_DISCOVER;
1368         }
1369         rt->rt_flags |= IEEE80211_MESHRT_FLAGS_VALID; /* mark valid */
1370
1371         /* Update forwarding information to TA if metric improves */
1372         hwmp_update_transmitter(vap, ni, "PREP");
1373
1374         /*
1375          * If it's NOT for us, propagate the PREP
1376          */
1377         if (!IEEE80211_ADDR_EQ(vap->iv_myaddr, prep->prep_origaddr) &&
1378             prep->prep_ttl > 1 &&
1379             prep->prep_hopcount < hs->hs_maxhops) {
1380                 struct ieee80211_meshprep_ie pprep; /* propagated PREP */
1381                 /*
1382                  * NB: We should already have setup the path to orig
1383                  * mesh STA when we propagated PREQ to target mesh STA,
1384                  * no PREP is generated without a corresponding PREQ.
1385                  * XXX: for now just ignore.
1386                  */
1387                 if (rtorig == NULL) {
1388                         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1389                             "received PREP for an unknown orig(%s)",
1390                             ether_sprintf(prep->prep_origaddr));
1391                         return;
1392                 }
1393
1394                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1395                     "propagate PREP from %s",
1396                     ether_sprintf(prep->prep_targetaddr));
1397
1398                 memcpy(&pprep, prep, sizeof(pprep));
1399                 pprep.prep_hopcount += 1;
1400                 pprep.prep_ttl -= 1;
1401                 pprep.prep_metric += ms->ms_pmetric->mpm_metric(ni);
1402                 hwmp_send_prep(vap, rtorig->rt_nexthop, &pprep);
1403
1404                 /* precursor list for the Target Mesh STA Address is updated */
1405         }
1406
1407         /*
1408          * Check if we received a PREP w/ AE and store target external address.
1409          * We may store target external address if recevied PREP w/ AE
1410          * and we are not final destination
1411          */
1412         if (prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE) {
1413                 rtext = ieee80211_mesh_rt_find(vap,
1414                         prep->prep_target_ext_addr);
1415                 if (rtext == NULL) {
1416                         rtext = ieee80211_mesh_rt_add(vap,
1417                                 prep->prep_target_ext_addr);
1418                         if (rtext == NULL) {
1419                                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1420                                     "unable to add PREP path to proxy %s",
1421                                     ether_sprintf(prep->prep_targetaddr));
1422                                 vap->iv_stats.is_mesh_rtaddfailed++;
1423                                 return;
1424                         }
1425                 }
1426                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1427                     "%s path to %s, hopcount %d:%d metric %d:%d",
1428                     rtext->rt_flags & IEEE80211_MESHRT_FLAGS_VALID ?
1429                     "prefer" : "update",
1430                     ether_sprintf(prep->prep_target_ext_addr),
1431                     rtext->rt_nhops, prep->prep_hopcount + 1,
1432                     rtext->rt_metric, metric);
1433
1434                 rtext->rt_flags = IEEE80211_MESHRT_FLAGS_PROXY |
1435                         IEEE80211_MESHRT_FLAGS_VALID;
1436                 IEEE80211_ADDR_COPY(rtext->rt_dest,
1437                     prep->prep_target_ext_addr);
1438                 IEEE80211_ADDR_COPY(rtext->rt_mesh_gate,
1439                     prep->prep_targetaddr);
1440                 IEEE80211_ADDR_COPY(rtext->rt_nexthop, wh->i_addr2);
1441                 rtext->rt_metric = metric;
1442                 rtext->rt_lifetime = prep->prep_lifetime;
1443                 rtext->rt_nhops = prep->prep_hopcount + 1;
1444                 rtext->rt_ext_seq = prep->prep_origseq; /* new proxy seq */
1445                 /*
1446                  * XXX: proxy entries have no HWMP priv data,
1447                  * nullify them to be sure?
1448                  */
1449         }
1450         /*
1451          * Check for frames queued awaiting path discovery.
1452          * XXX probably can tell exactly and avoid remove call
1453          * NB: hash may have false matches, if so they will get
1454          *     stuck back on the stageq because there won't be
1455          *     a path.
1456          */
1457         addr = prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE ?
1458             prep->prep_target_ext_addr : prep->prep_targetaddr;
1459         m = ieee80211_ageq_remove(&ic->ic_stageq,
1460             (struct ieee80211_node *)(uintptr_t)
1461             ieee80211_mac_hash(ic, addr)); /* either dest or ext_dest */
1462
1463         /*
1464          * All frames in the stageq here should be non-M_ENCAP; or things
1465          * will get very unhappy.
1466          */
1467         for (; m != NULL; m = next) {
1468                 next = m->m_nextpkt;
1469                 m->m_nextpkt = NULL;
1470                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1471                     "flush queued frame %p len %d", m, m->m_pkthdr.len);
1472                 /*
1473                  * If the mbuf has M_ENCAP set, ensure we free it.
1474                  * Note that after if_transmit() is called, m is invalid.
1475                  */
1476                 (void) ieee80211_vap_xmitpkt(vap, m);
1477         }
1478 #undef  IS_PROXY
1479 #undef  PROXIED_BY_US
1480 }
1481
1482 static int
1483 hwmp_send_prep(struct ieee80211vap *vap,
1484     const uint8_t da[IEEE80211_ADDR_LEN],
1485     struct ieee80211_meshprep_ie *prep)
1486 {
1487         /* NB: there's no PREP minimum interval. */
1488
1489         /*
1490          * mesh prep action frame format
1491          *     [6] da
1492          *     [6] sa
1493          *     [6] addr3 = sa
1494          *     [1] action
1495          *     [1] category
1496          *     [tlv] mesh path reply
1497          */
1498         prep->prep_ie = IEEE80211_ELEMID_MESHPREP;
1499         prep->prep_len = prep->prep_flags & IEEE80211_MESHPREP_FLAGS_AE ?
1500             IEEE80211_MESHPREP_BASE_SZ_AE : IEEE80211_MESHPREP_BASE_SZ;
1501         return hwmp_send_action(vap, da, (uint8_t *)prep, prep->prep_len + 2);
1502 }
1503
1504 #define PERR_DFLAGS(n)  perr.perr_dests[n].dest_flags
1505 #define PERR_DADDR(n)   perr.perr_dests[n].dest_addr
1506 #define PERR_DSEQ(n)    perr.perr_dests[n].dest_seq
1507 #define PERR_DRCODE(n)  perr.perr_dests[n].dest_rcode
1508 static void
1509 hwmp_peerdown(struct ieee80211_node *ni)
1510 {
1511         struct ieee80211vap *vap = ni->ni_vap;
1512         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1513         struct ieee80211_meshperr_ie perr;
1514         struct ieee80211_mesh_route *rt;
1515         struct ieee80211_hwmp_route *hr;
1516
1517         rt = ieee80211_mesh_rt_find(vap, ni->ni_macaddr);
1518         if (rt == NULL)
1519                 return;
1520         hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1521         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1522             "%s", "delete route entry");
1523         perr.perr_ttl = ms->ms_ttl;
1524         perr.perr_ndests = 1;
1525         PERR_DFLAGS(0) = 0;
1526         if (hr->hr_seq == 0)
1527                 PERR_DFLAGS(0) |= IEEE80211_MESHPERR_DFLAGS_USN;
1528         PERR_DFLAGS(0) |= IEEE80211_MESHPERR_DFLAGS_RC;
1529         IEEE80211_ADDR_COPY(PERR_DADDR(0), rt->rt_dest);
1530         PERR_DSEQ(0) = ++hr->hr_seq;
1531         PERR_DRCODE(0) = IEEE80211_REASON_MESH_PERR_DEST_UNREACH;
1532         /* NB: flush everything passing through peer */
1533         ieee80211_mesh_rt_flush_peer(vap, ni->ni_macaddr);
1534         hwmp_send_perr(vap, broadcastaddr, &perr);
1535 }
1536 #undef  PERR_DFLAGS
1537 #undef  PERR_DADDR
1538 #undef  PERR_DSEQ
1539 #undef  PERR_DRCODE
1540
1541 #define PERR_DFLAGS(n)          perr->perr_dests[n].dest_flags
1542 #define PERR_DADDR(n)           perr->perr_dests[n].dest_addr
1543 #define PERR_DSEQ(n)            perr->perr_dests[n].dest_seq
1544 #define PERR_DEXTADDR(n)        perr->perr_dests[n].dest_ext_addr
1545 #define PERR_DRCODE(n)          perr->perr_dests[n].dest_rcode
1546 static void
1547 hwmp_recv_perr(struct ieee80211vap *vap, struct ieee80211_node *ni,
1548     const struct ieee80211_frame *wh, const struct ieee80211_meshperr_ie *perr)
1549 {
1550         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1551         struct ieee80211_mesh_route *rt = NULL;
1552         struct ieee80211_mesh_route *rt_ext = NULL;
1553         struct ieee80211_hwmp_route *hr;
1554         struct ieee80211_meshperr_ie *pperr = NULL;
1555         int i, j = 0, forward = 0;
1556
1557         IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1558             "received PERR from %s", ether_sprintf(wh->i_addr2));
1559
1560         /*
1561          * if forwarding is true, prepare pperr
1562          */
1563         if (ms->ms_flags & IEEE80211_MESHFLAGS_FWD) {
1564                 forward = 1;
1565                 pperr = kmalloc(sizeof(*perr) + 31*sizeof(*perr->perr_dests),
1566                     M_80211_MESH_PERR, M_INTWAIT); /* XXX: magic number, 32 err dests */
1567         }
1568
1569         /*
1570          * Acceptance criteria: check if we have forwarding information
1571          * stored about destination, and that nexthop == TA of this PERR.
1572          * NB: we also build a new PERR to propagate in case we should forward.
1573          */
1574         for (i = 0; i < perr->perr_ndests; i++) {
1575                 rt = ieee80211_mesh_rt_find(vap, PERR_DADDR(i));
1576                 if (rt == NULL)
1577                         continue;
1578                 if (!IEEE80211_ADDR_EQ(rt->rt_nexthop, wh->i_addr2))
1579                         continue;
1580
1581                 /* found and accepted a PERR ndest element, process it... */
1582                 if (forward)
1583                         memcpy(&pperr->perr_dests[j], &perr->perr_dests[i],
1584                             sizeof(*perr->perr_dests));
1585                 hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1586                 switch(PERR_DFLAGS(i)) {
1587                 case (IEEE80211_REASON_MESH_PERR_NO_FI):
1588                         if (PERR_DSEQ(i) == 0) {
1589                                 hr->hr_seq++;
1590                                 if (forward) {
1591                                         pperr->perr_dests[j].dest_seq =
1592                                             hr->hr_seq;
1593                                 }
1594                         } else {
1595                                 hr->hr_seq = PERR_DSEQ(i);
1596                         }
1597                         rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_VALID;
1598                         j++;
1599                         break;
1600                 case (IEEE80211_REASON_MESH_PERR_DEST_UNREACH):
1601                         if(HWMP_SEQ_GT(PERR_DSEQ(i), hr->hr_seq)) {
1602                                 hr->hr_seq = PERR_DSEQ(i);
1603                                 rt->rt_flags &= ~IEEE80211_MESHRT_FLAGS_VALID;
1604                                 j++;
1605                         }
1606                         break;
1607                 case (IEEE80211_REASON_MESH_PERR_NO_PROXY):
1608                         rt_ext = ieee80211_mesh_rt_find(vap, PERR_DEXTADDR(i));
1609                         if (rt_ext != NULL) {
1610                                 rt_ext->rt_flags &=
1611                                     ~IEEE80211_MESHRT_FLAGS_VALID;
1612                                 j++;
1613                         }
1614                         break;
1615                 default:
1616                         IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1617                             "PERR, unknown reason code %u\n", PERR_DFLAGS(i));
1618                         goto done; /* XXX: stats?? */
1619                 }
1620                 ieee80211_mesh_rt_flush_peer(vap, PERR_DADDR(i));
1621                 KASSERT(j < 32, ("PERR, error ndest >= 32 (%u)", j));
1622         }
1623         if (j == 0) {
1624                 IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL, "%s",
1625                     "PERR not accepted");
1626                 goto done; /* XXX: stats?? */
1627         }
1628
1629         /*
1630          * Propagate the PERR if we previously found it on our routing table.
1631          */
1632         if (forward && perr->perr_ttl > 1) {
1633                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP, ni,
1634                     "propagate PERR from %s", ether_sprintf(wh->i_addr2));
1635                 pperr->perr_ndests = j;
1636                 pperr->perr_ttl--;
1637                 hwmp_send_perr(vap, broadcastaddr, pperr);
1638         }
1639 done:
1640         if (pperr != NULL)
1641                 kfree(pperr, M_80211_MESH_PERR);
1642 }
1643 #undef  PERR_DFLAGS
1644 #undef  PERR_DADDR
1645 #undef  PERR_DSEQ
1646 #undef  PERR_DEXTADDR
1647 #undef  PERR_DRCODE
1648
1649 static int
1650 hwmp_send_perr(struct ieee80211vap *vap,
1651     const uint8_t da[IEEE80211_ADDR_LEN],
1652     struct ieee80211_meshperr_ie *perr)
1653 {
1654         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1655         int i;
1656         uint8_t length = 0;
1657
1658         /*
1659          * Enforce PERR interval.
1660          */
1661         if (ratecheck(&hs->hs_lastperr, &ieee80211_hwmp_perrminint) == 0)
1662                 return EALREADY;
1663         getmicrouptime(&hs->hs_lastperr);
1664
1665         /*
1666          * mesh perr action frame format
1667          *     [6] da
1668          *     [6] sa
1669          *     [6] addr3 = sa
1670          *     [1] action
1671          *     [1] category
1672          *     [tlv] mesh path error
1673          */
1674         perr->perr_ie = IEEE80211_ELEMID_MESHPERR;
1675         length = IEEE80211_MESHPERR_BASE_SZ;
1676         for (i = 0; i<perr->perr_ndests; i++) {
1677                 if (perr->perr_dests[i].dest_flags &
1678                     IEEE80211_MESHPERR_FLAGS_AE) {
1679                         length += IEEE80211_MESHPERR_DEST_SZ_AE;
1680                         continue ;
1681                 }
1682                 length += IEEE80211_MESHPERR_DEST_SZ;
1683         }
1684         perr->perr_len =length;
1685         return hwmp_send_action(vap, da, (uint8_t *)perr, perr->perr_len+2);
1686 }
1687
1688 /*
1689  * Called from the rest of the net80211 code (mesh code for example).
1690  * NB: IEEE80211_REASON_MESH_PERR_DEST_UNREACH can be trigger by the fact that
1691  * a mesh STA is unable to forward an MSDU/MMPDU to a next-hop mesh STA.
1692  */
1693 #define PERR_DFLAGS(n)          perr.perr_dests[n].dest_flags
1694 #define PERR_DADDR(n)           perr.perr_dests[n].dest_addr
1695 #define PERR_DSEQ(n)            perr.perr_dests[n].dest_seq
1696 #define PERR_DEXTADDR(n)        perr.perr_dests[n].dest_ext_addr
1697 #define PERR_DRCODE(n)          perr.perr_dests[n].dest_rcode
1698 static void
1699 hwmp_senderror(struct ieee80211vap *vap,
1700     const uint8_t addr[IEEE80211_ADDR_LEN],
1701     struct ieee80211_mesh_route *rt, int rcode)
1702 {
1703         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1704         struct ieee80211_hwmp_route *hr = NULL;
1705         struct ieee80211_meshperr_ie perr;
1706
1707         if (rt != NULL)
1708                 hr = IEEE80211_MESH_ROUTE_PRIV(rt,
1709                     struct ieee80211_hwmp_route);
1710
1711         perr.perr_ndests = 1;
1712         perr.perr_ttl = ms->ms_ttl;
1713         PERR_DFLAGS(0) = 0;
1714         PERR_DRCODE(0) = rcode;
1715
1716         switch (rcode) {
1717         case IEEE80211_REASON_MESH_PERR_NO_FI:
1718                 IEEE80211_ADDR_COPY(PERR_DADDR(0), addr);
1719                 PERR_DSEQ(0) = 0; /* reserved */
1720                 break;
1721         case IEEE80211_REASON_MESH_PERR_NO_PROXY:
1722                 KASSERT(rt != NULL, ("no proxy info for sending PERR"));
1723                 KASSERT(rt->rt_flags & IEEE80211_MESHRT_FLAGS_PROXY,
1724                     ("route is not marked proxy"));
1725                 PERR_DFLAGS(0) |= IEEE80211_MESHPERR_FLAGS_AE;
1726                 IEEE80211_ADDR_COPY(PERR_DADDR(0), vap->iv_myaddr);
1727                 PERR_DSEQ(0) = rt->rt_ext_seq;
1728                 IEEE80211_ADDR_COPY(PERR_DEXTADDR(0), addr);
1729                 break;
1730         case IEEE80211_REASON_MESH_PERR_DEST_UNREACH:
1731                 KASSERT(rt != NULL, ("no route info for sending PERR"));
1732                 IEEE80211_ADDR_COPY(PERR_DADDR(0), addr);
1733                 PERR_DSEQ(0) = hr->hr_seq;
1734                 break;
1735         default:
1736                 KASSERT(0, ("unknown reason code for HWMP PERR (%u)", rcode));
1737         }
1738         hwmp_send_perr(vap, broadcastaddr, &perr);
1739 }
1740 #undef  PERR_DFLAGS
1741 #undef  PEER_DADDR
1742 #undef  PERR_DSEQ
1743 #undef  PERR_DEXTADDR
1744 #undef  PERR_DRCODE
1745
1746 static void
1747 hwmp_recv_rann(struct ieee80211vap *vap, struct ieee80211_node *ni,
1748     const struct ieee80211_frame *wh, const struct ieee80211_meshrann_ie *rann)
1749 {
1750         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1751         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1752         struct ieee80211_mesh_route *rt = NULL;
1753         struct ieee80211_hwmp_route *hr;
1754         struct ieee80211_meshpreq_ie preq;
1755         struct ieee80211_meshrann_ie prann;
1756         uint32_t metric = 0;
1757
1758         if (IEEE80211_ADDR_EQ(rann->rann_addr, vap->iv_myaddr))
1759                 return;
1760
1761         rt = ieee80211_mesh_rt_find(vap, rann->rann_addr);
1762         if (rt != NULL && rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) {
1763                 hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1764
1765                 /* Acceptance criteria: if RANN.seq < stored seq, discard RANN */
1766                 if (HWMP_SEQ_LT(rann->rann_seq, hr->hr_seq)) {
1767                         IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1768                         "RANN seq %u < %u", rann->rann_seq, hr->hr_seq);
1769                         return;
1770                 }
1771
1772                 /* Acceptance criteria: if RANN.seq == stored seq AND
1773                 * RANN.metric > stored metric, discard RANN */
1774                 if (HWMP_SEQ_EQ(rann->rann_seq, hr->hr_seq) &&
1775                 rann->rann_metric > rt->rt_metric) {
1776                         IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1777                         "RANN metric %u > %u", rann->rann_metric, rt->rt_metric);
1778                         return;
1779                 }
1780         }
1781
1782         /* RANN ACCEPTED */
1783
1784         ieee80211_hwmp_rannint = rann->rann_interval; /* XXX: mtx lock? */
1785         metric = rann->rann_metric + ms->ms_pmetric->mpm_metric(ni);
1786
1787         if (rt == NULL) {
1788                 rt = ieee80211_mesh_rt_add(vap, rann->rann_addr);
1789                 if (rt == NULL) {
1790                         IEEE80211_DISCARD(vap, IEEE80211_MSG_HWMP, wh, NULL,
1791                             "unable to add mac for RANN root %s",
1792                             ether_sprintf(rann->rann_addr));
1793                             vap->iv_stats.is_mesh_rtaddfailed++;
1794                         return;
1795                 }
1796         }
1797         hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1798         /* Check if root is a mesh gate, mark it */
1799         if (rann->rann_flags & IEEE80211_MESHRANN_FLAGS_GATE) {
1800                 struct ieee80211_mesh_gate_route *gr;
1801
1802                 rt->rt_flags |= IEEE80211_MESHRT_FLAGS_GATE;
1803                 gr = ieee80211_mesh_mark_gate(vap, rann->rann_addr,
1804                         rt);
1805                 gr->gr_lastseq = 0; /* NOT GANN */
1806         }
1807         /* discovery timeout */
1808         ieee80211_mesh_rt_update(rt,
1809             ticks_to_msecs(ieee80211_hwmp_roottimeout));
1810
1811         preq.preq_flags = IEEE80211_MESHPREQ_FLAGS_AM;
1812         preq.preq_hopcount = 0;
1813         preq.preq_ttl = ms->ms_ttl;
1814         preq.preq_id = 0; /* reserved */
1815         IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1816         preq.preq_origseq = ++hs->hs_seq;
1817         preq.preq_lifetime = ieee80211_hwmp_roottimeout;
1818         preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1819         preq.preq_tcount = 1;
1820         preq.preq_targets[0].target_flags = IEEE80211_MESHPREQ_TFLAGS_TO;
1821         /* NB: IEEE80211_MESHPREQ_TFLAGS_USN = 0 implicitly implied */
1822         IEEE80211_ADDR_COPY(preq.preq_targets[0].target_addr, rann->rann_addr);
1823         preq.preq_targets[0].target_seq = rann->rann_seq;
1824         /* XXX: if rootconfint have not passed, we built this preq in vain */
1825         hwmp_send_preq(vap, wh->i_addr2, &preq, &hr->hr_lastrootconf,
1826             &ieee80211_hwmp_rootconfint);
1827
1828         /* propagate a RANN */
1829         if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID &&
1830             rann->rann_ttl > 1 &&
1831             ms->ms_flags & IEEE80211_MESHFLAGS_FWD) {
1832                 hr->hr_seq = rann->rann_seq;
1833                 memcpy(&prann, rann, sizeof(prann));
1834                 prann.rann_hopcount += 1;
1835                 prann.rann_ttl -= 1;
1836                 prann.rann_metric += ms->ms_pmetric->mpm_metric(ni);
1837                 hwmp_send_rann(vap, broadcastaddr, &prann);
1838         }
1839 }
1840
1841 static int
1842 hwmp_send_rann(struct ieee80211vap *vap,
1843     const uint8_t da[IEEE80211_ADDR_LEN],
1844     struct ieee80211_meshrann_ie *rann)
1845 {
1846         /*
1847          * mesh rann action frame format
1848          *     [6] da
1849          *     [6] sa
1850          *     [6] addr3 = sa
1851          *     [1] action
1852          *     [1] category
1853          *     [tlv] root annoucement
1854          */
1855         rann->rann_ie = IEEE80211_ELEMID_MESHRANN;
1856         rann->rann_len = IEEE80211_MESHRANN_BASE_SZ;
1857         return hwmp_send_action(vap, da, (uint8_t *)rann, rann->rann_len + 2);
1858 }
1859
1860 #define PREQ_TFLAGS(n)  preq.preq_targets[n].target_flags
1861 #define PREQ_TADDR(n)   preq.preq_targets[n].target_addr
1862 #define PREQ_TSEQ(n)    preq.preq_targets[n].target_seq
1863 static void
1864 hwmp_rediscover_cb(void *arg)
1865 {
1866         struct ieee80211_mesh_route *rt = arg;
1867         struct ieee80211vap *vap = rt->rt_vap;
1868         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1869         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1870         struct ieee80211_hwmp_route *hr;
1871         struct ieee80211_meshpreq_ie preq; /* Optimize: storing first preq? */
1872
1873         if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID))
1874                 return ; /* nothing to do */
1875
1876         hr = IEEE80211_MESH_ROUTE_PRIV(rt, struct ieee80211_hwmp_route);
1877         if (hr->hr_preqretries >=
1878                 ieee80211_hwmp_maxpreq_retries) {
1879                 IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_ANY,
1880                         rt->rt_dest, "%s",
1881                         "max number of discovery, send queued frames to GATE");
1882                 ieee80211_mesh_forward_to_gates(vap, rt);
1883                 vap->iv_stats.is_mesh_fwd_nopath++;
1884                 return ; /* XXX: flush queue? */
1885         }
1886
1887         hr->hr_preqretries++;
1888
1889
1890         IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, rt->rt_dest,
1891             "start path rediscovery , target seq %u", hr->hr_seq);
1892         /*
1893          * Try to discover the path for this node.
1894          * Group addressed PREQ Case A
1895          */
1896         preq.preq_flags = 0;
1897         preq.preq_hopcount = 0;
1898         preq.preq_ttl = ms->ms_ttl;
1899         preq.preq_id = ++hs->hs_preqid;
1900         IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1901         preq.preq_origseq = hr->hr_origseq;
1902         preq.preq_lifetime = ticks_to_msecs(ieee80211_hwmp_pathtimeout);
1903         preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1904         preq.preq_tcount = 1;
1905         IEEE80211_ADDR_COPY(PREQ_TADDR(0), rt->rt_dest);
1906         PREQ_TFLAGS(0) = 0;
1907         if (ieee80211_hwmp_targetonly)
1908                 PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_TO;
1909         PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_USN;
1910         PREQ_TSEQ(0) = 0; /* RESERVED when USN flag is set */
1911         /* XXX check return value */
1912         hwmp_send_preq(vap, broadcastaddr, &preq, &hr->hr_lastpreq,
1913             &ieee80211_hwmp_preqminint);
1914         callout_reset(&rt->rt_discovery,
1915                 ieee80211_hwmp_net_diameter_traversaltime * 2,
1916                 hwmp_rediscover_cb, rt);
1917 }
1918
1919 static struct ieee80211_node *
1920 hwmp_discover(struct ieee80211vap *vap,
1921     const uint8_t dest[IEEE80211_ADDR_LEN], struct mbuf *m)
1922 {
1923         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
1924         struct ieee80211_mesh_state *ms = vap->iv_mesh;
1925         struct ieee80211_mesh_route *rt = NULL;
1926         struct ieee80211_hwmp_route *hr;
1927         struct ieee80211_meshpreq_ie preq;
1928         struct ieee80211_node *ni;
1929         int sendpreq = 0;
1930
1931         KASSERT(vap->iv_opmode == IEEE80211_M_MBSS,
1932             ("not a mesh vap, opmode %d", vap->iv_opmode));
1933
1934         KASSERT(!IEEE80211_ADDR_EQ(vap->iv_myaddr, dest),
1935             ("%s: discovering self!", __func__));
1936
1937         ni = NULL;
1938         if (!IEEE80211_IS_MULTICAST(dest)) {
1939                 rt = ieee80211_mesh_rt_find(vap, dest);
1940                 if (rt == NULL) {
1941                         rt = ieee80211_mesh_rt_add(vap, dest);
1942                         if (rt == NULL) {
1943                                 IEEE80211_NOTE(vap, IEEE80211_MSG_HWMP,
1944                                     ni, "unable to add discovery path to %s",
1945                                     ether_sprintf(dest));
1946                                 vap->iv_stats.is_mesh_rtaddfailed++;
1947                                 goto done;
1948                         }
1949                 }
1950                 hr = IEEE80211_MESH_ROUTE_PRIV(rt,
1951                     struct ieee80211_hwmp_route);
1952                 if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_DISCOVER) {
1953                         IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
1954                             "%s", "already discovering queue frame until path found");
1955                         sendpreq = 1;
1956                         goto done;
1957                 }
1958                 if ((rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID) == 0) {
1959                         if (hr->hr_lastdiscovery != 0 &&
1960                             (ticks - hr->hr_lastdiscovery <
1961                             (ieee80211_hwmp_net_diameter_traversaltime * 2))) {
1962                                 IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_ANY,
1963                                     dest, NULL, "%s",
1964                                     "too frequent discovery requeust");
1965                                 sendpreq = 1;
1966                                 goto done;
1967                         }
1968                         hr->hr_lastdiscovery = ticks;
1969                         if (hr->hr_preqretries >=
1970                             ieee80211_hwmp_maxpreq_retries) {
1971                                 IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_ANY,
1972                                     dest, NULL, "%s",
1973                                     "no valid path , max number of discovery");
1974                                 vap->iv_stats.is_mesh_fwd_nopath++;
1975                                 goto done;
1976                         }
1977                         rt->rt_flags = IEEE80211_MESHRT_FLAGS_DISCOVER;
1978                         hr->hr_preqretries++;
1979                         if (hr->hr_origseq == 0)
1980                                 hr->hr_origseq = ++hs->hs_seq;
1981                         rt->rt_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
1982                         sendpreq = 1;
1983                         IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
1984                             "start path discovery (src %s), target seq %u",
1985                             m == NULL ? "<none>" : ether_sprintf(
1986                             mtod(m, struct ether_header *)->ether_shost),
1987                             hr->hr_seq);
1988                         /*
1989                          * Try to discover the path for this node.
1990                          * Group addressed PREQ Case A
1991                          */
1992                         preq.preq_flags = 0;
1993                         preq.preq_hopcount = 0;
1994                         preq.preq_ttl = ms->ms_ttl;
1995                         preq.preq_id = ++hs->hs_preqid;
1996                         IEEE80211_ADDR_COPY(preq.preq_origaddr, vap->iv_myaddr);
1997                         preq.preq_origseq = hr->hr_origseq;
1998                         preq.preq_lifetime =
1999                             ticks_to_msecs(ieee80211_hwmp_pathtimeout);
2000                         preq.preq_metric = IEEE80211_MESHLMETRIC_INITIALVAL;
2001                         preq.preq_tcount = 1;
2002                         IEEE80211_ADDR_COPY(PREQ_TADDR(0), dest);
2003                         PREQ_TFLAGS(0) = 0;
2004                         if (ieee80211_hwmp_targetonly)
2005                                 PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_TO;
2006                         PREQ_TFLAGS(0) |= IEEE80211_MESHPREQ_TFLAGS_USN;
2007                         PREQ_TSEQ(0) = 0; /* RESERVED when USN flag is set */
2008                         /* XXX check return value */
2009                         hwmp_send_preq(vap, broadcastaddr, &preq,
2010                             &hr->hr_lastpreq, &ieee80211_hwmp_preqminint);
2011                         callout_reset(&rt->rt_discovery,
2012                             ieee80211_hwmp_net_diameter_traversaltime * 2,
2013                             hwmp_rediscover_cb, rt);
2014                 }
2015                 if (rt->rt_flags & IEEE80211_MESHRT_FLAGS_VALID)
2016                         ni = ieee80211_find_txnode(vap, rt->rt_nexthop);
2017         } else {
2018                 ni = ieee80211_find_txnode(vap, dest);
2019                 /* NB: if null then we leak mbuf */
2020                 KASSERT(ni != NULL, ("leak mcast frame"));
2021                 return ni;
2022         }
2023 done:
2024         if (ni == NULL && m != NULL) {
2025                 if (sendpreq) {
2026                         struct ieee80211com *ic = vap->iv_ic;
2027                         /*
2028                          * Queue packet for transmit when path discovery
2029                          * completes.  If discovery never completes the
2030                          * frame will be flushed by way of the aging timer.
2031                          */
2032                         IEEE80211_NOTE_MAC(vap, IEEE80211_MSG_HWMP, dest,
2033                             "%s", "queue frame until path found");
2034                         m->m_pkthdr.rcvif = (void *)(uintptr_t)
2035                             ieee80211_mac_hash(ic, dest);
2036                         /* XXX age chosen randomly */
2037                         ieee80211_ageq_append(&ic->ic_stageq, m,
2038                             IEEE80211_INACT_WAIT);
2039                 } else {
2040                         IEEE80211_DISCARD_MAC(vap, IEEE80211_MSG_HWMP,
2041                             dest, NULL, "%s", "no valid path to this node");
2042                         m_freem(m);
2043                 }
2044         }
2045         return ni;
2046 }
2047 #undef  PREQ_TFLAGS
2048 #undef  PREQ_TADDR
2049 #undef  PREQ_TSEQ
2050
2051 static int
2052 hwmp_ioctl_get80211(struct ieee80211vap *vap, struct ieee80211req *ireq)
2053 {
2054         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
2055         int error;
2056
2057         if (vap->iv_opmode != IEEE80211_M_MBSS)
2058                 return ENOSYS;
2059         error = 0;
2060         switch (ireq->i_type) {
2061         case IEEE80211_IOC_HWMP_ROOTMODE:
2062                 ireq->i_val = hs->hs_rootmode;
2063                 break;
2064         case IEEE80211_IOC_HWMP_MAXHOPS:
2065                 ireq->i_val = hs->hs_maxhops;
2066                 break;
2067         default:
2068                 return ENOSYS;
2069         }
2070         return error;
2071 }
2072 IEEE80211_IOCTL_GET(hwmp, hwmp_ioctl_get80211);
2073
2074 static int
2075 hwmp_ioctl_set80211(struct ieee80211vap *vap, struct ieee80211req *ireq)
2076 {
2077         struct ieee80211_hwmp_state *hs = vap->iv_hwmp;
2078         int error;
2079
2080         if (vap->iv_opmode != IEEE80211_M_MBSS)
2081                 return ENOSYS;
2082         error = 0;
2083         switch (ireq->i_type) {
2084         case IEEE80211_IOC_HWMP_ROOTMODE:
2085                 if (ireq->i_val < 0 || ireq->i_val > 3)
2086                         return EINVAL;
2087                 hs->hs_rootmode = ireq->i_val;
2088                 hwmp_rootmode_setup(vap);
2089                 break;
2090         case IEEE80211_IOC_HWMP_MAXHOPS:
2091                 if (ireq->i_val <= 0 || ireq->i_val > 255)
2092                         return EINVAL;
2093                 hs->hs_maxhops = ireq->i_val;
2094                 break;
2095         default:
2096                 return ENOSYS;
2097         }
2098         return error;
2099 }
2100 IEEE80211_IOCTL_SET(hwmp, hwmp_ioctl_set80211);