ip_reass.c revision 1.2 1 1.2 rmind /* $NetBSD: ip_reass.c,v 1.2 2010/07/19 14:09:45 rmind Exp $ */
2 1.1 rmind
3 1.1 rmind /*
4 1.1 rmind * Copyright (c) 1982, 1986, 1988, 1993
5 1.1 rmind * The Regents of the University of California. All rights reserved.
6 1.1 rmind *
7 1.1 rmind * Redistribution and use in source and binary forms, with or without
8 1.1 rmind * modification, are permitted provided that the following conditions
9 1.1 rmind * are met:
10 1.1 rmind * 1. Redistributions of source code must retain the above copyright
11 1.1 rmind * notice, this list of conditions and the following disclaimer.
12 1.1 rmind * 2. Redistributions in binary form must reproduce the above copyright
13 1.1 rmind * notice, this list of conditions and the following disclaimer in the
14 1.1 rmind * documentation and/or other materials provided with the distribution.
15 1.1 rmind * 3. Neither the name of the University nor the names of its contributors
16 1.1 rmind * may be used to endorse or promote products derived from this software
17 1.1 rmind * without specific prior written permission.
18 1.1 rmind *
19 1.1 rmind * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 1.1 rmind * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 1.1 rmind * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 1.1 rmind * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 1.1 rmind * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 1.1 rmind * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 1.1 rmind * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 1.1 rmind * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 1.1 rmind * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 1.1 rmind * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 1.1 rmind * SUCH DAMAGE.
30 1.1 rmind *
31 1.1 rmind * @(#)ip_input.c 8.2 (Berkeley) 1/4/94
32 1.1 rmind */
33 1.1 rmind
34 1.1 rmind /*
35 1.1 rmind * IP reassembly.
36 1.1 rmind *
37 1.1 rmind * Additive-Increase/Multiplicative-Decrease (AIMD) strategy for IP
38 1.1 rmind * reassembly queue buffer managment.
39 1.1 rmind *
40 1.1 rmind * We keep a count of total IP fragments (NB: not fragmented packets),
41 1.1 rmind * awaiting reassembly (ip_nfrags) and a limit (ip_maxfrags) on fragments.
42 1.1 rmind * If ip_nfrags exceeds ip_maxfrags the limit, we drop half the total
43 1.1 rmind * fragments in reassembly queues. This AIMD policy avoids repeatedly
44 1.1 rmind * deleting single packets under heavy fragmentation load (e.g., from lossy
45 1.1 rmind * NFS peers).
46 1.1 rmind */
47 1.1 rmind
48 1.1 rmind #include <sys/cdefs.h>
49 1.2 rmind __KERNEL_RCSID(0, "$NetBSD: ip_reass.c,v 1.2 2010/07/19 14:09:45 rmind Exp $");
50 1.1 rmind
51 1.1 rmind #include <sys/param.h>
52 1.2 rmind #include <sys/types.h>
53 1.1 rmind
54 1.1 rmind #include <sys/malloc.h>
55 1.1 rmind #include <sys/mbuf.h>
56 1.1 rmind #include <sys/domain.h>
57 1.1 rmind #include <sys/protosw.h>
58 1.1 rmind #include <sys/pool.h>
59 1.2 rmind #include <sys/queue.h>
60 1.1 rmind #include <sys/sysctl.h>
61 1.2 rmind #include <sys/systm.h>
62 1.1 rmind
63 1.1 rmind #include <net/if.h>
64 1.1 rmind #include <net/route.h>
65 1.1 rmind
66 1.1 rmind #include <netinet/in.h>
67 1.1 rmind #include <netinet/in_systm.h>
68 1.1 rmind #include <netinet/ip.h>
69 1.1 rmind #include <netinet/in_pcb.h>
70 1.2 rmind #include <netinet/ip_var.h>
71 1.1 rmind #include <netinet/in_proto.h>
72 1.1 rmind #include <netinet/ip_private.h>
73 1.1 rmind #include <netinet/in_var.h>
74 1.1 rmind
75 1.1 rmind /*
76 1.1 rmind * IP datagram reassembly hashed queues, pool, lock and counters.
77 1.1 rmind */
78 1.1 rmind #define IPREASS_HASH_SHIFT 6
79 1.1 rmind #define IPREASS_HASH_SIZE (1 << IPREASS_HASH_SHIFT)
80 1.1 rmind #define IPREASS_HASH_MASK (IPREASS_HASH_SIZE - 1)
81 1.1 rmind #define IPREASS_HASH(x, y) \
82 1.1 rmind (((((x) & 0xf) | ((((x) >> 8) & 0xf) << 4)) ^ (y)) & IPREASS_HASH_MASK)
83 1.1 rmind
84 1.1 rmind struct ipqhead ipq[IPREASS_HASH_SIZE];
85 1.1 rmind struct pool ipqent_pool;
86 1.1 rmind static int ipq_locked;
87 1.1 rmind
88 1.1 rmind static int ip_nfragpackets; /* packets in reass queue */
89 1.1 rmind static int ip_nfrags; /* total fragments in reass queues */
90 1.1 rmind
91 1.1 rmind static int ip_maxfragpackets; /* limit on packets. XXX sysctl */
92 1.1 rmind static int ip_maxfrags; /* limit on fragments. XXX sysctl */
93 1.1 rmind
94 1.1 rmind /*
95 1.2 rmind * IP reassembly queue structure. Each fragment being reassembled is
96 1.2 rmind * attached to one of these structures. They are timed out after ipq_ttl
97 1.2 rmind * drops to 0, and may also be reclaimed if memory becomes tight.
98 1.2 rmind */
99 1.2 rmind struct ipq {
100 1.2 rmind LIST_ENTRY(ipq) ipq_q; /* to other reass headers */
101 1.2 rmind uint8_t ipq_ttl; /* time for reass q to live */
102 1.2 rmind uint8_t ipq_p; /* protocol of this fragment */
103 1.2 rmind uint16_t ipq_id; /* sequence id for reassembly */
104 1.2 rmind struct ipqehead ipq_fragq; /* to ip fragment queue */
105 1.2 rmind struct in_addr ipq_src;
106 1.2 rmind struct in_addr ipq_dst;
107 1.2 rmind uint16_t ipq_nfrags; /* frags in this queue entry */
108 1.2 rmind uint8_t ipq_tos; /* TOS of this fragment */
109 1.2 rmind };
110 1.2 rmind
111 1.2 rmind /*
112 1.1 rmind * Cached copy of nmbclusters. If nbclusters is different,
113 1.1 rmind * recalculate IP parameters derived from nmbclusters.
114 1.1 rmind */
115 1.1 rmind static int ip_nmbclusters; /* copy of nmbclusters */
116 1.1 rmind
117 1.1 rmind /*
118 1.1 rmind * IP reassembly TTL machinery for multiplicative drop.
119 1.1 rmind */
120 1.1 rmind static u_int fragttl_histo[IPFRAGTTL + 1];
121 1.1 rmind
122 1.1 rmind void sysctl_ip_reass_setup(void);
123 1.1 rmind static void ip_nmbclusters_changed(void);
124 1.2 rmind
125 1.2 rmind static struct ipq * ip_reass_lookup(struct ip *, u_int *);
126 1.2 rmind static struct mbuf * ip_reass(struct ipqent *, struct ipq *, u_int);
127 1.2 rmind static u_int ip_reass_ttl_decr(u_int ticks);
128 1.2 rmind static void ip_reass_drophalf(void);
129 1.2 rmind static void ip_freef(struct ipq *);
130 1.1 rmind
131 1.1 rmind /*
132 1.1 rmind * ip_reass_init:
133 1.1 rmind *
134 1.1 rmind * Initialization of IP reassembly mechanism.
135 1.1 rmind */
136 1.1 rmind void
137 1.1 rmind ip_reass_init(void)
138 1.1 rmind {
139 1.1 rmind int i;
140 1.1 rmind
141 1.1 rmind pool_init(&ipqent_pool, sizeof(struct ipqent), 0, 0, 0, "ipqepl",
142 1.1 rmind NULL, IPL_VM);
143 1.1 rmind
144 1.1 rmind for (i = 0; i < IPREASS_HASH_SIZE; i++) {
145 1.1 rmind LIST_INIT(&ipq[i]);
146 1.1 rmind }
147 1.1 rmind ip_maxfragpackets = 200;
148 1.1 rmind ip_maxfrags = 0;
149 1.1 rmind ip_nmbclusters_changed();
150 1.1 rmind
151 1.1 rmind sysctl_ip_reass_setup();
152 1.1 rmind }
153 1.1 rmind
154 1.1 rmind static struct sysctllog *ip_reass_sysctllog;
155 1.1 rmind
156 1.1 rmind void
157 1.1 rmind sysctl_ip_reass_setup(void)
158 1.1 rmind {
159 1.1 rmind
160 1.1 rmind sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
161 1.1 rmind CTLFLAG_PERMANENT,
162 1.1 rmind CTLTYPE_NODE, "net", NULL,
163 1.1 rmind NULL, 0, NULL, 0,
164 1.1 rmind CTL_NET, CTL_EOL);
165 1.1 rmind sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
166 1.1 rmind CTLFLAG_PERMANENT,
167 1.1 rmind CTLTYPE_NODE, "inet",
168 1.1 rmind SYSCTL_DESCR("PF_INET related settings"),
169 1.1 rmind NULL, 0, NULL, 0,
170 1.1 rmind CTL_NET, PF_INET, CTL_EOL);
171 1.1 rmind sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
172 1.1 rmind CTLFLAG_PERMANENT,
173 1.1 rmind CTLTYPE_NODE, "ip",
174 1.1 rmind SYSCTL_DESCR("IPv4 related settings"),
175 1.1 rmind NULL, 0, NULL, 0,
176 1.1 rmind CTL_NET, PF_INET, IPPROTO_IP, CTL_EOL);
177 1.1 rmind
178 1.1 rmind sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
179 1.1 rmind CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
180 1.1 rmind CTLTYPE_INT, "maxfragpackets",
181 1.1 rmind SYSCTL_DESCR("Maximum number of fragments to retain for "
182 1.1 rmind "possible reassembly"),
183 1.1 rmind NULL, 0, &ip_maxfragpackets, 0,
184 1.1 rmind CTL_NET, PF_INET, IPPROTO_IP, IPCTL_MAXFRAGPACKETS, CTL_EOL);
185 1.1 rmind }
186 1.1 rmind
187 1.1 rmind #define CHECK_NMBCLUSTER_PARAMS() \
188 1.1 rmind do { \
189 1.1 rmind if (__predict_false(ip_nmbclusters != nmbclusters)) \
190 1.1 rmind ip_nmbclusters_changed(); \
191 1.1 rmind } while (/*CONSTCOND*/0)
192 1.1 rmind
193 1.1 rmind /*
194 1.1 rmind * Compute IP limits derived from the value of nmbclusters.
195 1.1 rmind */
196 1.1 rmind static void
197 1.1 rmind ip_nmbclusters_changed(void)
198 1.1 rmind {
199 1.1 rmind ip_maxfrags = nmbclusters / 4;
200 1.1 rmind ip_nmbclusters = nmbclusters;
201 1.1 rmind }
202 1.1 rmind
203 1.1 rmind static inline int ipq_lock_try(void);
204 1.1 rmind static inline void ipq_unlock(void);
205 1.1 rmind
206 1.1 rmind static inline int
207 1.1 rmind ipq_lock_try(void)
208 1.1 rmind {
209 1.1 rmind int s;
210 1.1 rmind
211 1.1 rmind /*
212 1.1 rmind * Use splvm() -- we're blocking things that would cause
213 1.1 rmind * mbuf allocation.
214 1.1 rmind */
215 1.1 rmind s = splvm();
216 1.1 rmind if (ipq_locked) {
217 1.1 rmind splx(s);
218 1.1 rmind return (0);
219 1.1 rmind }
220 1.1 rmind ipq_locked = 1;
221 1.1 rmind splx(s);
222 1.1 rmind return (1);
223 1.1 rmind }
224 1.1 rmind
225 1.1 rmind static inline void
226 1.1 rmind ipq_unlock(void)
227 1.1 rmind {
228 1.1 rmind int s;
229 1.1 rmind
230 1.1 rmind s = splvm();
231 1.1 rmind ipq_locked = 0;
232 1.1 rmind splx(s);
233 1.1 rmind }
234 1.1 rmind
235 1.1 rmind #ifdef DIAGNOSTIC
236 1.1 rmind #define IPQ_LOCK() \
237 1.1 rmind do { \
238 1.1 rmind if (ipq_lock_try() == 0) { \
239 1.1 rmind printf("%s:%d: ipq already locked\n", __FILE__, __LINE__); \
240 1.1 rmind panic("ipq_lock"); \
241 1.1 rmind } \
242 1.1 rmind } while (/*CONSTCOND*/ 0)
243 1.1 rmind #define IPQ_LOCK_CHECK() \
244 1.1 rmind do { \
245 1.1 rmind if (ipq_locked == 0) { \
246 1.1 rmind printf("%s:%d: ipq lock not held\n", __FILE__, __LINE__); \
247 1.1 rmind panic("ipq lock check"); \
248 1.1 rmind } \
249 1.1 rmind } while (/*CONSTCOND*/ 0)
250 1.1 rmind #else
251 1.1 rmind #define IPQ_LOCK() (void) ipq_lock_try()
252 1.1 rmind #define IPQ_LOCK_CHECK() /* nothing */
253 1.1 rmind #endif
254 1.1 rmind
255 1.1 rmind #define IPQ_UNLOCK() ipq_unlock()
256 1.1 rmind
257 1.1 rmind /*
258 1.1 rmind * ip_reass_lookup:
259 1.1 rmind *
260 1.1 rmind * Look for queue of fragments of this datagram.
261 1.1 rmind */
262 1.2 rmind static struct ipq *
263 1.1 rmind ip_reass_lookup(struct ip *ip, u_int *hashp)
264 1.1 rmind {
265 1.1 rmind struct ipq *fp;
266 1.1 rmind u_int hash;
267 1.1 rmind
268 1.1 rmind IPQ_LOCK();
269 1.1 rmind hash = IPREASS_HASH(ip->ip_src.s_addr, ip->ip_id);
270 1.1 rmind LIST_FOREACH(fp, &ipq[hash], ipq_q) {
271 1.1 rmind if (ip->ip_id != fp->ipq_id)
272 1.1 rmind continue;
273 1.1 rmind if (!in_hosteq(ip->ip_src, fp->ipq_src))
274 1.1 rmind continue;
275 1.1 rmind if (!in_hosteq(ip->ip_dst, fp->ipq_dst))
276 1.1 rmind continue;
277 1.1 rmind if (ip->ip_p != fp->ipq_p)
278 1.1 rmind continue;
279 1.1 rmind break;
280 1.1 rmind }
281 1.1 rmind *hashp = hash;
282 1.1 rmind return fp;
283 1.1 rmind }
284 1.1 rmind
285 1.1 rmind /*
286 1.1 rmind * ip_reass:
287 1.1 rmind *
288 1.1 rmind * Take incoming datagram fragment and try to reassemble it into whole
289 1.1 rmind * datagram. If a chain for reassembly of this datagram already exists,
290 1.1 rmind * then it is given as 'fp'; otherwise have to make a chain.
291 1.1 rmind */
292 1.1 rmind struct mbuf *
293 1.1 rmind ip_reass(struct ipqent *ipqe, struct ipq *fp, u_int hash)
294 1.1 rmind {
295 1.1 rmind struct ipqhead *ipqhead = &ipq[hash];
296 1.1 rmind const int hlen = ipqe->ipqe_ip->ip_hl << 2;
297 1.1 rmind struct mbuf *m = ipqe->ipqe_m, *t;
298 1.1 rmind struct ipqent *nq, *p, *q;
299 1.1 rmind struct ip *ip;
300 1.1 rmind int i, next, s;
301 1.1 rmind
302 1.1 rmind IPQ_LOCK_CHECK();
303 1.1 rmind
304 1.1 rmind /*
305 1.1 rmind * Presence of header sizes in mbufs would confuse code below.
306 1.1 rmind */
307 1.1 rmind m->m_data += hlen;
308 1.1 rmind m->m_len -= hlen;
309 1.1 rmind
310 1.1 rmind #ifdef notyet
311 1.1 rmind /* Make sure fragment limit is up-to-date. */
312 1.1 rmind CHECK_NMBCLUSTER_PARAMS();
313 1.1 rmind
314 1.1 rmind /* If we have too many fragments, drop the older half. */
315 1.1 rmind if (ip_nfrags >= ip_maxfrags) {
316 1.1 rmind ip_reass_drophalf(void);
317 1.1 rmind }
318 1.1 rmind #endif
319 1.1 rmind
320 1.1 rmind /*
321 1.1 rmind * We are about to add a fragment; increment frag count.
322 1.1 rmind */
323 1.1 rmind ip_nfrags++;
324 1.1 rmind
325 1.1 rmind /*
326 1.1 rmind * If first fragment to arrive, create a reassembly queue.
327 1.1 rmind */
328 1.1 rmind if (fp == NULL) {
329 1.1 rmind /*
330 1.1 rmind * Enforce upper bound on number of fragmented packets
331 1.1 rmind * for which we attempt reassembly: a) if maxfrag is 0,
332 1.1 rmind * never accept fragments b) if maxfrag is -1, accept
333 1.1 rmind * all fragments without limitation.
334 1.1 rmind */
335 1.1 rmind if (ip_maxfragpackets < 0)
336 1.1 rmind ;
337 1.1 rmind else if (ip_nfragpackets >= ip_maxfragpackets) {
338 1.1 rmind goto dropfrag;
339 1.1 rmind }
340 1.1 rmind ip_nfragpackets++;
341 1.1 rmind fp = malloc(sizeof(struct ipq), M_FTABLE, M_NOWAIT);
342 1.1 rmind if (fp == NULL) {
343 1.1 rmind goto dropfrag;
344 1.1 rmind }
345 1.1 rmind LIST_INSERT_HEAD(ipqhead, fp, ipq_q);
346 1.1 rmind fp->ipq_nfrags = 1;
347 1.1 rmind fp->ipq_ttl = IPFRAGTTL;
348 1.1 rmind fp->ipq_p = ipqe->ipqe_ip->ip_p;
349 1.1 rmind fp->ipq_id = ipqe->ipqe_ip->ip_id;
350 1.1 rmind fp->ipq_tos = ipqe->ipqe_ip->ip_tos;
351 1.1 rmind TAILQ_INIT(&fp->ipq_fragq);
352 1.1 rmind fp->ipq_src = ipqe->ipqe_ip->ip_src;
353 1.1 rmind fp->ipq_dst = ipqe->ipqe_ip->ip_dst;
354 1.1 rmind p = NULL;
355 1.1 rmind goto insert;
356 1.1 rmind } else {
357 1.1 rmind fp->ipq_nfrags++;
358 1.1 rmind }
359 1.1 rmind
360 1.1 rmind /*
361 1.1 rmind * Find a segment which begins after this one does.
362 1.1 rmind */
363 1.1 rmind for (p = NULL, q = TAILQ_FIRST(&fp->ipq_fragq); q != NULL;
364 1.1 rmind p = q, q = TAILQ_NEXT(q, ipqe_q))
365 1.1 rmind if (ntohs(q->ipqe_ip->ip_off) > ntohs(ipqe->ipqe_ip->ip_off))
366 1.1 rmind break;
367 1.1 rmind
368 1.1 rmind /*
369 1.1 rmind * If there is a preceding segment, it may provide some of our
370 1.1 rmind * data already. If so, drop the data from the incoming segment.
371 1.1 rmind * If it provides all of our data, drop us.
372 1.1 rmind */
373 1.1 rmind if (p != NULL) {
374 1.1 rmind i = ntohs(p->ipqe_ip->ip_off) + ntohs(p->ipqe_ip->ip_len) -
375 1.1 rmind ntohs(ipqe->ipqe_ip->ip_off);
376 1.1 rmind if (i > 0) {
377 1.1 rmind if (i >= ntohs(ipqe->ipqe_ip->ip_len)) {
378 1.1 rmind goto dropfrag;
379 1.1 rmind }
380 1.1 rmind m_adj(ipqe->ipqe_m, i);
381 1.1 rmind ipqe->ipqe_ip->ip_off =
382 1.1 rmind htons(ntohs(ipqe->ipqe_ip->ip_off) + i);
383 1.1 rmind ipqe->ipqe_ip->ip_len =
384 1.1 rmind htons(ntohs(ipqe->ipqe_ip->ip_len) - i);
385 1.1 rmind }
386 1.1 rmind }
387 1.1 rmind
388 1.1 rmind /*
389 1.1 rmind * While we overlap succeeding segments trim them or, if they are
390 1.1 rmind * completely covered, dequeue them.
391 1.1 rmind */
392 1.1 rmind for (; q != NULL &&
393 1.1 rmind ntohs(ipqe->ipqe_ip->ip_off) + ntohs(ipqe->ipqe_ip->ip_len) >
394 1.1 rmind ntohs(q->ipqe_ip->ip_off); q = nq) {
395 1.1 rmind i = (ntohs(ipqe->ipqe_ip->ip_off) +
396 1.1 rmind ntohs(ipqe->ipqe_ip->ip_len)) - ntohs(q->ipqe_ip->ip_off);
397 1.1 rmind if (i < ntohs(q->ipqe_ip->ip_len)) {
398 1.1 rmind q->ipqe_ip->ip_len =
399 1.1 rmind htons(ntohs(q->ipqe_ip->ip_len) - i);
400 1.1 rmind q->ipqe_ip->ip_off =
401 1.1 rmind htons(ntohs(q->ipqe_ip->ip_off) + i);
402 1.1 rmind m_adj(q->ipqe_m, i);
403 1.1 rmind break;
404 1.1 rmind }
405 1.1 rmind nq = TAILQ_NEXT(q, ipqe_q);
406 1.1 rmind m_freem(q->ipqe_m);
407 1.1 rmind TAILQ_REMOVE(&fp->ipq_fragq, q, ipqe_q);
408 1.1 rmind s = splvm();
409 1.1 rmind pool_put(&ipqent_pool, q);
410 1.1 rmind splx(s);
411 1.1 rmind fp->ipq_nfrags--;
412 1.1 rmind ip_nfrags--;
413 1.1 rmind }
414 1.1 rmind
415 1.1 rmind insert:
416 1.1 rmind /*
417 1.1 rmind * Stick new segment in its place; check for complete reassembly.
418 1.1 rmind */
419 1.1 rmind if (p == NULL) {
420 1.1 rmind TAILQ_INSERT_HEAD(&fp->ipq_fragq, ipqe, ipqe_q);
421 1.1 rmind } else {
422 1.1 rmind TAILQ_INSERT_AFTER(&fp->ipq_fragq, p, ipqe, ipqe_q);
423 1.1 rmind }
424 1.1 rmind next = 0;
425 1.1 rmind for (p = NULL, q = TAILQ_FIRST(&fp->ipq_fragq); q != NULL;
426 1.1 rmind p = q, q = TAILQ_NEXT(q, ipqe_q)) {
427 1.1 rmind if (ntohs(q->ipqe_ip->ip_off) != next) {
428 1.1 rmind IPQ_UNLOCK();
429 1.1 rmind return NULL;
430 1.1 rmind }
431 1.1 rmind next += ntohs(q->ipqe_ip->ip_len);
432 1.1 rmind }
433 1.1 rmind if (p->ipqe_mff) {
434 1.1 rmind IPQ_UNLOCK();
435 1.1 rmind return NULL;
436 1.1 rmind }
437 1.1 rmind /*
438 1.1 rmind * Reassembly is complete. Check for a bogus message size and
439 1.1 rmind * concatenate fragments.
440 1.1 rmind */
441 1.1 rmind q = TAILQ_FIRST(&fp->ipq_fragq);
442 1.1 rmind ip = q->ipqe_ip;
443 1.1 rmind if ((next + (ip->ip_hl << 2)) > IP_MAXPACKET) {
444 1.1 rmind IP_STATINC(IP_STAT_TOOLONG);
445 1.1 rmind ip_freef(fp);
446 1.1 rmind IPQ_UNLOCK();
447 1.1 rmind return NULL;
448 1.1 rmind }
449 1.1 rmind m = q->ipqe_m;
450 1.1 rmind t = m->m_next;
451 1.1 rmind m->m_next = NULL;
452 1.1 rmind m_cat(m, t);
453 1.1 rmind nq = TAILQ_NEXT(q, ipqe_q);
454 1.1 rmind s = splvm();
455 1.1 rmind pool_put(&ipqent_pool, q);
456 1.1 rmind splx(s);
457 1.1 rmind for (q = nq; q != NULL; q = nq) {
458 1.1 rmind t = q->ipqe_m;
459 1.1 rmind nq = TAILQ_NEXT(q, ipqe_q);
460 1.1 rmind s = splvm();
461 1.1 rmind pool_put(&ipqent_pool, q);
462 1.1 rmind splx(s);
463 1.1 rmind m_cat(m, t);
464 1.1 rmind }
465 1.1 rmind ip_nfrags -= fp->ipq_nfrags;
466 1.1 rmind
467 1.1 rmind /*
468 1.1 rmind * Create header for new packet by modifying header of first
469 1.1 rmind * packet. Dequeue and discard fragment reassembly header. Make
470 1.1 rmind * header visible.
471 1.1 rmind */
472 1.2 rmind ip->ip_len = htons((ip->ip_hl << 2) + next);
473 1.1 rmind ip->ip_src = fp->ipq_src;
474 1.1 rmind ip->ip_dst = fp->ipq_dst;
475 1.2 rmind
476 1.1 rmind LIST_REMOVE(fp, ipq_q);
477 1.1 rmind free(fp, M_FTABLE);
478 1.1 rmind ip_nfragpackets--;
479 1.1 rmind m->m_len += (ip->ip_hl << 2);
480 1.1 rmind m->m_data -= (ip->ip_hl << 2);
481 1.1 rmind /* some debugging cruft by sklower, below, will go away soon */
482 1.1 rmind if (m->m_flags & M_PKTHDR) { /* XXX this should be done elsewhere */
483 1.1 rmind int plen = 0;
484 1.1 rmind for (t = m; t; t = t->m_next) {
485 1.1 rmind plen += t->m_len;
486 1.1 rmind }
487 1.1 rmind m->m_pkthdr.len = plen;
488 1.1 rmind m->m_pkthdr.csum_flags = 0;
489 1.1 rmind }
490 1.1 rmind IPQ_UNLOCK();
491 1.1 rmind return m;
492 1.1 rmind
493 1.1 rmind dropfrag:
494 1.1 rmind if (fp != NULL) {
495 1.1 rmind fp->ipq_nfrags--;
496 1.1 rmind }
497 1.1 rmind ip_nfrags--;
498 1.1 rmind IP_STATINC(IP_STAT_FRAGDROPPED);
499 1.1 rmind m_freem(m);
500 1.1 rmind s = splvm();
501 1.1 rmind pool_put(&ipqent_pool, ipqe);
502 1.1 rmind splx(s);
503 1.1 rmind IPQ_UNLOCK();
504 1.1 rmind return NULL;
505 1.1 rmind }
506 1.1 rmind
507 1.1 rmind /*
508 1.1 rmind * ip_freef:
509 1.1 rmind *
510 1.1 rmind * Free a fragment reassembly header and all associated datagrams.
511 1.1 rmind */
512 1.2 rmind static void
513 1.1 rmind ip_freef(struct ipq *fp)
514 1.1 rmind {
515 1.1 rmind struct ipqent *q, *p;
516 1.1 rmind u_int nfrags = 0;
517 1.1 rmind int s;
518 1.1 rmind
519 1.1 rmind IPQ_LOCK_CHECK();
520 1.1 rmind
521 1.1 rmind for (q = TAILQ_FIRST(&fp->ipq_fragq); q != NULL; q = p) {
522 1.1 rmind p = TAILQ_NEXT(q, ipqe_q);
523 1.1 rmind m_freem(q->ipqe_m);
524 1.1 rmind nfrags++;
525 1.1 rmind TAILQ_REMOVE(&fp->ipq_fragq, q, ipqe_q);
526 1.1 rmind s = splvm();
527 1.1 rmind pool_put(&ipqent_pool, q);
528 1.1 rmind splx(s);
529 1.1 rmind }
530 1.1 rmind
531 1.1 rmind if (nfrags != fp->ipq_nfrags) {
532 1.1 rmind printf("ip_freef: nfrags %d != %d\n", fp->ipq_nfrags, nfrags);
533 1.1 rmind }
534 1.1 rmind ip_nfrags -= nfrags;
535 1.1 rmind LIST_REMOVE(fp, ipq_q);
536 1.1 rmind free(fp, M_FTABLE);
537 1.1 rmind ip_nfragpackets--;
538 1.1 rmind }
539 1.1 rmind
540 1.1 rmind /*
541 1.1 rmind * ip_reass_ttl_decr:
542 1.1 rmind *
543 1.1 rmind * Decrement TTL of all reasembly queue entries by `ticks'. Count
544 1.1 rmind * number of distinct fragments (as opposed to partial, fragmented
545 1.1 rmind * datagrams) inthe reassembly queue. While we traverse the entire
546 1.1 rmind * reassembly queue, compute and return the median TTL over all
547 1.1 rmind * fragments.
548 1.1 rmind */
549 1.1 rmind static u_int
550 1.1 rmind ip_reass_ttl_decr(u_int ticks)
551 1.1 rmind {
552 1.1 rmind u_int nfrags, median, dropfraction, keepfraction;
553 1.1 rmind struct ipq *fp, *nfp;
554 1.1 rmind int i;
555 1.1 rmind
556 1.1 rmind nfrags = 0;
557 1.1 rmind memset(fragttl_histo, 0, sizeof(fragttl_histo));
558 1.1 rmind
559 1.1 rmind for (i = 0; i < IPREASS_HASH_SIZE; i++) {
560 1.1 rmind for (fp = LIST_FIRST(&ipq[i]); fp != NULL; fp = nfp) {
561 1.1 rmind fp->ipq_ttl = ((fp->ipq_ttl <= ticks) ?
562 1.1 rmind 0 : fp->ipq_ttl - ticks);
563 1.1 rmind nfp = LIST_NEXT(fp, ipq_q);
564 1.1 rmind if (fp->ipq_ttl == 0) {
565 1.1 rmind IP_STATINC(IP_STAT_FRAGTIMEOUT);
566 1.1 rmind ip_freef(fp);
567 1.1 rmind } else {
568 1.1 rmind nfrags += fp->ipq_nfrags;
569 1.1 rmind fragttl_histo[fp->ipq_ttl] += fp->ipq_nfrags;
570 1.1 rmind }
571 1.1 rmind }
572 1.1 rmind }
573 1.1 rmind
574 1.1 rmind KASSERT(ip_nfrags == nfrags);
575 1.1 rmind
576 1.1 rmind /* Find median (or other drop fraction) in histogram. */
577 1.1 rmind dropfraction = (ip_nfrags / 2);
578 1.1 rmind keepfraction = ip_nfrags - dropfraction;
579 1.1 rmind for (i = IPFRAGTTL, median = 0; i >= 0; i--) {
580 1.1 rmind median += fragttl_histo[i];
581 1.1 rmind if (median >= keepfraction)
582 1.1 rmind break;
583 1.1 rmind }
584 1.1 rmind
585 1.1 rmind /* Return TTL of median (or other fraction). */
586 1.1 rmind return (u_int)i;
587 1.1 rmind }
588 1.1 rmind
589 1.1 rmind static void
590 1.1 rmind ip_reass_drophalf(void)
591 1.1 rmind {
592 1.1 rmind u_int median_ticks;
593 1.1 rmind
594 1.1 rmind /*
595 1.1 rmind * Compute median TTL of all fragments, and count frags
596 1.1 rmind * with that TTL or lower (roughly half of all fragments).
597 1.1 rmind */
598 1.1 rmind median_ticks = ip_reass_ttl_decr(0);
599 1.1 rmind
600 1.1 rmind /* Drop half. */
601 1.1 rmind median_ticks = ip_reass_ttl_decr(median_ticks);
602 1.1 rmind }
603 1.1 rmind
604 1.1 rmind /*
605 1.1 rmind * ip_reass_drain: drain off all datagram fragments. Do not acquire
606 1.1 rmind * softnet_lock as can be called from hardware interrupt context.
607 1.1 rmind */
608 1.1 rmind void
609 1.1 rmind ip_reass_drain(void)
610 1.1 rmind {
611 1.1 rmind
612 1.1 rmind /*
613 1.1 rmind * We may be called from a device's interrupt context. If
614 1.1 rmind * the ipq is already busy, just bail out now.
615 1.1 rmind */
616 1.1 rmind if (ipq_lock_try() != 0) {
617 1.1 rmind /*
618 1.1 rmind * Drop half the total fragments now. If more mbufs are
619 1.1 rmind * needed, we will be called again soon.
620 1.1 rmind */
621 1.1 rmind ip_reass_drophalf();
622 1.1 rmind IPQ_UNLOCK();
623 1.1 rmind }
624 1.1 rmind }
625 1.1 rmind
626 1.1 rmind /*
627 1.1 rmind * ip_reass_slowtimo:
628 1.1 rmind *
629 1.1 rmind * If a timer expires on a reassembly queue, discard it.
630 1.1 rmind */
631 1.1 rmind void
632 1.1 rmind ip_reass_slowtimo(void)
633 1.1 rmind {
634 1.1 rmind static u_int dropscanidx = 0;
635 1.1 rmind u_int i, median_ttl;
636 1.1 rmind
637 1.1 rmind IPQ_LOCK();
638 1.1 rmind
639 1.1 rmind /* Age TTL of all fragments by 1 tick .*/
640 1.1 rmind median_ttl = ip_reass_ttl_decr(1);
641 1.1 rmind
642 1.1 rmind /* Make sure fragment limit is up-to-date. */
643 1.1 rmind CHECK_NMBCLUSTER_PARAMS();
644 1.1 rmind
645 1.1 rmind /* If we have too many fragments, drop the older half. */
646 1.1 rmind if (ip_nfrags > ip_maxfrags) {
647 1.1 rmind ip_reass_ttl_decr(median_ttl);
648 1.1 rmind }
649 1.1 rmind
650 1.1 rmind /*
651 1.1 rmind * If we are over the maximum number of fragmented packets (due to
652 1.1 rmind * the limit being lowered), drain off enough to get down to the
653 1.1 rmind * new limit. Start draining from the reassembly hashqueue most
654 1.1 rmind * recently drained.
655 1.1 rmind */
656 1.1 rmind if (ip_maxfragpackets < 0)
657 1.1 rmind ;
658 1.1 rmind else {
659 1.1 rmind int wrapped = 0;
660 1.1 rmind
661 1.1 rmind i = dropscanidx;
662 1.1 rmind while (ip_nfragpackets > ip_maxfragpackets && wrapped == 0) {
663 1.1 rmind while (LIST_FIRST(&ipq[i]) != NULL) {
664 1.1 rmind ip_freef(LIST_FIRST(&ipq[i]));
665 1.1 rmind }
666 1.1 rmind if (++i >= IPREASS_HASH_SIZE) {
667 1.1 rmind i = 0;
668 1.1 rmind }
669 1.1 rmind /*
670 1.1 rmind * Do not scan forever even if fragment counters are
671 1.1 rmind * wrong: stop after scanning entire reassembly queue.
672 1.1 rmind */
673 1.1 rmind if (i == dropscanidx) {
674 1.1 rmind wrapped = 1;
675 1.1 rmind }
676 1.1 rmind }
677 1.1 rmind dropscanidx = i;
678 1.1 rmind }
679 1.1 rmind IPQ_UNLOCK();
680 1.1 rmind }
681 1.2 rmind
682 1.2 rmind /*
683 1.2 rmind * ip_reass_packet: generic routine to perform IP reassembly.
684 1.2 rmind *
685 1.2 rmind * => Passed fragment should have IP_MF flag and/or offset set.
686 1.2 rmind * => Fragment should not have other than IP_MF flags set.
687 1.2 rmind *
688 1.2 rmind * => Returns 0 on success or error otherwise. When reassembly is complete,
689 1.2 rmind * m_final representing a constructed final packet is set.
690 1.2 rmind */
691 1.2 rmind int
692 1.2 rmind ip_reass_packet(struct mbuf *m, struct ip *ip, bool mff, struct mbuf **m_final)
693 1.2 rmind {
694 1.2 rmind struct ipq *fp;
695 1.2 rmind struct ipqent *ipqe;
696 1.2 rmind u_int hash;
697 1.2 rmind
698 1.2 rmind /* Look for queue of fragments of this datagram. */
699 1.2 rmind fp = ip_reass_lookup(ip, &hash);
700 1.2 rmind
701 1.2 rmind /* Make sure that TOS matches previous fragments. */
702 1.2 rmind if (fp && fp->ipq_tos != ip->ip_tos) {
703 1.2 rmind IP_STATINC(IP_STAT_BADFRAGS);
704 1.2 rmind IPQ_UNLOCK();
705 1.2 rmind return EINVAL;
706 1.2 rmind }
707 1.2 rmind
708 1.2 rmind /*
709 1.2 rmind * Create new entry and attempt to reassembly.
710 1.2 rmind */
711 1.2 rmind IP_STATINC(IP_STAT_FRAGMENTS);
712 1.2 rmind int s = splvm();
713 1.2 rmind ipqe = pool_get(&ipqent_pool, PR_NOWAIT);
714 1.2 rmind splx(s);
715 1.2 rmind if (ipqe == NULL) {
716 1.2 rmind IP_STATINC(IP_STAT_RCVMEMDROP);
717 1.2 rmind IPQ_UNLOCK();
718 1.2 rmind return ENOMEM;
719 1.2 rmind }
720 1.2 rmind ipqe->ipqe_mff = mff;
721 1.2 rmind ipqe->ipqe_m = m;
722 1.2 rmind ipqe->ipqe_ip = ip;
723 1.2 rmind
724 1.2 rmind *m_final = ip_reass(ipqe, fp, hash);
725 1.2 rmind if (*m_final) {
726 1.2 rmind /* Note if finally reassembled. */
727 1.2 rmind IP_STATINC(IP_STAT_REASSEMBLED);
728 1.2 rmind }
729 1.2 rmind return 0;
730 1.2 rmind }
731