xref: /freebsd/sys/netinet/tcp_stacks/tailq_hash.c (revision e18b97bd63a8112625f7014d2326ecf533b710dd)

#include <sys/cdefs.h>
#include "opt_inet.h"
#include "opt_inet6.h"
#include "opt_ipsec.h"
#include "opt_ratelimit.h"
#include "opt_kern_tls.h"
#include <sys/param.h>
#include <sys/arb.h>
#include <sys/module.h>
#include <sys/kernel.h>
#ifdef TCP_HHOOK
#include <sys/hhook.h>
#endif
#include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/lock.h>
#include <sys/mutex.h>
#include <sys/mbuf.h>
#include <sys/proc.h>		/* for proc0 declaration */
#include <sys/socket.h>
#include <sys/socketvar.h>
#include <sys/sysctl.h>
#include <sys/systm.h>
#ifdef STATS
#include <sys/qmath.h>
#include <sys/tree.h>
#include <sys/stats.h> /* Must come after qmath.h and tree.h */
#else
#include <sys/tree.h>
#endif
#include <sys/refcount.h>
#include <sys/queue.h>
#include <sys/tim_filter.h>
#include <sys/smp.h>
#include <sys/kthread.h>
#include <sys/kern_prefetch.h>
#include <sys/protosw.h>
#ifdef TCP_ACCOUNTING
#include <sys/sched.h>
#include <machine/cpu.h>
#endif
#include <vm/uma.h>

#include <net/route.h>
#include <net/route/nhop.h>
#include <net/vnet.h>

#define TCPSTATES		/* for logging */

#include <netinet/in.h>
#include <netinet/in_kdtrace.h>
#include <netinet/in_pcb.h>
#include <netinet/ip.h>
#include <netinet/ip_icmp.h>	/* required for icmp_var.h */
#include <netinet/icmp_var.h>	/* for ICMP_BANDLIM */
#include <netinet/ip_var.h>
#include <netinet/ip6.h>
#include <netinet6/in6_pcb.h>
#include <netinet6/ip6_var.h>
#include <netinet/tcp.h>
#include <netinet/tcp_fsm.h>
#include <netinet/tcp_seq.h>
#include <netinet/tcp_timer.h>
#include <netinet/tcp_var.h>
#include <netinet/tcp_log_buf.h>
#include <netinet/tcp_syncache.h>
#include <netinet/tcp_hpts.h>
#include <netinet/tcp_accounting.h>
#include <netinet/tcpip.h>
#include <netinet/cc/cc.h>
#include <netinet/cc/cc_newreno.h>
#include <netinet/tcp_fastopen.h>
#include <netinet/tcp_lro.h>
#ifdef NETFLIX_SHARED_CWND
#include <netinet/tcp_shared_cwnd.h>
#endif
#ifdef TCP_OFFLOAD
#include <netinet/tcp_offload.h>
#endif
#ifdef INET6
#include <netinet6/tcp6_var.h>
#endif
#include <netinet/tcp_ecn.h>

#include <netipsec/ipsec_support.h>

#if defined(IPSEC) || defined(IPSEC_SUPPORT)
#include <netipsec/ipsec.h>
#include <netipsec/ipsec6.h>
#endif				/* IPSEC */

#include <netinet/udp.h>
#include <netinet/udp_var.h>
#include <machine/in_cksum.h>

#ifdef MAC
#include <security/mac/mac_framework.h>
#endif
#include "sack_filter.h"
#include "tcp_rack.h"
#include "tailq_hash.h"
#include "opt_global.h"


struct rack_sendmap *
tqhash_min(struct tailq_hash *hs)
{
	struct rack_sendmap *rsm;

	rsm = hs->rsm_min;
	return(rsm);
}

struct rack_sendmap *
tqhash_max(struct tailq_hash *hs)
{
	struct rack_sendmap *rsm;

	rsm = hs->rsm_max;
	return (rsm);
}

int
tqhash_empty(struct tailq_hash *hs)
{
	if (hs->count == 0)
		return(1);
	return(0);
}

struct rack_sendmap *
tqhash_find(struct tailq_hash *hs, uint32_t seq)
{
	struct rack_sendmap *e;
	int bindex, pbucket, fc = 1;

	if ((SEQ_LT(seq, hs->min)) ||
	    (hs->count == 0) ||
	    (SEQ_GEQ(seq, hs->max))) {
		/* Not here */
		return (NULL);
	}
	bindex = seq / SEQ_BUCKET_SIZE;
	bindex %= MAX_HASH_ENTRIES;
	/* Lets look through the bucket it belongs to */
	if (TAILQ_EMPTY(&hs->ht[bindex])) {
		goto look_backwards;
	}
	TAILQ_FOREACH(e, &hs->ht[bindex], next) {
		if (fc == 1) {
			/*
			 * Special check for when a cum-ack
			 * as moved up over a seq and now its
			 * a bucket behind where it belongs. In
			 * the case of SACKs which create new rsm's
			 * this won't occur.
			 */
			if (SEQ_GT(e->r_start, seq)) {
				goto look_backwards;
			}
			fc = 0;
		}
		if (SEQ_GEQ(seq, e->r_start) &&
		    (SEQ_LT(seq, e->r_end))) {
			/* Its in this block */
			return (e);
		}
	}
	/* Did not find it */
	return (NULL);
look_backwards:
	if (bindex == 0)
		pbucket = MAX_HASH_ENTRIES - 1;
	else
		pbucket = bindex - 1;
	TAILQ_FOREACH_REVERSE(e, &hs->ht[pbucket], rack_head, next) {
		if (SEQ_GEQ(seq, e->r_start) &&
		    (SEQ_LT(seq, e->r_end))) {
			/* Its in this block */
			return (e);
		}
		if (SEQ_GEQ(e->r_end, seq))
			break;
	}
	return (NULL);
}

