Home | History | Annotate | Line # | Download | only in netinet
ip_reass.c revision 1.17.2.1
      1  1.17.2.1  christos /*	$NetBSD: ip_reass.c,v 1.17.2.1 2019/06/10 22:09:47 christos 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.17.2.1  christos __KERNEL_RCSID(0, "$NetBSD: ip_reass.c,v 1.17.2.1 2019/06/10 22:09:47 christos 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.4     rmind #include <sys/mutex.h>
     57       1.1     rmind #include <sys/pool.h>
     58       1.2     rmind #include <sys/queue.h>
     59       1.1     rmind #include <sys/sysctl.h>
     60       1.2     rmind #include <sys/systm.h>
     61       1.1     rmind 
     62       1.1     rmind #include <net/if.h>
     63       1.1     rmind 
     64       1.1     rmind #include <netinet/in.h>
     65       1.1     rmind #include <netinet/in_systm.h>
     66       1.1     rmind #include <netinet/ip.h>
     67       1.1     rmind #include <netinet/in_pcb.h>
     68       1.2     rmind #include <netinet/ip_var.h>
     69       1.1     rmind #include <netinet/ip_private.h>
     70       1.1     rmind #include <netinet/in_var.h>
     71       1.1     rmind 
     72       1.1     rmind /*
     73       1.3     rmind  * IP reassembly queue structures.  Each fragment being reassembled is
     74       1.3     rmind  * attached to one of these structures.  They are timed out after TTL
     75       1.3     rmind  * drops to 0, and may also be reclaimed if memory becomes tight.
     76       1.3     rmind  */
     77       1.3     rmind 
     78       1.3     rmind typedef struct ipfr_qent {
     79       1.3     rmind 	TAILQ_ENTRY(ipfr_qent)	ipqe_q;
     80       1.3     rmind 	struct ip *		ipqe_ip;
     81       1.3     rmind 	struct mbuf *		ipqe_m;
     82       1.3     rmind 	bool			ipqe_mff;
     83  1.17.2.1  christos 	uint16_t		ipqe_off;
     84  1.17.2.1  christos 	uint16_t		ipqe_len;
     85       1.3     rmind } ipfr_qent_t;
     86       1.3     rmind 
     87       1.7     rmind TAILQ_HEAD(ipfr_qent_head, ipfr_qent);
     88       1.7     rmind 
     89       1.3     rmind typedef struct ipfr_queue {
     90       1.3     rmind 	LIST_ENTRY(ipfr_queue)	ipq_q;		/* to other reass headers */
     91       1.7     rmind 	struct ipfr_qent_head	ipq_fragq;	/* queue of fragment entries */
     92       1.3     rmind 	uint8_t			ipq_ttl;	/* time for reass q to live */
     93       1.3     rmind 	uint8_t			ipq_p;		/* protocol of this fragment */
     94       1.3     rmind 	uint16_t		ipq_id;		/* sequence id for reassembly */
     95       1.3     rmind 	struct in_addr		ipq_src;
     96       1.3     rmind 	struct in_addr		ipq_dst;
     97       1.3     rmind 	uint16_t		ipq_nfrags;	/* frags in this queue entry */
     98      1.17      maxv 	uint8_t			ipq_tos;	/* TOS of this fragment */
     99      1.17      maxv 	int			ipq_ipsec;	/* IPsec flags */
    100       1.3     rmind } ipfr_queue_t;
    101       1.3     rmind 
    102       1.3     rmind /*
    103       1.3     rmind  * Hash table of IP reassembly queues.
    104       1.1     rmind  */
    105       1.1     rmind #define	IPREASS_HASH_SHIFT	6
    106       1.1     rmind #define	IPREASS_HASH_SIZE	(1 << IPREASS_HASH_SHIFT)
    107       1.1     rmind #define	IPREASS_HASH_MASK	(IPREASS_HASH_SIZE - 1)
    108       1.1     rmind #define	IPREASS_HASH(x, y) \
    109       1.1     rmind 	(((((x) & 0xf) | ((((x) >> 8) & 0xf) << 4)) ^ (y)) & IPREASS_HASH_MASK)
    110       1.1     rmind 
    111       1.3     rmind static LIST_HEAD(, ipfr_queue)	ip_frags[IPREASS_HASH_SIZE];
    112       1.4     rmind static pool_cache_t	ipfren_cache;
    113       1.4     rmind static kmutex_t		ipfr_lock;
    114       1.1     rmind 
    115       1.3     rmind /* Number of packets in reassembly queue and total number of fragments. */
    116       1.3     rmind static int		ip_nfragpackets;
    117       1.3     rmind static int		ip_nfrags;
    118       1.1     rmind 
    119       1.3     rmind /* Limits on packet and fragments. */
    120       1.3     rmind static int		ip_maxfragpackets;
    121       1.3     rmind static int		ip_maxfrags;
    122       1.1     rmind 
    123       1.1     rmind /*
    124       1.3     rmind  * Cached copy of nmbclusters.  If nbclusters is different, recalculate
    125       1.3     rmind  * IP parameters derived from nmbclusters.
    126       1.2     rmind  */
    127       1.3     rmind static int		ip_nmbclusters;
    128       1.1     rmind 
    129       1.1     rmind /*
    130       1.1     rmind  * IP reassembly TTL machinery for multiplicative drop.
    131       1.1     rmind  */
    132       1.3     rmind static u_int		fragttl_histo[IPFRAGTTL + 1];
    133       1.1     rmind 
    134       1.4     rmind static struct sysctllog *ip_reass_sysctllog;
    135       1.4     rmind 
    136       1.3     rmind void			sysctl_ip_reass_setup(void);
    137       1.3     rmind static void		ip_nmbclusters_changed(void);
    138       1.2     rmind 
    139       1.3     rmind static struct mbuf *	ip_reass(ipfr_qent_t *, ipfr_queue_t *, u_int);
    140       1.2     rmind static u_int		ip_reass_ttl_decr(u_int ticks);
    141       1.2     rmind static void		ip_reass_drophalf(void);
    142       1.3     rmind static void		ip_freef(ipfr_queue_t *);
    143       1.1     rmind 
    144       1.1     rmind /*
    145       1.1     rmind  * ip_reass_init:
    146       1.1     rmind  *
    147       1.1     rmind  *	Initialization of IP reassembly mechanism.
    148       1.1     rmind  */
    149       1.1     rmind void
    150       1.1     rmind ip_reass_init(void)
    151       1.1     rmind {
    152       1.1     rmind 	int i;
    153       1.1     rmind 
    154       1.4     rmind 	ipfren_cache = pool_cache_init(sizeof(ipfr_qent_t), coherency_unit,
    155       1.4     rmind 	    0, 0, "ipfrenpl", NULL, IPL_NET, NULL, NULL, NULL);
    156       1.6      yamt 	mutex_init(&ipfr_lock, MUTEX_DEFAULT, IPL_VM);
    157       1.1     rmind 
    158       1.1     rmind 	for (i = 0; i < IPREASS_HASH_SIZE; i++) {
    159       1.3     rmind 		LIST_INIT(&ip_frags[i]);
    160       1.1     rmind 	}
    161       1.1     rmind 	ip_maxfragpackets = 200;
    162       1.1     rmind 	ip_maxfrags = 0;
    163       1.1     rmind 	ip_nmbclusters_changed();
    164       1.1     rmind 
    165       1.1     rmind 	sysctl_ip_reass_setup();
    166       1.1     rmind }
    167       1.1     rmind 
    168       1.1     rmind void
    169       1.1     rmind sysctl_ip_reass_setup(void)
    170       1.1     rmind {
    171       1.1     rmind 
    172       1.1     rmind 	sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
    173       1.1     rmind 		CTLFLAG_PERMANENT,
    174       1.1     rmind 		CTLTYPE_NODE, "inet",
    175       1.1     rmind 		SYSCTL_DESCR("PF_INET related settings"),
    176       1.1     rmind 		NULL, 0, NULL, 0,
    177       1.1     rmind 		CTL_NET, PF_INET, CTL_EOL);
    178       1.1     rmind 	sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
    179       1.1     rmind 		CTLFLAG_PERMANENT,
    180       1.1     rmind 		CTLTYPE_NODE, "ip",
    181       1.1     rmind 		SYSCTL_DESCR("IPv4 related settings"),
    182       1.1     rmind 		NULL, 0, NULL, 0,
    183       1.1     rmind 		CTL_NET, PF_INET, IPPROTO_IP, CTL_EOL);
    184       1.1     rmind 
    185       1.1     rmind 	sysctl_createv(&ip_reass_sysctllog, 0, NULL, NULL,
    186       1.1     rmind 		CTLFLAG_PERMANENT|CTLFLAG_READWRITE,
    187       1.1     rmind 		CTLTYPE_INT, "maxfragpackets",
    188       1.1     rmind 		SYSCTL_DESCR("Maximum number of fragments to retain for "
    189       1.1     rmind 			     "possible reassembly"),
    190       1.1     rmind 		NULL, 0, &ip_maxfragpackets, 0,
    191       1.1     rmind 		CTL_NET, PF_INET, IPPROTO_IP, IPCTL_MAXFRAGPACKETS, CTL_EOL);
    192       1.1     rmind }
    193       1.1     rmind 
    194       1.1     rmind #define CHECK_NMBCLUSTER_PARAMS()				\
    195       1.1     rmind do {								\
    196       1.1     rmind 	if (__predict_false(ip_nmbclusters != nmbclusters))	\
    197       1.1     rmind 		ip_nmbclusters_changed();			\
    198       1.1     rmind } while (/*CONSTCOND*/0)
    199       1.1     rmind 
    200       1.1     rmind /*
    201       1.1     rmind  * Compute IP limits derived from the value of nmbclusters.
    202       1.1     rmind  */
    203       1.1     rmind static void
    204       1.1     rmind ip_nmbclusters_changed(void)
    205       1.1     rmind {
    206       1.1     rmind 	ip_maxfrags = nmbclusters / 4;
    207       1.1     rmind 	ip_nmbclusters = nmbclusters;
    208       1.1     rmind }
    209       1.1     rmind 
    210       1.1     rmind /*
    211       1.1     rmind  * ip_reass:
    212       1.1     rmind  *
    213       1.1     rmind  *	Take incoming datagram fragment and try to reassemble it into whole
    214       1.1     rmind  *	datagram.  If a chain for reassembly of this datagram already exists,
    215       1.1     rmind  *	then it is given as 'fp'; otherwise have to make a chain.
    216       1.1     rmind  */
    217      1.15      maxv static struct mbuf *
    218       1.3     rmind ip_reass(ipfr_qent_t *ipqe, ipfr_queue_t *fp, const u_int hash)
    219       1.1     rmind {
    220  1.17.2.1  christos 	struct ip *ip = ipqe->ipqe_ip;
    221       1.7     rmind 	const int hlen = ip->ip_hl << 2;
    222       1.1     rmind 	struct mbuf *m = ipqe->ipqe_m, *t;
    223      1.17      maxv 	int ipsecflags = m->m_flags & (M_DECRYPTED|M_AUTHIPHDR);
    224       1.3     rmind 	ipfr_qent_t *nq, *p, *q;
    225       1.4     rmind 	int i, next;
    226       1.1     rmind 
    227       1.4     rmind 	KASSERT(mutex_owned(&ipfr_lock));
    228       1.1     rmind 
    229       1.1     rmind 	/*
    230       1.1     rmind 	 * Presence of header sizes in mbufs would confuse code below.
    231       1.1     rmind 	 */
    232       1.1     rmind 	m->m_data += hlen;
    233       1.1     rmind 	m->m_len -= hlen;
    234       1.1     rmind 
    235       1.1     rmind 	/*
    236       1.1     rmind 	 * We are about to add a fragment; increment frag count.
    237       1.1     rmind 	 */
    238       1.1     rmind 	ip_nfrags++;
    239       1.1     rmind 
    240       1.1     rmind 	/*
    241       1.1     rmind 	 * If first fragment to arrive, create a reassembly queue.
    242       1.1     rmind 	 */
    243       1.1     rmind 	if (fp == NULL) {
    244       1.1     rmind 		/*
    245       1.1     rmind 		 * Enforce upper bound on number of fragmented packets
    246       1.1     rmind 		 * for which we attempt reassembly:  a) if maxfrag is 0,
    247       1.1     rmind 		 * never accept fragments  b) if maxfrag is -1, accept
    248       1.1     rmind 		 * all fragments without limitation.
    249       1.1     rmind 		 */
    250  1.17.2.1  christos 		if (ip_maxfragpackets < 0) {
    251  1.17.2.1  christos 			/* no limit */
    252  1.17.2.1  christos 		} else if (ip_nfragpackets >= ip_maxfragpackets) {
    253       1.1     rmind 			goto dropfrag;
    254       1.1     rmind 		}
    255       1.3     rmind 		fp = malloc(sizeof(ipfr_queue_t), M_FTABLE, M_NOWAIT);
    256       1.1     rmind 		if (fp == NULL) {
    257       1.1     rmind 			goto dropfrag;
    258       1.1     rmind 		}
    259       1.8     enami 		ip_nfragpackets++;
    260       1.7     rmind 		TAILQ_INIT(&fp->ipq_fragq);
    261       1.1     rmind 		fp->ipq_nfrags = 1;
    262       1.1     rmind 		fp->ipq_ttl = IPFRAGTTL;
    263       1.7     rmind 		fp->ipq_p = ip->ip_p;
    264       1.7     rmind 		fp->ipq_id = ip->ip_id;
    265       1.7     rmind 		fp->ipq_tos = ip->ip_tos;
    266      1.17      maxv 		fp->ipq_ipsec = ipsecflags;
    267       1.7     rmind 		fp->ipq_src = ip->ip_src;
    268       1.7     rmind 		fp->ipq_dst = ip->ip_dst;
    269       1.7     rmind 		LIST_INSERT_HEAD(&ip_frags[hash], fp, ipq_q);
    270       1.1     rmind 		p = NULL;
    271       1.1     rmind 		goto insert;
    272       1.1     rmind 	} else {
    273       1.1     rmind 		fp->ipq_nfrags++;
    274       1.1     rmind 	}
    275       1.1     rmind 
    276       1.1     rmind 	/*
    277       1.1     rmind 	 * Find a segment which begins after this one does.
    278       1.1     rmind 	 */
    279       1.7     rmind 	TAILQ_FOREACH(q, &fp->ipq_fragq, ipqe_q) {
    280  1.17.2.1  christos 		if (q->ipqe_off > ipqe->ipqe_off)
    281       1.1     rmind 			break;
    282       1.7     rmind 	}
    283       1.7     rmind 	if (q != NULL) {
    284       1.7     rmind 		p = TAILQ_PREV(q, ipfr_qent_head, ipqe_q);
    285       1.7     rmind 	} else {
    286       1.7     rmind 		p = TAILQ_LAST(&fp->ipq_fragq, ipfr_qent_head);
    287       1.7     rmind 	}
    288       1.1     rmind 
    289       1.1     rmind 	/*
    290  1.17.2.1  christos 	 * Look at the preceding segment.
    291  1.17.2.1  christos 	 *
    292  1.17.2.1  christos 	 * If it provides some of our data already, in part or entirely, trim
    293  1.17.2.1  christos 	 * us or drop us.
    294  1.17.2.1  christos 	 *
    295  1.17.2.1  christos 	 * If a preceding segment exists, and was marked as the last segment,
    296  1.17.2.1  christos 	 * drop us.
    297       1.1     rmind 	 */
    298       1.1     rmind 	if (p != NULL) {
    299  1.17.2.1  christos 		i = p->ipqe_off + p->ipqe_len - ipqe->ipqe_off;
    300       1.1     rmind 		if (i > 0) {
    301  1.17.2.1  christos 			if (i >= ipqe->ipqe_len) {
    302       1.1     rmind 				goto dropfrag;
    303       1.1     rmind 			}
    304       1.1     rmind 			m_adj(ipqe->ipqe_m, i);
    305  1.17.2.1  christos 			ipqe->ipqe_off = ipqe->ipqe_off + i;
    306  1.17.2.1  christos 			ipqe->ipqe_len = ipqe->ipqe_len - i;
    307       1.1     rmind 		}
    308       1.1     rmind 	}
    309  1.17.2.1  christos 	if (p != NULL && !p->ipqe_mff) {
    310  1.17.2.1  christos 		goto dropfrag;
    311  1.17.2.1  christos 	}
    312       1.1     rmind 
    313       1.1     rmind 	/*
    314  1.17.2.1  christos 	 * Look at the segments that follow.
    315  1.17.2.1  christos 	 *
    316  1.17.2.1  christos 	 * If we cover them, in part or entirely, trim them or dequeue them.
    317  1.17.2.1  christos 	 *
    318  1.17.2.1  christos 	 * If a following segment exists, and we are marked as the last
    319  1.17.2.1  christos 	 * segment, drop us.
    320       1.1     rmind 	 */
    321       1.7     rmind 	while (q != NULL) {
    322  1.17.2.1  christos 		i = ipqe->ipqe_off + ipqe->ipqe_len - q->ipqe_off;
    323  1.17.2.1  christos 		if (i <= 0) {
    324       1.7     rmind 			break;
    325       1.7     rmind 		}
    326  1.17.2.1  christos 		if (i < q->ipqe_len) {
    327  1.17.2.1  christos 			q->ipqe_off = q->ipqe_off + i;
    328  1.17.2.1  christos 			q->ipqe_len = q->ipqe_len - i;
    329       1.1     rmind 			m_adj(q->ipqe_m, i);
    330       1.1     rmind 			break;
    331       1.1     rmind 		}
    332       1.1     rmind 		nq = TAILQ_NEXT(q, ipqe_q);
    333       1.1     rmind 		m_freem(q->ipqe_m);
    334       1.1     rmind 		TAILQ_REMOVE(&fp->ipq_fragq, q, ipqe_q);
    335       1.4     rmind 		pool_cache_put(ipfren_cache, q);
    336       1.1     rmind 		fp->ipq_nfrags--;
    337       1.1     rmind 		ip_nfrags--;
    338       1.7     rmind 		q = nq;
    339       1.1     rmind 	}
    340  1.17.2.1  christos 	if (q != NULL && !ipqe->ipqe_mff) {
    341  1.17.2.1  christos 		goto dropfrag;
    342  1.17.2.1  christos 	}
    343       1.1     rmind 
    344       1.1     rmind insert:
    345       1.1     rmind 	/*
    346       1.1     rmind 	 * Stick new segment in its place; check for complete reassembly.
    347       1.1     rmind 	 */
    348       1.1     rmind 	if (p == NULL) {
    349       1.1     rmind 		TAILQ_INSERT_HEAD(&fp->ipq_fragq, ipqe, ipqe_q);
    350       1.1     rmind 	} else {
    351       1.1     rmind 		TAILQ_INSERT_AFTER(&fp->ipq_fragq, p, ipqe, ipqe_q);
    352       1.1     rmind 	}
    353       1.1     rmind 	next = 0;
    354       1.7     rmind 	TAILQ_FOREACH(q, &fp->ipq_fragq, ipqe_q) {
    355  1.17.2.1  christos 		if (q->ipqe_off != next) {
    356       1.4     rmind 			mutex_exit(&ipfr_lock);
    357       1.1     rmind 			return NULL;
    358       1.1     rmind 		}
    359  1.17.2.1  christos 		next += q->ipqe_len;
    360       1.1     rmind 	}
    361       1.7     rmind 	p = TAILQ_LAST(&fp->ipq_fragq, ipfr_qent_head);
    362       1.1     rmind 	if (p->ipqe_mff) {
    363       1.4     rmind 		mutex_exit(&ipfr_lock);
    364       1.1     rmind 		return NULL;
    365       1.1     rmind 	}
    366       1.7     rmind 
    367       1.1     rmind 	/*
    368       1.4     rmind 	 * Reassembly is complete.  Check for a bogus message size.
    369       1.1     rmind 	 */
    370       1.1     rmind 	q = TAILQ_FIRST(&fp->ipq_fragq);
    371       1.1     rmind 	ip = q->ipqe_ip;
    372       1.1     rmind 	if ((next + (ip->ip_hl << 2)) > IP_MAXPACKET) {
    373       1.1     rmind 		IP_STATINC(IP_STAT_TOOLONG);
    374       1.1     rmind 		ip_freef(fp);
    375       1.4     rmind 		mutex_exit(&ipfr_lock);
    376       1.1     rmind 		return NULL;
    377       1.1     rmind 	}
    378       1.4     rmind 	LIST_REMOVE(fp, ipq_q);
    379       1.4     rmind 	ip_nfrags -= fp->ipq_nfrags;
    380       1.4     rmind 	ip_nfragpackets--;
    381       1.4     rmind 	mutex_exit(&ipfr_lock);
    382       1.4     rmind 
    383       1.4     rmind 	/* Concatenate all fragments. */
    384       1.1     rmind 	m = q->ipqe_m;
    385       1.1     rmind 	t = m->m_next;
    386       1.1     rmind 	m->m_next = NULL;
    387       1.1     rmind 	m_cat(m, t);
    388       1.1     rmind 	nq = TAILQ_NEXT(q, ipqe_q);
    389       1.4     rmind 	pool_cache_put(ipfren_cache, q);
    390       1.4     rmind 
    391       1.1     rmind 	for (q = nq; q != NULL; q = nq) {
    392       1.1     rmind 		t = q->ipqe_m;
    393       1.1     rmind 		nq = TAILQ_NEXT(q, ipqe_q);
    394       1.4     rmind 		pool_cache_put(ipfren_cache, q);
    395      1.16      maxv 		m_remove_pkthdr(t);
    396       1.1     rmind 		m_cat(m, t);
    397       1.1     rmind 	}
    398       1.1     rmind 
    399       1.1     rmind 	/*
    400       1.1     rmind 	 * Create header for new packet by modifying header of first
    401       1.1     rmind 	 * packet.  Dequeue and discard fragment reassembly header.  Make
    402       1.1     rmind 	 * header visible.
    403       1.1     rmind 	 */
    404       1.2     rmind 	ip->ip_len = htons((ip->ip_hl << 2) + next);
    405  1.17.2.1  christos 	ip->ip_off = htons(0);
    406       1.1     rmind 	ip->ip_src = fp->ipq_src;
    407       1.1     rmind 	ip->ip_dst = fp->ipq_dst;
    408       1.5     enami 	free(fp, M_FTABLE);
    409       1.2     rmind 
    410       1.1     rmind 	m->m_len += (ip->ip_hl << 2);
    411       1.1     rmind 	m->m_data -= (ip->ip_hl << 2);
    412       1.4     rmind 
    413       1.4     rmind 	/* Fix up mbuf.  XXX This should be done elsewhere. */
    414      1.14      maxv 	{
    415      1.14      maxv 		KASSERT(m->m_flags & M_PKTHDR);
    416       1.1     rmind 		int plen = 0;
    417       1.1     rmind 		for (t = m; t; t = t->m_next) {
    418       1.1     rmind 			plen += t->m_len;
    419       1.1     rmind 		}
    420       1.1     rmind 		m->m_pkthdr.len = plen;
    421       1.1     rmind 		m->m_pkthdr.csum_flags = 0;
    422       1.1     rmind 	}
    423       1.1     rmind 	return m;
    424       1.1     rmind 
    425       1.1     rmind dropfrag:
    426       1.1     rmind 	if (fp != NULL) {
    427       1.1     rmind 		fp->ipq_nfrags--;
    428       1.1     rmind 	}
    429       1.1     rmind 	ip_nfrags--;
    430       1.1     rmind 	IP_STATINC(IP_STAT_FRAGDROPPED);
    431       1.4     rmind 	mutex_exit(&ipfr_lock);
    432       1.4     rmind 
    433       1.4     rmind 	pool_cache_put(ipfren_cache, ipqe);
    434       1.1     rmind 	m_freem(m);
    435       1.1     rmind 	return NULL;
    436       1.1     rmind }
    437       1.1     rmind 
    438       1.1     rmind /*
    439       1.1     rmind  * ip_freef:
    440       1.1     rmind  *
    441       1.1     rmind  *	Free a fragment reassembly header and all associated datagrams.
    442       1.1     rmind  */
    443       1.2     rmind static void
    444       1.3     rmind ip_freef(ipfr_queue_t *fp)
    445       1.1     rmind {
    446       1.4     rmind 	ipfr_qent_t *q;
    447       1.1     rmind 
    448       1.4     rmind 	KASSERT(mutex_owned(&ipfr_lock));
    449       1.1     rmind 
    450       1.4     rmind 	LIST_REMOVE(fp, ipq_q);
    451       1.4     rmind 	ip_nfrags -= fp->ipq_nfrags;
    452       1.4     rmind 	ip_nfragpackets--;
    453       1.4     rmind 
    454       1.4     rmind 	while ((q = TAILQ_FIRST(&fp->ipq_fragq)) != NULL) {
    455       1.4     rmind 		TAILQ_REMOVE(&fp->ipq_fragq, q, ipqe_q);
    456       1.1     rmind 		m_freem(q->ipqe_m);
    457       1.4     rmind 		pool_cache_put(ipfren_cache, q);
    458       1.1     rmind 	}
    459       1.1     rmind 	free(fp, M_FTABLE);
    460       1.1     rmind }
    461       1.1     rmind 
    462       1.1     rmind /*
    463       1.1     rmind  * ip_reass_ttl_decr:
    464       1.1     rmind  *
    465       1.1     rmind  *	Decrement TTL of all reasembly queue entries by `ticks'.  Count
    466       1.1     rmind  *	number of distinct fragments (as opposed to partial, fragmented
    467       1.1     rmind  *	datagrams) inthe reassembly queue.  While we  traverse the entire
    468       1.1     rmind  *	reassembly queue, compute and return the median TTL over all
    469       1.1     rmind  *	fragments.
    470       1.1     rmind  */
    471       1.1     rmind static u_int
    472       1.1     rmind ip_reass_ttl_decr(u_int ticks)
    473       1.1     rmind {
    474       1.1     rmind 	u_int nfrags, median, dropfraction, keepfraction;
    475       1.3     rmind 	ipfr_queue_t *fp, *nfp;
    476       1.1     rmind 	int i;
    477       1.1     rmind 
    478       1.1     rmind 	nfrags = 0;
    479       1.1     rmind 	memset(fragttl_histo, 0, sizeof(fragttl_histo));
    480       1.1     rmind 
    481       1.1     rmind 	for (i = 0; i < IPREASS_HASH_SIZE; i++) {
    482       1.3     rmind 		for (fp = LIST_FIRST(&ip_frags[i]); fp != NULL; fp = nfp) {
    483       1.1     rmind 			fp->ipq_ttl = ((fp->ipq_ttl <= ticks) ?
    484       1.1     rmind 			    0 : fp->ipq_ttl - ticks);
    485       1.1     rmind 			nfp = LIST_NEXT(fp, ipq_q);
    486       1.1     rmind 			if (fp->ipq_ttl == 0) {
    487       1.1     rmind 				IP_STATINC(IP_STAT_FRAGTIMEOUT);
    488       1.1     rmind 				ip_freef(fp);
    489       1.1     rmind 			} else {
    490       1.1     rmind 				nfrags += fp->ipq_nfrags;
    491       1.1     rmind 				fragttl_histo[fp->ipq_ttl] += fp->ipq_nfrags;
    492       1.1     rmind 			}
    493       1.1     rmind 		}
    494       1.1     rmind 	}
    495       1.1     rmind 
    496       1.1     rmind 	KASSERT(ip_nfrags == nfrags);
    497       1.1     rmind 
    498       1.1     rmind 	/* Find median (or other drop fraction) in histogram. */
    499       1.1     rmind 	dropfraction = (ip_nfrags / 2);
    500       1.1     rmind 	keepfraction = ip_nfrags - dropfraction;
    501       1.1     rmind 	for (i = IPFRAGTTL, median = 0; i >= 0; i--) {
    502       1.1     rmind 		median += fragttl_histo[i];
    503       1.1     rmind 		if (median >= keepfraction)
    504       1.1     rmind 			break;
    505       1.1     rmind 	}
    506       1.1     rmind 
    507       1.1     rmind 	/* Return TTL of median (or other fraction). */
    508       1.1     rmind 	return (u_int)i;
    509       1.1     rmind }
    510       1.1     rmind 
    511       1.1     rmind static void
    512       1.1     rmind ip_reass_drophalf(void)
    513       1.1     rmind {
    514       1.1     rmind 	u_int median_ticks;
    515       1.1     rmind 
    516       1.4     rmind 	KASSERT(mutex_owned(&ipfr_lock));
    517       1.4     rmind 
    518       1.1     rmind 	/*
    519       1.1     rmind 	 * Compute median TTL of all fragments, and count frags
    520       1.1     rmind 	 * with that TTL or lower (roughly half of all fragments).
    521       1.1     rmind 	 */
    522       1.1     rmind 	median_ticks = ip_reass_ttl_decr(0);
    523       1.1     rmind 
    524       1.1     rmind 	/* Drop half. */
    525       1.1     rmind 	median_ticks = ip_reass_ttl_decr(median_ticks);
    526       1.1     rmind }
    527       1.1     rmind 
    528       1.1     rmind /*
    529       1.1     rmind  * ip_reass_drain: drain off all datagram fragments.  Do not acquire
    530       1.1     rmind  * softnet_lock as can be called from hardware interrupt context.
    531       1.1     rmind  */
    532       1.1     rmind void
    533       1.1     rmind ip_reass_drain(void)
    534       1.1     rmind {
    535       1.1     rmind 
    536       1.1     rmind 	/*
    537       1.1     rmind 	 * We may be called from a device's interrupt context.  If
    538       1.1     rmind 	 * the ipq is already busy, just bail out now.
    539       1.1     rmind 	 */
    540       1.4     rmind 	if (mutex_tryenter(&ipfr_lock)) {
    541       1.1     rmind 		/*
    542       1.1     rmind 		 * Drop half the total fragments now. If more mbufs are
    543       1.1     rmind 		 * needed, we will be called again soon.
    544       1.1     rmind 		 */
    545       1.1     rmind 		ip_reass_drophalf();
    546       1.4     rmind 		mutex_exit(&ipfr_lock);
    547       1.1     rmind 	}
    548       1.1     rmind }
    549       1.1     rmind 
    550       1.1     rmind /*
    551       1.1     rmind  * ip_reass_slowtimo:
    552       1.1     rmind  *
    553       1.1     rmind  *	If a timer expires on a reassembly queue, discard it.
    554       1.1     rmind  */
    555       1.1     rmind void
    556       1.1     rmind ip_reass_slowtimo(void)
    557       1.1     rmind {
    558       1.1     rmind 	static u_int dropscanidx = 0;
    559       1.1     rmind 	u_int i, median_ttl;
    560       1.1     rmind 
    561       1.4     rmind 	mutex_enter(&ipfr_lock);
    562       1.1     rmind 
    563       1.1     rmind 	/* Age TTL of all fragments by 1 tick .*/
    564       1.1     rmind 	median_ttl = ip_reass_ttl_decr(1);
    565       1.1     rmind 
    566       1.1     rmind 	/* Make sure fragment limit is up-to-date. */
    567       1.1     rmind 	CHECK_NMBCLUSTER_PARAMS();
    568       1.1     rmind 
    569       1.1     rmind 	/* If we have too many fragments, drop the older half. */
    570       1.1     rmind 	if (ip_nfrags > ip_maxfrags) {
    571       1.1     rmind 		ip_reass_ttl_decr(median_ttl);
    572       1.1     rmind 	}
    573       1.1     rmind 
    574       1.1     rmind 	/*
    575       1.1     rmind 	 * If we are over the maximum number of fragmented packets (due to
    576       1.1     rmind 	 * the limit being lowered), drain off enough to get down to the
    577       1.1     rmind 	 * new limit.  Start draining from the reassembly hashqueue most
    578       1.1     rmind 	 * recently drained.
    579       1.1     rmind 	 */
    580       1.1     rmind 	if (ip_maxfragpackets < 0)
    581       1.1     rmind 		;
    582       1.1     rmind 	else {
    583       1.1     rmind 		int wrapped = 0;
    584       1.1     rmind 
    585       1.1     rmind 		i = dropscanidx;
    586       1.1     rmind 		while (ip_nfragpackets > ip_maxfragpackets && wrapped == 0) {
    587       1.3     rmind 			while (LIST_FIRST(&ip_frags[i]) != NULL) {
    588       1.3     rmind 				ip_freef(LIST_FIRST(&ip_frags[i]));
    589       1.1     rmind 			}
    590       1.1     rmind 			if (++i >= IPREASS_HASH_SIZE) {
    591       1.1     rmind 				i = 0;
    592       1.1     rmind 			}
    593       1.1     rmind 			/*
    594       1.1     rmind 			 * Do not scan forever even if fragment counters are
    595       1.1     rmind 			 * wrong: stop after scanning entire reassembly queue.
    596       1.1     rmind 			 */
    597       1.1     rmind 			if (i == dropscanidx) {
    598       1.1     rmind 				wrapped = 1;
    599       1.1     rmind 			}
    600       1.1     rmind 		}
    601       1.1     rmind 		dropscanidx = i;
    602       1.1     rmind 	}
    603       1.4     rmind 	mutex_exit(&ipfr_lock);
    604       1.1     rmind }
    605       1.2     rmind 
    606       1.2     rmind /*
    607       1.2     rmind  * ip_reass_packet: generic routine to perform IP reassembly.
    608       1.2     rmind  *
    609       1.2     rmind  * => Passed fragment should have IP_MF flag and/or offset set.
    610       1.2     rmind  * => Fragment should not have other than IP_MF flags set.
    611       1.2     rmind  *
    612       1.7     rmind  * => Returns 0 on success or error otherwise.
    613       1.7     rmind  * => On complete, m0 represents a constructed final packet.
    614       1.2     rmind  */
    615       1.2     rmind int
    616  1.17.2.1  christos ip_reass_packet(struct mbuf **m0)
    617       1.2     rmind {
    618  1.17.2.1  christos 	struct mbuf *m = *m0;
    619  1.17.2.1  christos 	struct ip *ip = mtod(m, struct ip *);
    620       1.7     rmind 	const int hlen = ip->ip_hl << 2;
    621       1.7     rmind 	const int len = ntohs(ip->ip_len);
    622      1.17      maxv 	int ipsecflags = m->m_flags & (M_DECRYPTED|M_AUTHIPHDR);
    623       1.3     rmind 	ipfr_queue_t *fp;
    624       1.3     rmind 	ipfr_qent_t *ipqe;
    625       1.7     rmind 	u_int hash, off, flen;
    626       1.7     rmind 	bool mff;
    627       1.7     rmind 
    628       1.7     rmind 	/*
    629       1.7     rmind 	 * Prevent TCP blind data attacks by not allowing non-initial
    630       1.7     rmind 	 * fragments to start at less than 68 bytes (minimal fragment
    631       1.7     rmind 	 * size) and making sure the first fragment is at least 68
    632       1.7     rmind 	 * bytes.
    633       1.7     rmind 	 */
    634       1.7     rmind 	off = (ntohs(ip->ip_off) & IP_OFFMASK) << 3;
    635       1.7     rmind 	if ((off > 0 ? off + hlen : len) < IP_MINFRAGSIZE - 1) {
    636       1.7     rmind 		IP_STATINC(IP_STAT_BADFRAGS);
    637       1.7     rmind 		return EINVAL;
    638       1.7     rmind 	}
    639       1.7     rmind 
    640      1.12      maxv 	if (off + len > IP_MAXPACKET) {
    641      1.13      maxv 		IP_STATINC(IP_STAT_TOOLONG);
    642      1.12      maxv 		return EINVAL;
    643      1.12      maxv 	}
    644      1.12      maxv 
    645       1.7     rmind 	/*
    646       1.7     rmind 	 * Fragment length and MF flag.  Make sure that fragments have
    647       1.7     rmind 	 * a data length which is non-zero and multiple of 8 bytes.
    648       1.7     rmind 	 */
    649       1.7     rmind 	flen = ntohs(ip->ip_len) - hlen;
    650       1.7     rmind 	mff = (ip->ip_off & htons(IP_MF)) != 0;
    651       1.7     rmind 	if (mff && (flen == 0 || (flen & 0x7) != 0)) {
    652       1.7     rmind 		IP_STATINC(IP_STAT_BADFRAGS);
    653       1.7     rmind 		return EINVAL;
    654       1.7     rmind 	}
    655       1.7     rmind 
    656       1.2     rmind 	/* Look for queue of fragments of this datagram. */
    657       1.4     rmind 	mutex_enter(&ipfr_lock);
    658       1.3     rmind 	hash = IPREASS_HASH(ip->ip_src.s_addr, ip->ip_id);
    659       1.3     rmind 	LIST_FOREACH(fp, &ip_frags[hash], ipq_q) {
    660       1.3     rmind 		if (ip->ip_id != fp->ipq_id)
    661       1.3     rmind 			continue;
    662       1.3     rmind 		if (!in_hosteq(ip->ip_src, fp->ipq_src))
    663       1.3     rmind 			continue;
    664       1.3     rmind 		if (!in_hosteq(ip->ip_dst, fp->ipq_dst))
    665       1.3     rmind 			continue;
    666       1.3     rmind 		if (ip->ip_p != fp->ipq_p)
    667       1.3     rmind 			continue;
    668       1.3     rmind 		break;
    669       1.3     rmind 	}
    670       1.2     rmind 
    671      1.17      maxv 	if (fp) {
    672      1.17      maxv 		/* All fragments must have the same IPsec flags. */
    673      1.17      maxv 		if (fp->ipq_ipsec != ipsecflags) {
    674      1.17      maxv 			IP_STATINC(IP_STAT_BADFRAGS);
    675      1.17      maxv 			mutex_exit(&ipfr_lock);
    676      1.17      maxv 			return EINVAL;
    677      1.17      maxv 		}
    678      1.17      maxv 
    679      1.17      maxv 		/* Make sure that TOS matches previous fragments. */
    680      1.17      maxv 		if (fp->ipq_tos != ip->ip_tos) {
    681      1.17      maxv 			IP_STATINC(IP_STAT_BADFRAGS);
    682      1.17      maxv 			mutex_exit(&ipfr_lock);
    683      1.17      maxv 			return EINVAL;
    684      1.17      maxv 		}
    685       1.2     rmind 	}
    686       1.2     rmind 
    687       1.2     rmind 	/*
    688       1.2     rmind 	 * Create new entry and attempt to reassembly.
    689       1.2     rmind 	 */
    690       1.2     rmind 	IP_STATINC(IP_STAT_FRAGMENTS);
    691       1.4     rmind 	ipqe = pool_cache_get(ipfren_cache, PR_NOWAIT);
    692       1.2     rmind 	if (ipqe == NULL) {
    693       1.2     rmind 		IP_STATINC(IP_STAT_RCVMEMDROP);
    694       1.4     rmind 		mutex_exit(&ipfr_lock);
    695       1.2     rmind 		return ENOMEM;
    696       1.2     rmind 	}
    697       1.2     rmind 	ipqe->ipqe_mff = mff;
    698       1.2     rmind 	ipqe->ipqe_m = m;
    699       1.2     rmind 	ipqe->ipqe_ip = ip;
    700  1.17.2.1  christos 	ipqe->ipqe_off = off;
    701  1.17.2.1  christos 	ipqe->ipqe_len = flen;
    702       1.2     rmind 
    703       1.7     rmind 	*m0 = ip_reass(ipqe, fp, hash);
    704       1.7     rmind 	if (*m0) {
    705       1.7     rmind 		/* Note that finally reassembled. */
    706       1.2     rmind 		IP_STATINC(IP_STAT_REASSEMBLED);
    707       1.2     rmind 	}
    708       1.2     rmind 	return 0;
    709       1.2     rmind }
    710