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 */ 27 28 /* 29 * IEEE 802.11 age queue support. 30 */ 31 #include "opt_wlan.h" 32 33 #include <sys/param.h> 34 #include <sys/systm.h> 35 #include <sys/kernel.h> 36 37 #include <sys/socket.h> 38 39 #include <net/if.h> 40 #include <net/if_media.h> 41 #include <net/ethernet.h> 42 #include <net/route.h> 43 44 #include <netproto/802_11/ieee80211_var.h> 45 46 /* 47 * Initialize an ageq. 48 */ 49 void 50 ieee80211_ageq_init(struct ieee80211_ageq *aq, int maxlen, const char *name) 51 { 52 memset(aq, 0, sizeof(*aq)); 53 aq->aq_maxlen = maxlen; 54 } 55 56 /* 57 * Cleanup an ageq initialized with ieee80211_ageq_init. Note 58 * the queue is assumed empty; this can be done with ieee80211_ageq_drain. 59 */ 60 void 61 ieee80211_ageq_cleanup(struct ieee80211_ageq *aq) 62 { 63 KASSERT(aq->aq_len == 0, ("%d frames on ageq", aq->aq_len)); 64 } 65 66 /* 67 * Free an mbuf according to ageq rules: if marked as holding 68 * and 802.11 frame then also reclaim a node reference from 69 * the packet header; this handles packets q'd in the tx path. 70 */ 71 static void 72 ageq_mfree(struct mbuf *m) 73 { 74 if (m->m_flags & M_ENCAP) { 75 struct ieee80211_node *ni = (void *) m->m_pkthdr.rcvif; 76 ieee80211_free_node(ni); 77 } 78 m->m_nextpkt = NULL; 79 m_freem(m); 80 } 81 82 /* 83 * Free a list of mbufs using ageq rules (see above). 84 */ 85 void 86 ieee80211_ageq_mfree(struct mbuf *m) 87 { 88 struct mbuf *next; 89 90 for (; m != NULL; m = next) { 91 next = m->m_nextpkt; 92 ageq_mfree(m); 93 } 94 } 95 96 /* 97 * Append an mbuf to the ageq and mark it with the specified max age 98 * If the frame is not removed before the age (in seconds) expires 99 * then it is reclaimed (along with any node reference). 100 */ 101 int 102 ieee80211_ageq_append(struct ieee80211_ageq *aq, struct mbuf *m, int age) 103 { 104 if (__predict_true(aq->aq_len < aq->aq_maxlen)) { 105 if (aq->aq_tail == NULL) { 106 aq->aq_head = m; 107 } else { 108 aq->aq_tail->m_nextpkt = m; 109 age -= M_AGE_GET(aq->aq_head); 110 } 111 KASSERT(age >= 0, ("age %d", age)); 112 M_AGE_SET(m, age); 113 m->m_nextpkt = NULL; 114 aq->aq_tail = m; 115 aq->aq_len++; 116 return 0; 117 } else { 118 /* 119 * No space, drop and cleanup references. 120 */ 121 aq->aq_drops++; 122 /* XXX tail drop? */ 123 ageq_mfree(m); 124 return ENOSPC; 125 } 126 } 127 128 /* 129 * Drain/reclaim all frames from an ageq. 130 */ 131 void 132 ieee80211_ageq_drain(struct ieee80211_ageq *aq) 133 { 134 ieee80211_ageq_mfree(ieee80211_ageq_remove(aq, NULL)); 135 } 136 137 /* 138 * Drain/reclaim frames associated with a specific node from an ageq. 139 */ 140 void 141 ieee80211_ageq_drain_node(struct ieee80211_ageq *aq, 142 struct ieee80211_node *ni) 143 { 144 ieee80211_ageq_mfree(ieee80211_ageq_remove(aq, ni)); 145 } 146 147 /* 148 * Age frames on the age queue. Ages are stored as time 149 * deltas (in seconds) relative to the head so we can check 150 * and/or adjust only the head of the list. If a frame's age 151 * exceeds the time quanta then remove it. The list of removed 152 * frames is is returned to the caller joined by m_nextpkt. 153 */ 154 struct mbuf * 155 ieee80211_ageq_age(struct ieee80211_ageq *aq, int quanta) 156 { 157 struct mbuf *head, **phead; 158 struct mbuf *m; 159 160 phead = &head; 161 if (aq->aq_len != 0) { 162 while ((m = aq->aq_head) != NULL && M_AGE_GET(m) < quanta) { 163 if ((aq->aq_head = m->m_nextpkt) == NULL) 164 aq->aq_tail = NULL; 165 KASSERT(aq->aq_len > 0, ("aq len %d", aq->aq_len)); 166 aq->aq_len--; 167 /* add to private list for return */ 168 *phead = m; 169 phead = &m->m_nextpkt; 170 } 171 if (m != NULL) 172 M_AGE_SUB(m, quanta); 173 } 174 *phead = NULL; 175 return head; 176 } 177 178 /* 179 * Remove all frames matching the specified node identifier 180 * (NULL matches all). Frames are returned as a list joined 181 * by m_nextpkt. 182 */ 183 struct mbuf * 184 ieee80211_ageq_remove(struct ieee80211_ageq *aq, 185 struct ieee80211_node *match) 186 { 187 struct mbuf *m, **prev, *ohead; 188 struct mbuf *head, **phead; 189 190 ohead = aq->aq_head; 191 prev = &aq->aq_head; 192 phead = &head; 193 while ((m = *prev) != NULL) { 194 if (match != NULL && m->m_pkthdr.rcvif != (void *) match) { 195 prev = &m->m_nextpkt; 196 continue; 197 } 198 /* 199 * Adjust q length. 200 */ 201 KASSERT(aq->aq_len > 0, ("aq len %d", aq->aq_len)); 202 aq->aq_len--; 203 /* 204 * Remove from forward list; tail pointer is harder. 205 */ 206 if (aq->aq_tail == m) { 207 KASSERT(m->m_nextpkt == NULL, ("not last")); 208 if (aq->aq_head == m) { /* list empty */ 209 KASSERT(aq->aq_len == 0, 210 ("not empty, len %d", aq->aq_len)); 211 aq->aq_tail = NULL; 212 } else { /* must be one before */ 213 aq->aq_tail = (struct mbuf *)((uintptr_t)prev - 214 offsetof(struct mbuf, m_nextpkt)); 215 } 216 } 217 *prev = m->m_nextpkt; 218 219 /* add to private list for return */ 220 *phead = m; 221 phead = &m->m_nextpkt; 222 } 223 if (head == ohead && aq->aq_head != NULL) /* correct age */ 224 M_AGE_SET(aq->aq_head, M_AGE_GET(head)); 225 226 *phead = NULL; 227 return head; 228 } 229