struct rack_sendmap *
tqhash_next(struct tailq_hash *hs, struct rack_sendmap *rsm)
{
	struct rack_sendmap *e;

	e = TAILQ_NEXT(rsm, next);
	if (e == NULL) {
		/* Move to next bucket */
		int nxt;

		nxt = rsm->bindex + 1;
		if (nxt >= MAX_HASH_ENTRIES)
			nxt = 0;
		e = TAILQ_FIRST(&hs->ht[nxt]);
	}
	return(e);
}

struct rack_sendmap *
tqhash_prev(struct tailq_hash *hs, struct rack_sendmap *rsm)
{
	struct rack_sendmap *e;

	e = TAILQ_PREV(rsm, rack_head, next);
	if (e == NULL) {
		int prev;

		if (rsm->bindex > 0)
			prev = rsm->bindex - 1;
		else
			prev = MAX_HASH_ENTRIES - 1;
		e = TAILQ_LAST(&hs->ht[prev], rack_head);
	}
	return (e);
}

void
tqhash_remove(struct tailq_hash *hs, struct rack_sendmap *rsm, int type)
{

	hs->count--;
	if (hs->count == 0) {
		hs->min = hs->max;
		hs->rsm_max = hs->rsm_min = NULL;
	} else if (type == REMOVE_TYPE_CUMACK) {
		hs->min = rsm->r_end;
		hs->rsm_min = tqhash_next(hs, rsm);
	} else if (rsm == hs->rsm_max) {
		hs->rsm_max = tqhash_prev(hs, rsm);
		hs->max = hs->rsm_max->r_end;
	}
	TAILQ_REMOVE(&hs->ht[rsm->bindex], rsm, next);
}

int
tqhash_insert(struct tailq_hash *hs, struct rack_sendmap *rsm)
{
	struct rack_sendmap *e, *l;
	int inserted = 0;
	uint32_t ebucket;

#ifdef INVARIANTS
	if (hs->count > 0) {
		if ((rsm->r_end - hs->min) >  MAX_ALLOWED_SEQ_RANGE) {
			return (-1);
		}
		e = tqhash_find(hs, rsm->r_start);
		if (e) {
			return (-2);
		}
	}
#endif
	rsm->bindex = rsm->r_start / SEQ_BUCKET_SIZE;
	rsm->bindex %= MAX_HASH_ENTRIES;
	ebucket = rsm->r_end / SEQ_BUCKET_SIZE;
	ebucket %= MAX_HASH_ENTRIES;
	if (ebucket != rsm->bindex) {
		/* This RSM straddles the bucket boundary */
		rsm->r_flags |= RACK_STRADDLE;
	} else {
		rsm->r_flags &= ~RACK_STRADDLE;
	}
	if (hs->count == 0) {
		/* Special case */
		hs->min = rsm->r_start;
		hs->max = rsm->r_end;
		hs->rsm_min = hs->rsm_max = rsm;
		hs->count = 1;
	} else {
		hs->count++;
		if (SEQ_GEQ(rsm->r_end, hs->max)) {
			hs->max = rsm->r_end;
			hs->rsm_max = rsm;
		} if (SEQ_LEQ(rsm->r_start, hs->min)) {
			hs->min = rsm->r_start;
			hs->rsm_min = rsm;
		}
	}
	/* Check the common case of inserting at the end */
	l = TAILQ_LAST(&hs->ht[rsm->bindex], rack_head);
	if ((l == NULL) || (SEQ_GT(rsm->r_start, l->r_start))) {
		TAILQ_INSERT_TAIL(&hs->ht[rsm->bindex], rsm, next);
		return (0);
	}
	TAILQ_FOREACH(e, &hs->ht[rsm->bindex], next) {
		if (SEQ_LEQ(rsm->r_start, e->r_start)) {
			inserted = 1;
			TAILQ_INSERT_BEFORE(e, rsm, next);
			break;
		}
	}
	if (inserted == 0) {
		TAILQ_INSERT_TAIL(&hs->ht[rsm->bindex], rsm, next);
	}
	return (0);
}

void
tqhash_init(struct tailq_hash *hs)
{
	int i;

	for(i = 0; i < MAX_HASH_ENTRIES; i++) {
		TAILQ_INIT(&hs->ht[i]);
	}
	hs->min = hs->max = 0;
	hs->rsm_min = hs->rsm_max = NULL;
	hs->count = 0;
}

int
tqhash_trim(struct tailq_hash *hs, uint32_t th_ack)
{
	struct rack_sendmap *rsm;

	if (SEQ_LT(th_ack, hs->min)) {
		/* It can't be behind our current min */
		return (-1);
	}
	if (SEQ_GEQ(th_ack, hs->max)) {
		/*  It can't be beyond or at our current max */
		return (-2);
	}
	rsm = tqhash_min(hs);
	if (rsm == NULL) {
		/* nothing to trim */
		return (-3);
	}
	if (SEQ_GEQ(th_ack, rsm->r_end)) {
		/*
		 * You can't trim all bytes instead
		 * you need to remove it.
		 */
		return (-4);
	}
	if (SEQ_GT(th_ack, hs->min))
	    hs->min = th_ack;
	/*
	 * Should we trim it for the caller?
	 * they may have already which is ok...
	 */
	if (SEQ_GT(th_ack, rsm->r_start)) {
		rsm->r_start = th_ack;
	}
	return (0);
}

void
tqhash_update_end(struct tailq_hash *hs, struct rack_sendmap *rsm,
    uint32_t th_ack)
{
	if (hs->max == rsm->r_end)
		hs->max = th_ack;
	rsm->r_end = th_ack;
}