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