From a06d57a3ff9f3fec7a315a8a931acacf67bec7a4 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Wed, 1 Feb 2012 21:13:01 +0000 Subject: [PATCH 1/1] server/keyexch.c: Randomized exponential retransmit backoff. Organization: Straylight/Edgeware From: Mark Wooding Rather than retrying after a constant delay, increase the delay by a constant factor. We now start with a smaller retransmit interval, and cap at a fairly long wait. Also introduce a random `wobble' proportional to the delay in order to prevent a server being hammered by a swarm of clients acting in unison if it comes back after an outage. --- server/keyexch.c | 99 ++++++++++++++++++++++++++++++++++++++++++++---- server/tripe.h | 13 ++++++- 2 files changed, 104 insertions(+), 8 deletions(-) diff --git a/server/keyexch.c b/server/keyexch.c index c27d69fd..b1f23d73 100644 --- a/server/keyexch.c +++ b/server/keyexch.c @@ -279,6 +279,88 @@ static void settimer(keyexch *kx, struct timeval *tv) kx->f |= KXF_TIMER; } +/* --- @f2tv@ --- * + * + * Arguments: @struct timeval *tv@ = where to write the timeval + * @double t@ = a time as a floating point number + * + * Returns: --- + * + * Use: Converts a floating-point time into a timeval. + */ + +static void f2tv(struct timeval *tv, double t) +{ + tv->tv_sec = t; + tv->tv_usec = (t - tv->tv_sec)*MILLION; +} + +/* --- @wobble@ --- * + * + * Arguments: @double t@ = a time interval + * + * Returns: The same time interval, with a random error applied. + */ + +static double wobble(double t) +{ + uint32 r = rand_global.ops->word(&rand_global); + double w = (r/F_2P32) - 0.5; + return (t + t*w*T_WOBBLE); +} + +/* --- @rs_time@ --- * + * + * Arguments: @retry *rs@ = current retry state + * @struct timeval *tv@ = where to write the result + * @const struct timeval *now@ = current time, or null + * + * Returns: --- + * + * Use: Computes a time at which to retry sending a key-exchange + * packet. This algorithm is subject to change, but it's + * currently a capped exponential backoff, slightly randomized + * to try to keep clients from hammering a server that's only + * just woken up. + * + * If @now@ is null then the function works out the time for + * itself. + */ + +static void rs_time(retry *rs, struct timeval *tv, const struct timeval *now) +{ + double t; + struct timeval rtv; + + if (!rs->t) + t = SEC(2); + else { + t = (rs->t * 5)/4; + if (t > MIN(5)) t = MIN(5); + } + rs->t = t; + + if (!now) { + now = tv; + gettimeofday(tv, 0); + } + f2tv(&rtv, wobble(t)); + TV_ADD(tv, now, &rtv); +} + +/* --- @retry_reset@ --- * + * + * Arguments: @retry *rs@ = retry state + * + * Returns: -- + * + * Use: Resets a retry state to indicate that progress has been + * made. Also useful for initializing the state in the first + * place. + */ + +static void rs_reset(retry *rs) { rs->t = 0; } + /*----- Challenge management ----------------------------------------------*/ /* --- Notes on challenge management --- * @@ -363,6 +445,7 @@ static kxchal *kxc_new(keyexch *kx) kxc->kx = kx; kxc->f = 0; kx->r[i] = kxc; + rs_reset(&kxc->rs); return (kxc); } @@ -457,7 +540,7 @@ static void kxc_answer(keyexch *kx, kxchal *kxc) if (kxc->f & KXF_TIMER) sel_rmtimer(&kxc->t); gettimeofday(&tv, 0); - tv.tv_sec += T_RETRY; + rs_time(&kxc->rs, &tv, &tv); sel_addtimer(&sel, &kxc->t, &tv, kxc_timer, kxc); kxc->f |= KXF_TIMER; } @@ -768,8 +851,7 @@ static void resend(keyexch *kx) } if (kx->s < KXS_SWITCH) { - gettimeofday(&tv, 0); - tv.tv_sec += T_RETRY; + rs_time(&kx->rs, &tv, 0); settimer(kx, &tv); } } @@ -912,11 +994,12 @@ bad: static void kxfinish(keyexch *kx) { kxchal *kxc = kx->r[0]; - struct timeval tv; + struct timeval now, tv; ks_activate(kxc->ks); - gettimeofday(&tv, 0); - tv.tv_sec += T_REGEN; + gettimeofday(&now, 0); + f2tv(&tv, wobble(T_REGEN)); + TV_ADD(&tv, &now, &tv); settimer(kx, &tv); kx->s = KXS_SWITCH; a_notify("KXDONE", "?PEER", kx->p, A_END); @@ -1170,9 +1253,10 @@ void kx_message(keyexch *kx, unsigned msg, buf *b) int rc; gettimeofday(&now, 0); + rs_reset(&kx->rs); if (kx->f & KXF_CORK) { start(kx, now.tv_sec); - TV_ADDL(&tv, &now, T_RETRY, 0); + rs_time(&kx->rs, &tv, &now); settimer(kx, &tv); a_notify("KXSTART", A_END); } @@ -1282,6 +1366,7 @@ int kx_init(keyexch *kx, peer *p, keyset **ks, unsigned f) return (-1); } kx->f = KXF_DEAD | KXF_PUBKEY | f; + rs_reset(&kx->rs); if (!(kx->f & KXF_CORK)) { start(kx, time(0)); resend(kx); diff --git a/server/tripe.h b/server/tripe.h index d447326e..ad20daa7 100644 --- a/server/tripe.h +++ b/server/tripe.h @@ -134,6 +134,7 @@ #define SEC(n) (n##u) #define MIN(n) (n##u * 60u) +#define F_2P32 (65536.0*65536.0) #define MEG(n) (n##ul * 1024ul * 1024ul) /* --- Timing parameters --- */ @@ -142,7 +143,11 @@ #define T_REGEN MIN(40) /* Regeneration time for a key */ #define T_VALID SEC(20) /* Challenge validity period */ -#define T_RETRY SEC(10) /* Challenge retransmit interval */ +#define T_RETRYMIN SEC(2) /* Minimum retry interval */ +#define T_RETRYMAX MIN(5) /* Maximum retry interval */ +#define T_RETRYGROW (5.0/4.0) /* Retry interval growth factor */ + +#define T_WOBBLE (1.0/3.0) /* Relative timer randomness */ /* --- Other things --- */ @@ -246,6 +251,10 @@ typedef struct keyset { * Clive Jones. */ +typedef struct retry { + double t; /* Current retry time */ +} retry; + #define KX_NCHAL 16u typedef struct kxchal { @@ -255,6 +264,7 @@ typedef struct kxchal { keyset *ks; /* Pointer to temporary keyset */ unsigned f; /* Various useful flags */ sel_timer t; /* Response timer for challenge */ + retry rs; /* Retry state */ octet hc[MAXHASHSZ]; /* Hash of his challenge */ octet ck[MAXHASHSZ]; /* His magical check value */ octet hswrq_in[MAXHASHSZ]; /* Inbound switch request message */ @@ -269,6 +279,7 @@ typedef struct keyexch { unsigned f; /* Various useful flags */ unsigned s; /* Current state in exchange */ sel_timer t; /* Timer for next exchange */ + retry rs; /* Retry state */ ge *kpub; /* Peer's public key */ time_t texp_kpub; /* Expiry time for public key */ mp *alpha; /* My temporary secret */ -- [mdw]