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