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