summaryrefslogtreecommitdiff
path: root/sys/netinet
diff options
context:
space:
mode:
authorthorpej <thorpej@NetBSD.org>1999-04-29 03:54:22 +0000
committerthorpej <thorpej@NetBSD.org>1999-04-29 03:54:22 +0000
commit2cd33a0ce1a8b37d443871c09ca2dbcbfbe61e99 (patch)
tree79a4761c1b9acb02368c4539e0040d95d2136725 /sys/netinet
parent53af2d00541712177f4d8f028807ac16af0088f7 (diff)
Implement retransmit logic for the SYN cache engine. Fixes a rare condition
where one side can think a connection exists, where the other side thinks the connection was never established. The original problem was first reported by Ty Sarna in PR #5909. The original fix I made to the code didn't cover all cases. The problem this fix addresses was reported by Christoph Badura via private e-mail. Many thanks to Bill Sommerfeld for helping me to test this code, and for finding a subtle bug.
Diffstat (limited to 'sys/netinet')
-rw-r--r--sys/netinet/in_proto.c5
-rw-r--r--sys/netinet/tcp_input.c248
-rw-r--r--sys/netinet/tcp_var.h23
3 files changed, 168 insertions, 108 deletions
diff --git a/sys/netinet/in_proto.c b/sys/netinet/in_proto.c
index 18f98ce1033..807f86226e6 100644
--- a/sys/netinet/in_proto.c
+++ b/sys/netinet/in_proto.c
@@ -1,4 +1,4 @@
-/* $NetBSD: in_proto.c,v 1.29 1999/01/14 01:16:55 thorpej Exp $ */
+/* $NetBSD: in_proto.c,v 1.30 1999/04/29 03:54:22 thorpej Exp $ */
/*
* Copyright (c) 1982, 1986, 1993
@@ -188,5 +188,4 @@ int tcp_syn_cache_size = TCP_SYN_HASH_SIZE;
int tcp_syn_cache_limit = TCP_SYN_HASH_SIZE*TCP_SYN_BUCKET_SIZE;
int tcp_syn_bucket_limit = 3*TCP_SYN_BUCKET_SIZE;
struct syn_cache_head tcp_syn_cache[TCP_SYN_HASH_SIZE];
-int tcp_syn_cache_interval = 8; /* runs timer every 4 seconds */
-int tcp_syn_cache_timeo = TCPTV_KEEP_INIT;
+int tcp_syn_cache_interval = 1; /* runs timer twice a second */
diff --git a/sys/netinet/tcp_input.c b/sys/netinet/tcp_input.c
index 0134f41ea46..fa28e925f91 100644
--- a/sys/netinet/tcp_input.c
+++ b/sys/netinet/tcp_input.c
@@ -1,4 +1,4 @@
-/* $NetBSD: tcp_input.c,v 1.79 1999/04/22 01:32:30 simonb Exp $ */
+/* $NetBSD: tcp_input.c,v 1.80 1999/04/29 03:54:22 thorpej Exp $ */
/*-
* Copyright (c) 1997, 1998, 1999 The NetBSD Foundation, Inc.
@@ -1846,13 +1846,11 @@ u_int32_t syn_hash1, syn_hash2;
((((sa)->s_addr^syn_hash1)*(((((u_int32_t)(dp))<<16) + \
((u_int32_t)(sp)))^syn_hash2)))
-LIST_HEAD(, syn_cache_head) tcp_syn_cache_queue;
-
-#define SYN_CACHE_RM(sc, scp) \
+#define SYN_CACHE_RM(sc) \
do { \
- TAILQ_REMOVE(&(scp)->sch_queue, (sc), sc_queue); \
- if (--(scp)->sch_length == 0) \
- LIST_REMOVE((scp), sch_headq); \
+ LIST_REMOVE((sc), sc_bucketq); \
+ tcp_syn_cache[(sc)->sc_bucketidx].sch_length--; \
+ TAILQ_REMOVE(&tcp_syn_cache_timeq[(sc)->sc_rxtshift], (sc), sc_timeq); \
syn_cache_count--; \
} while (0)
@@ -1867,17 +1865,33 @@ do { \
struct pool syn_cache_pool;
+/*
+ * We don't estimate RTT with SYNs, so each packet starts with the default
+ * RTT and each timer queue has a fixed timeout value. This allows us to
+ * optimize the timer queues somewhat.
+ */
+#define SYN_CACHE_TIMER_ARM(sc) \
+do { \
+ TCPT_RANGESET((sc)->sc_rxtcur, \
+ TCPTV_SRTTDFLT * tcp_backoff[(sc)->sc_rxtshift], TCPTV_MIN, \
+ TCPTV_REXMTMAX); \
+ PRT_SLOW_ARM((sc)->sc_rexmt, (sc)->sc_rxtcur); \
+} while (0)
+
+TAILQ_HEAD(, syn_cache) tcp_syn_cache_timeq[TCP_MAXRXTSHIFT + 1];
+
void
syn_cache_init()
{
int i;
- /* Initialize the hash bucket queues. */
+ /* Initialize the hash buckets. */
for (i = 0; i < tcp_syn_cache_size; i++)
- TAILQ_INIT(&tcp_syn_cache[i].sch_queue);
+ LIST_INIT(&tcp_syn_cache[i].sch_bucket);
- /* Initialize the active hash bucket cache. */
- LIST_INIT(&tcp_syn_cache_queue);
+ /* Initialize the timer queues. */
+ for (i = 0; i <= TCP_MAXRXTSHIFT; i++)
+ TAILQ_INIT(&tcp_syn_cache_timeq[i]);
/* Initialize the syn cache pool. */
pool_init(&syn_cache_pool, sizeof(struct syn_cache), 0, 0, 0,
@@ -1888,9 +1902,9 @@ void
syn_cache_insert(sc)
struct syn_cache *sc;
{
- struct syn_cache_head *scp, *scp2, *sce;
+ struct syn_cache_head *scp;
struct syn_cache *sc2;
- int s;
+ int s, i;
/*
* If there are no entries in the hash table, reinitialize
@@ -1904,7 +1918,8 @@ syn_cache_insert(sc)
}
sc->sc_hash = SYN_HASH(&sc->sc_src, sc->sc_sport, sc->sc_dport);
- scp = &tcp_syn_cache[sc->sc_hash % tcp_syn_cache_size];
+ sc->sc_bucketidx = sc->sc_hash % tcp_syn_cache_size;
+ scp = &tcp_syn_cache[sc->sc_bucketidx];
/*
* Make sure that we don't overflow the per-bucket
@@ -1914,44 +1929,71 @@ syn_cache_insert(sc)
if (scp->sch_length >= tcp_syn_bucket_limit) {
tcpstat.tcps_sc_bucketoverflow++;
/*
- * The bucket is full. Toss the first (i.e. oldest)
- * element in this bucket.
+ * The bucket is full. Toss the oldest element in the
+ * bucket. This will be the entry with our bucket
+ * index closest to the front of the timer queue with
+ * the largest timeout value.
+ *
+ * Note: This timer queue traversal may be expensive, so
+ * we hope that this doesn't happen very often. It is
+ * much more likely that we'll overflow the entire
+ * cache, which is much easier to handle; see below.
+ */
+ for (i = TCP_MAXRXTSHIFT; i >= 0; i--) {
+ for (sc2 = TAILQ_FIRST(&tcp_syn_cache_timeq[i]);
+ sc2 != NULL;
+ sc2 = TAILQ_NEXT(sc2, sc_timeq)) {
+ if (sc2->sc_bucketidx == sc->sc_bucketidx) {
+ SYN_CACHE_RM(sc2);
+ SYN_CACHE_PUT(sc2);
+ goto insert; /* 2 level break */
+ }
+ }
+ }
+#ifdef DIAGNOSTIC
+ /*
+ * This should never happen; we should always find an
+ * entry in our bucket.
*/
- sc2 = TAILQ_FIRST(&scp->sch_queue);
- SYN_CACHE_RM(sc2, scp);
- SYN_CACHE_PUT(sc2);
+ panic("syn_cache_insert: bucketoverflow: impossible");
+#endif
} else if (syn_cache_count >= tcp_syn_cache_limit) {
tcpstat.tcps_sc_overflowed++;
/*
- * The cache is full. Toss the first (i.e. oldest)
- * element in the first non-empty bucket we can find.
+ * The cache is full. Toss the oldest entry in the
+ * entire cache. This is the front entry in the
+ * first non-empty timer queue with the largest
+ * timeout value.
*/
- scp2 = scp;
- if (TAILQ_FIRST(&scp2->sch_queue) == NULL) {
- sce = &tcp_syn_cache[tcp_syn_cache_size];
- for (++scp2; scp2 != scp; scp2++) {
- if (scp2 >= sce)
- scp2 = &tcp_syn_cache[0];
- if (TAILQ_FIRST(&scp2->sch_queue) != NULL)
- break;
- }
- }
- sc2 = TAILQ_FIRST(&scp2->sch_queue);
- if (sc2 == NULL) {
- SYN_CACHE_PUT(sc);
- return;
+ for (i = TCP_MAXRXTSHIFT; i >= 0; i--) {
+ sc2 = TAILQ_FIRST(&tcp_syn_cache_timeq[i]);
+ if (sc2 == NULL)
+ continue;
+ SYN_CACHE_RM(sc2);
+ SYN_CACHE_PUT(sc2);
+ goto insert; /* symmetry with above */
}
- SYN_CACHE_RM(sc2, scp2);
- SYN_CACHE_PUT(sc2);
+#ifdef DIAGNOSTIC
+ /*
+ * This should never happen; we should always find an
+ * entry in the cache.
+ */
+ panic("syn_cache_insert: cache overflow: impossible");
+#endif
}
- /* Set entry's timer. */
- PRT_SLOW_ARM(sc->sc_timer, tcp_syn_cache_timeo);
+ insert:
+ /*
+ * Initialize the entry's timer.
+ */
+ sc->sc_rxttot = 0;
+ sc->sc_rxtshift = 0;
+ SYN_CACHE_TIMER_ARM(sc);
+ TAILQ_INSERT_TAIL(&tcp_syn_cache_timeq[sc->sc_rxtshift], sc, sc_timeq);
/* Put it into the bucket. */
- TAILQ_INSERT_TAIL(&scp->sch_queue, sc, sc_queue);
- if (++scp->sch_length == 1)
- LIST_INSERT_HEAD(&tcp_syn_cache_queue, scp, sch_headq);
+ LIST_INSERT_HEAD(&scp->sch_bucket, sc, sc_bucketq);
+ scp->sch_length++;
syn_cache_count++;
tcpstat.tcps_sc_added++;
@@ -1959,31 +2001,64 @@ syn_cache_insert(sc)
}
/*
- * Walk down the cache list, looking for expired entries in each bucket.
+ * Walk the timer queues, looking for SYN,ACKs that need to be retransmitted.
+ * If we have retransmitted an entry the maximum number of times, expire
+ * that entry.
*/
void
syn_cache_timer()
{
- struct syn_cache_head *scp, *nscp;
struct syn_cache *sc, *nsc;
- int s;
+ int i, s;
s = splsoftnet();
- for (scp = LIST_FIRST(&tcp_syn_cache_queue); scp != NULL; scp = nscp) {
-#ifdef DIAGNOSTIC
- if (TAILQ_FIRST(&scp->sch_queue) == NULL)
- panic("syn_cache_timer: queue inconsistency");
-#endif
- nscp = LIST_NEXT(scp, sch_headq);
- for (sc = TAILQ_FIRST(&scp->sch_queue);
- sc != NULL && PRT_SLOW_ISEXPIRED(sc->sc_timer);
+
+ /*
+ * First, get all the entries that need to be retransmitted, or
+ * must be expired due to exceeding the initial keepalive time.
+ */
+ for (i = 0; i < TCP_MAXRXTSHIFT; i++) {
+ for (sc = TAILQ_FIRST(&tcp_syn_cache_timeq[i]);
+ sc != NULL && PRT_SLOW_ISEXPIRED(sc->sc_rexmt);
sc = nsc) {
- nsc = TAILQ_NEXT(sc, sc_queue);
- tcpstat.tcps_sc_timed_out++;
- SYN_CACHE_RM(sc, scp);
- SYN_CACHE_PUT(sc);
+ nsc = TAILQ_NEXT(sc, sc_timeq);
+
+ /*
+ * Compute the total amount of time this entry has
+ * been on a queue. If this entry has been on longer
+ * than the keep alive timer would allow, expire it.
+ */
+ sc->sc_rxttot += sc->sc_rxtcur;
+ if (sc->sc_rxttot >= TCPTV_KEEP_INIT) {
+ tcpstat.tcps_sc_timed_out++;
+ SYN_CACHE_RM(sc);
+ SYN_CACHE_PUT(sc);
+ continue;
+ }
+
+ tcpstat.tcps_sc_retransmitted++;
+ (void) syn_cache_respond(sc, NULL);
+
+ /* Advance this entry onto the next timer queue. */
+ TAILQ_REMOVE(&tcp_syn_cache_timeq[i], sc, sc_timeq);
+ sc->sc_rxtshift = i + 1;
+ SYN_CACHE_TIMER_ARM(sc);
+ TAILQ_INSERT_TAIL(&tcp_syn_cache_timeq[sc->sc_rxtshift],
+ sc, sc_timeq);
}
}
+
+ /*
+ * Now get all the entries that are expired due to too many
+ * retransmissions.
+ */
+ for (sc = TAILQ_FIRST(&tcp_syn_cache_timeq[TCP_MAXRXTSHIFT]);
+ sc != NULL && PRT_SLOW_ISEXPIRED(sc->sc_rexmt);
+ sc = nsc) {
+ tcpstat.tcps_sc_timed_out++;
+ SYN_CACHE_RM(sc);
+ SYN_CACHE_PUT(sc);
+ }
splx(s);
}
@@ -2005,8 +2080,8 @@ syn_cache_lookup(ti, headp)
scp = &tcp_syn_cache[hash % tcp_syn_cache_size];
*headp = scp;
s = splsoftnet();
- for (sc = TAILQ_FIRST(&scp->sch_queue); sc != NULL;
- sc = TAILQ_NEXT(sc, sc_queue)) {
+ for (sc = LIST_FIRST(&scp->sch_bucket); sc != NULL;
+ sc = LIST_NEXT(sc, sc_bucketq)) {
if (sc->sc_hash != hash)
continue;
if (sc->sc_src.s_addr == ti->ti_src.s_addr &&
@@ -2056,7 +2131,6 @@ syn_cache_get(so, m)
register struct tcpiphdr *ti;
struct sockaddr_in *sin;
struct mbuf *am;
- long win;
int s;
ti = mtod(m, struct tcpiphdr *);
@@ -2066,24 +2140,20 @@ syn_cache_get(so, m)
return (NULL);
}
- win = sbspace(&so->so_rcv);
- if (win > TCP_MAXWIN)
- win = TCP_MAXWIN;
-
/*
* Verify the sequence and ack numbers. Try getting the correct
* response again.
*/
if ((ti->ti_ack != sc->sc_iss + 1) ||
SEQ_LEQ(ti->ti_seq, sc->sc_irs) ||
- SEQ_GT(ti->ti_seq, sc->sc_irs + 1 + win)) {
- (void) syn_cache_respond(sc, m, win, 0);
+ SEQ_GT(ti->ti_seq, sc->sc_irs + 1 + sc->sc_win)) {
+ (void) syn_cache_respond(sc, m);
splx(s);
return ((struct socket *)(-1));
}
/* Remove this cache entry */
- SYN_CACHE_RM(sc, scp);
+ SYN_CACHE_RM(sc);
splx(s);
/*
@@ -2164,7 +2234,7 @@ syn_cache_get(so, m)
* had to retransmit the SYN,ACK, we must initialize cwnd
* to 1 segment (i.e. the Loss Window).
*/
- if (sc->sc_rexmt_count)
+ if (sc->sc_rxtshift)
tp->snd_cwnd = tp->t_peermss;
else
tp->snd_cwnd = TCP_INITIAL_WINDOW(tcp_init_win, tp->t_peermss);
@@ -2180,8 +2250,8 @@ syn_cache_get(so, m)
tp->snd_up = tp->snd_una;
tp->snd_max = tp->snd_nxt = tp->iss+1;
TCP_TIMER_ARM(tp, TCPT_REXMT, tp->t_rxtcur);
- if (win > 0 && SEQ_GT(tp->rcv_nxt+win, tp->rcv_adv))
- tp->rcv_adv = tp->rcv_nxt + win;
+ if (sc->sc_win > 0 && SEQ_GT(tp->rcv_nxt + sc->sc_win, tp->rcv_adv))
+ tp->rcv_adv = tp->rcv_nxt + sc->sc_win;
tp->last_ack_sent = tp->rcv_nxt;
tcpstat.tcps_sc_completed++;
@@ -2222,7 +2292,7 @@ syn_cache_reset(ti)
splx(s);
return;
}
- SYN_CACHE_RM(sc, scp);
+ SYN_CACHE_RM(sc);
splx(s);
tcpstat.tcps_sc_reset++;
SYN_CACHE_PUT(sc);
@@ -2262,13 +2332,13 @@ syn_cache_unreach(ip, th)
*
* See tcp_notify().
*/
- if ((sc->sc_flags & SCF_UNREACH) == 0 || sc->sc_rexmt_count < 3) {
+ if ((sc->sc_flags & SCF_UNREACH) == 0 || sc->sc_rxtshift < 3) {
sc->sc_flags |= SCF_UNREACH;
splx(s);
return;
}
- SYN_CACHE_RM(sc, scp);
+ SYN_CACHE_RM(sc);
splx(s);
tcpstat.tcps_sc_unreach++;
SYN_CACHE_PUT(sc);
@@ -2336,23 +2406,11 @@ syn_cache_add(so, m, optp, optlen, oi)
/*
* See if we already have an entry for this connection.
- * If we do, resend the SYN,ACK, and remember since the
- * initial congestion window must be initialized to 1
- * segment when the connection completes.
+ * If we do, resend the SYN,ACK. We do not count this
+ * as a retransmission (XXX though maybe we should).
*/
if ((sc = syn_cache_lookup(ti, &scp)) != NULL) {
tcpstat.tcps_sc_dupesyn++;
- sc->sc_rexmt_count++;
- if (sc->sc_rexmt_count == 0) {
- /*
- * Eeek! We rolled the counter. Just set it
- * to the max value. This shouldn't ever happen,
- * but there's no real reason to panic here, since
- * the count doesn't have to be very precise.
- */
- sc->sc_rexmt_count = USHRT_MAX;
- }
-
if (ipopts) {
/*
* If we were remembering a previous source route,
@@ -2362,8 +2420,8 @@ syn_cache_add(so, m, optp, optlen, oi)
(void) m_free(sc->sc_ipopts);
sc->sc_ipopts = ipopts;
}
-
- if (syn_cache_respond(sc, m, win, tb.ts_recent) == 0) {
+ sc->sc_timestamp = tb.ts_recent;
+ if (syn_cache_respond(sc, m) == 0) {
tcpstat.tcps_sndacks++;
tcpstat.tcps_sndtotal++;
}
@@ -2393,6 +2451,8 @@ syn_cache_add(so, m, optp, optlen, oi)
sc->sc_peermaxseg = oi->maxseg;
sc->sc_ourmaxseg = tcp_mss_to_advertise(m->m_flags & M_PKTHDR ?
m->m_pkthdr.rcvif : NULL);
+ sc->sc_win = win;
+ sc->sc_timestamp = tb.ts_recent;
if (tcp_do_rfc1323 && (tb.t_flags & TF_RCVD_TSTMP))
sc->sc_flags |= SCF_TIMESTAMP;
if ((tb.t_flags & (TF_RCVD_SCALE|TF_REQ_SCALE)) ==
@@ -2407,7 +2467,7 @@ syn_cache_add(so, m, optp, optlen, oi)
sc->sc_requested_s_scale = 15;
sc->sc_request_r_scale = 15;
}
- if (syn_cache_respond(sc, m, win, tb.ts_recent) == 0) {
+ if (syn_cache_respond(sc, m) == 0) {
syn_cache_insert(sc);
tcpstat.tcps_sndacks++;
tcpstat.tcps_sndtotal++;
@@ -2419,11 +2479,9 @@ syn_cache_add(so, m, optp, optlen, oi)
}
int
-syn_cache_respond(sc, m, win, ts)
+syn_cache_respond(sc, m)
struct syn_cache *sc;
struct mbuf *m;
- long win;
- u_long ts;
{
struct route *ro = &sc->sc_route;
struct rtentry *rt;
@@ -2473,7 +2531,7 @@ syn_cache_respond(sc, m, win, ts)
/* ti_x2 already 0 */
ti->ti_off = (sizeof(struct tcphdr) + optlen) >> 2;
ti->ti_flags = TH_SYN|TH_ACK;
- ti->ti_win = htons(win);
+ ti->ti_win = htons(sc->sc_win);
/* ti_sum already 0 */
/* ti_urp already 0 */
@@ -2496,7 +2554,7 @@ syn_cache_respond(sc, m, win, ts)
/* Form timestamp option as shown in appendix A of RFC 1323. */
*lp++ = htonl(TCPOPT_TSTAMP_HDR);
*lp++ = htonl(tcp_now);
- *lp = htonl(ts);
+ *lp = htonl(sc->sc_timestamp);
optp += TCPOLEN_TSTAMP_APPA;
}
diff --git a/sys/netinet/tcp_var.h b/sys/netinet/tcp_var.h
index 7f9c5ac5bf4..5e8c125c93a 100644
--- a/sys/netinet/tcp_var.h
+++ b/sys/netinet/tcp_var.h
@@ -1,4 +1,4 @@
-/* $NetBSD: tcp_var.h,v 1.58 1999/01/24 01:21:18 thorpej Exp $ */
+/* $NetBSD: tcp_var.h,v 1.59 1999/04/29 03:54:23 thorpej Exp $ */
/*-
* Copyright (c) 1997, 1998, 1999 The NetBSD Foundation, Inc.
@@ -277,16 +277,21 @@ struct tcp_opt_info {
* Data for the TCP compressed state engine.
*/
struct syn_cache {
- TAILQ_ENTRY(syn_cache) sc_queue;
+ LIST_ENTRY(syn_cache) sc_bucketq; /* link on bucket list */
+ TAILQ_ENTRY(syn_cache) sc_timeq; /* link on timer queue */
struct route sc_route; /* cached route */
- u_int sc_timer;
+ long sc_win; /* advertised window */
+ int sc_bucketidx; /* our bucket index */
u_int32_t sc_hash;
+ u_int32_t sc_timestamp; /* timestamp from SYN */
struct in_addr sc_src;
struct in_addr sc_dst;
tcp_seq sc_irs;
tcp_seq sc_iss;
- u_short sc_rexmt_count; /* number of times SYN,ACK
- was retransmitted */
+ u_int sc_rexmt; /* retransmit timer */
+ u_int sc_rxtcur; /* current rxt timeout */
+ u_int sc_rxttot; /* total time spend on queues */
+ u_short sc_rxtshift; /* for computing backoff */
u_short sc_flags;
#define SCF_UNREACH 0x0001 /* we've had an unreach error */
@@ -302,8 +307,7 @@ struct syn_cache {
};
struct syn_cache_head {
- TAILQ_HEAD(, syn_cache) sch_queue; /* time-sorted entries */
- LIST_ENTRY(syn_cache_head) sch_headq; /* non-empty buckets */
+ LIST_HEAD(, syn_cache) sch_bucket; /* bucket entries */
u_short sch_length; /* # entries in bucket */
};
@@ -424,6 +428,7 @@ struct tcpstat {
u_long tcps_sc_dupesyn; /* # of duplicate SYNs received */
u_long tcps_sc_dropped; /* # of SYNs dropped (no route/mem) */
u_long tcps_sc_collisions; /* # of hash collisions */
+ u_long tcps_sc_retransmitted; /* # of retransmissions */
};
/*
@@ -498,7 +503,6 @@ extern int tcp_syn_bucket_limit;/* max entries per hash bucket */
extern int tcp_syn_cache_interval; /* compressed state timer */
extern int tcp_syn_cache_size;
-extern int tcp_syn_cache_timeo;
extern struct syn_cache_head tcp_syn_cache[];
extern u_long syn_cache_count;
@@ -584,8 +588,7 @@ void syn_cache_insert __P((struct syn_cache *));
struct syn_cache *
syn_cache_lookup __P((struct tcpiphdr *, struct syn_cache_head **));
void syn_cache_reset __P((struct tcpiphdr *));
-int syn_cache_respond __P((struct syn_cache *, struct mbuf *,
- long, u_long));
+int syn_cache_respond __P((struct syn_cache *, struct mbuf *));
void syn_cache_timer __P((void));
int tcp_newreno __P((struct tcpcb *, struct tcpiphdr *));