diff --git a/sys/netinet/tcp_stacks/tailq_hash.c b/sys/netinet/tcp_stacks/tailq_hash.c index 0792905e0128..5977bf874950 100644 --- a/sys/netinet/tcp_stacks/tailq_hash.c +++ b/sys/netinet/tcp_stacks/tailq_hash.c @@ -1,342 +1,341 @@ #include #include "opt_inet.h" #include "opt_inet6.h" #include "opt_ipsec.h" #include "opt_ratelimit.h" #include "opt_kern_tls.h" #include #include #include #include #ifdef TCP_HHOOK #include #endif #include #include #include #include #include #include /* for proc0 declaration */ #include #include #include #include #ifdef STATS #include #include #include /* Must come after qmath.h and tree.h */ #else #include #endif #include #include #include #include #include #include #include #ifdef TCP_ACCOUNTING #include #include #endif #include #include #include #include #define TCPSTATES /* for logging */ #include #include #include #include #include /* required for icmp_var.h */ #include /* for ICMP_BANDLIM */ #include #include #include #include #include -#define TCPOUTFLAGS #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef NETFLIX_SHARED_CWND #include #endif #ifdef TCP_OFFLOAD #include #endif #ifdef INET6 #include #endif #include #include #if defined(IPSEC) || defined(IPSEC_SUPPORT) #include #include #endif /* IPSEC */ #include #include #include #ifdef MAC #include #endif #include "sack_filter.h" #include "tcp_rack.h" #include "tailq_hash.h" struct rack_sendmap * tqhash_min(struct tailq_hash *hs) { struct rack_sendmap *rsm; rsm = tqhash_find(hs, hs->min); return(rsm); } struct rack_sendmap * tqhash_max(struct tailq_hash *hs) { struct rack_sendmap *rsm; rsm = tqhash_find(hs, (hs->max - 1)); 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) { TAILQ_REMOVE(&hs->ht[rsm->bindex], rsm, next); hs->count--; if (hs->count == 0) { hs->min = hs->max; } else if (type == REMOVE_TYPE_CUMACK) { hs->min = rsm->r_end; } } int tqhash_insert(struct tailq_hash *hs, struct rack_sendmap *rsm) { struct rack_sendmap *e, *l; int inserted = 0; uint32_t ebucket; 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); } } 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->count = 1; } else { hs->count++; if (SEQ_GT(rsm->r_end, hs->max)) hs->max = rsm->r_end; if (SEQ_LT(rsm->r_start, hs->min)) hs->min = rsm->r_start; } /* 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->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); }