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

   1 /*-
   2  * Copyright (c) 2009 Sam Leffler, Errno Consulting
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  15  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  16  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  17  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  18  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  19  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  20  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  21  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  *
  25  * $FreeBSD: head/sys/net80211/ieee80211_ageq.c 195527 2009-07-10 02:19:57Z sam $
  26  * $DragonFly$
  27  */
  28
  29 /*
  30  * IEEE 802.11 age queue support.
  31  */
  32 #include "opt_wlan.h"
  33
  34 #include <sys/param.h>
  35 #include <sys/systm.h>
  36 #include <sys/kernel.h>
  37
  38 #include <sys/socket.h>
  39
  40 #include <net/if.h>
  41 #include <net/if_media.h>
  42 #include <net/ethernet.h>
  43 #include <net/route.h>
  44
  45 #include <netproto/802_11/ieee80211_var.h>
  46
  47 /*
  48  * Initialize an ageq.
  49  */
  50 void
  51 ieee80211_ageq_init(struct ieee80211_ageq *aq, int maxlen, const char *name)
  52 {
  53         memset(aq, 0, sizeof(aq));
  54         aq->aq_maxlen = maxlen;
  55         IEEE80211_AGEQ_INIT(aq, name);          /* OS-dependent setup */
  56 }
  57
  58 /*
  59  * Cleanup an ageq initialized with ieee80211_ageq_init.  Note
  60  * the queue is assumed empty; this can be done with ieee80211_ageq_drain.
  61  */
  62 void
  63 ieee80211_ageq_cleanup(struct ieee80211_ageq *aq)
  64 {
  65         KASSERT(aq->aq_len == 0, ("%d frames on ageq", aq->aq_len));
  66         IEEE80211_AGEQ_DESTROY(aq);             /* OS-dependent cleanup */
  67 }
  68
  69 /*
  70  * Free an mbuf according to ageq rules: if marked as holding
  71  * and 802.11 frame then also reclaim a node reference from
  72  * the packet header; this handles packets q'd in the tx path.
  73  */
  74 static void
  75 ageq_mfree(struct mbuf *m)
  76 {
  77         if (m->m_flags & M_ENCAP) {
  78                 struct ieee80211_node *ni = (void *) m->m_pkthdr.rcvif;
  79                 ieee80211_free_node(ni);
  80         }
  81         m->m_nextpkt = NULL;
  82         m_freem(m);
  83 }
  84
  85 /*
  86  * Free a list of mbufs using ageq rules (see above).
  87  */
  88 void
  89 ieee80211_ageq_mfree(struct mbuf *m)
  90 {
  91         struct mbuf *next;
  92
  93         for (; m != NULL; m = next) {
  94                 next = m->m_nextpkt;
  95                 ageq_mfree(m);
  96         }
  97 }
  98
  99 /*
 100  * Append an mbuf to the ageq and mark it with the specified max age
 101  * If the frame is not removed before the age (in seconds) expires
 102  * then it is reclaimed (along with any node reference).
 103  */
 104 int
 105 ieee80211_ageq_append(struct ieee80211_ageq *aq, struct mbuf *m, int age)
 106 {
 107         IEEE80211_AGEQ_LOCK(aq);
 108         if (__predict_true(aq->aq_len < aq->aq_maxlen)) {
 109                 if (aq->aq_tail == NULL) {
 110                         aq->aq_head = m;
 111                 } else {
 112                         aq->aq_tail->m_nextpkt = m;
 113                         age -= M_AGE_GET(aq->aq_head);
 114                 }
 115                 KASSERT(age >= 0, ("age %d", age));
 116                 M_AGE_SET(m, age);
 117                 m->m_nextpkt = NULL;
 118                 aq->aq_tail = m;
 119                 aq->aq_len++;
 120                 IEEE80211_AGEQ_UNLOCK(aq);
 121                 return 0;
 122         } else {
 123                 /*
 124                  * No space, drop and cleanup references.
 125                  */
 126                 aq->aq_drops++;
 127                 IEEE80211_AGEQ_UNLOCK(aq);
 128                 /* XXX tail drop? */
 129                 ageq_mfree(m);
 130                 return ENOSPC;
 131         }
 132 }
 133
 134 /*
 135  * Drain/reclaim all frames from an ageq.
 136  */
 137 void
 138 ieee80211_ageq_drain(struct ieee80211_ageq *aq)
 139 {
 140         ieee80211_ageq_mfree(ieee80211_ageq_remove(aq, NULL));
 141 }
 142
 143 /*
 144  * Drain/reclaim frames associated with a specific node from an ageq.
 145  */
 146 void
 147 ieee80211_ageq_drain_node(struct ieee80211_ageq *aq,
 148         struct ieee80211_node *ni)
 149 {
 150         ieee80211_ageq_mfree(ieee80211_ageq_remove(aq, ni));
 151 }
 152
 153 /*
 154  * Age frames on the age queue.  Ages are stored as time
 155  * deltas (in seconds) relative to the head so we can check
 156  * and/or adjust only the head of the list.  If a frame's age
 157  * exceeds the time quanta then remove it.  The list of removed
 158  * frames is is returned to the caller joined by m_nextpkt.
 159  */
 160 struct mbuf *
 161 ieee80211_ageq_age(struct ieee80211_ageq *aq, int quanta)
 162 {
 163         struct mbuf *head, **phead;
 164         struct mbuf *m;
 165
 166         phead = &head;
 167         if (aq->aq_len != 0) {
 168                 IEEE80211_AGEQ_LOCK(aq);
 169                 while ((m = aq->aq_head) != NULL && M_AGE_GET(m) < quanta) {
 170                         if ((aq->aq_head = m->m_nextpkt) == NULL)
 171                                 aq->aq_tail = NULL;
 172                         KASSERT(aq->aq_len > 0, ("aq len %d", aq->aq_len));
 173                         aq->aq_len--;
 174                         /* add to private list for return */
 175                         *phead = m;
 176                         phead = &m->m_nextpkt;
 177                 }
 178                 if (m != NULL)
 179                         M_AGE_SUB(m, quanta);
 180                 IEEE80211_AGEQ_UNLOCK(aq);
 181         }
 182         *phead = NULL;
 183         return head;
 184 }
 185
 186 /*
 187  * Remove all frames matching the specified node identifier
 188  * (NULL matches all).  Frames are returned as a list joined
 189  * by m_nextpkt.
 190  */
 191 struct mbuf *
 192 ieee80211_ageq_remove(struct ieee80211_ageq *aq,
 193         struct ieee80211_node *match)
 194 {
 195         struct mbuf *m, **prev, *ohead;
 196         struct mbuf *head, **phead;
 197
 198         IEEE80211_AGEQ_LOCK(aq);
 199         ohead = aq->aq_head;
 200         prev = &aq->aq_head;
 201         phead = &head;
 202         while ((m = *prev) != NULL) {
 203                 if (match != NULL && m->m_pkthdr.rcvif != (void *) match) {
 204                         prev = &m->m_nextpkt;
 205                         continue;
 206                 }
 207                 /*
 208                  * Adjust q length.
 209                  */
 210                 KASSERT(aq->aq_len > 0, ("aq len %d", aq->aq_len));
 211                 aq->aq_len--;
 212                 /*
 213                  * Remove from forward list; tail pointer is harder.
 214                  */
 215                 if (aq->aq_tail == m) {
 216                         KASSERT(m->m_nextpkt == NULL, ("not last"));
 217                         if (aq->aq_head == m) {         /* list empty */
 218                                 KASSERT(aq->aq_len == 0,
 219                                     ("not empty, len %d", aq->aq_len));
 220                                 aq->aq_tail = NULL;
 221                         } else {                        /* must be one before */
 222                                 aq->aq_tail = (struct mbuf *)((uintptr_t)prev -
 223                                     offsetof(struct mbuf, m_nextpkt));
 224                         }
 225                 }
 226                 *prev = m->m_nextpkt;
 227
 228                 /* add to private list for return */
 229                 *phead = m;
 230                 phead = &m->m_nextpkt;
 231         }
 232         if (head == ohead && aq->aq_head != NULL)       /* correct age */
 233                 M_AGE_SET(aq->aq_head, M_AGE_GET(head));
 234         IEEE80211_AGEQ_UNLOCK(aq);
 235
 236         *phead = NULL;
 237         return head;
 238 }