From 25959e04c350c2b82d545ea38b18ff714acf61ba Mon Sep 17 00:00:00 2001 From: Todd Short Date: Fri, 5 Apr 2019 14:17:22 -0400 Subject: [PATCH] Optimize session cache flushing Sort SSL_SESSION structures by timeout in the linked list. Iterate over the linked list for timeout, stopping when no more session can be flushed. Do SSL_SESSION_free() outside of SSL_CTX lock Update timeout upon use Reviewed-by: Matt Caswell Reviewed-by: Paul Dale (Merged from https://github.com/openssl/openssl/pull/8687) --- doc/man3/SSL_CTX_set_session_cache_mode.pod | 5 + include/openssl/ssl.h.in | 1 + ssl/ssl_asn1.c | 11 +- ssl/ssl_local.h | 9 +- ssl/ssl_sess.c | 207 +++++++++++++++----- ssl/statem/statem_clnt.c | 7 +- ssl/statem/statem_srvr.c | 5 +- test/sslapitest.c | 124 ++++++++++++ 8 files changed, 310 insertions(+), 59 deletions(-) diff --git a/doc/man3/SSL_CTX_set_session_cache_mode.pod b/doc/man3/SSL_CTX_set_session_cache_mode.pod index 26febc6986..a698ffde5d 100644 --- a/doc/man3/SSL_CTX_set_session_cache_mode.pod +++ b/doc/man3/SSL_CTX_set_session_cache_mode.pod @@ -105,6 +105,11 @@ prevents these additions to the internal cache as well. Enable both SSL_SESS_CACHE_NO_INTERNAL_LOOKUP and SSL_SESS_CACHE_NO_INTERNAL_STORE at the same time. +=item SSL_SESS_CACHE_UPDATE_TIME + +Updates the timestamp of the session when it is used, increasing the lifespan +of the session. The session timeout applies to last use, rather then creation +time. =back diff --git a/include/openssl/ssl.h.in b/include/openssl/ssl.h.in index 2c34fd2a9a..9c00eb3d13 100644 --- a/include/openssl/ssl.h.in +++ b/include/openssl/ssl.h.in @@ -670,6 +670,7 @@ typedef int (*GEN_SESSION_CB) (SSL *ssl, unsigned char *id, # define SSL_SESS_CACHE_NO_INTERNAL_STORE 0x0200 # define SSL_SESS_CACHE_NO_INTERNAL \ (SSL_SESS_CACHE_NO_INTERNAL_LOOKUP|SSL_SESS_CACHE_NO_INTERNAL_STORE) +# define SSL_SESS_CACHE_UPDATE_TIME 0x0400 LHASH_OF(SSL_SESSION) *SSL_CTX_sessions(SSL_CTX *ctx); # define SSL_CTX_sess_number(ctx) \ diff --git a/ssl/ssl_asn1.c b/ssl/ssl_asn1.c index c4479c2dd6..2cbd95fa1b 100644 --- a/ssl/ssl_asn1.c +++ b/ssl/ssl_asn1.c @@ -163,8 +163,8 @@ int i2d_SSL_SESSION(const SSL_SESSION *in, unsigned char **pp) ssl_session_oinit(&as.session_id_context, &sid_ctx, in->sid_ctx, in->sid_ctx_length); - as.time = in->time; - as.timeout = in->timeout; + as.time = (int64_t)in->time; + as.timeout = (int64_t)in->timeout; as.verify_result = in->verify_result; as.peer = in->peer; @@ -302,14 +302,15 @@ SSL_SESSION *d2i_SSL_SESSION(SSL_SESSION **a, const unsigned char **pp, ret->master_key_length = tmpl; if (as->time != 0) - ret->time = (long)as->time; + ret->time = (time_t)as->time; else - ret->time = (long)time(NULL); + ret->time = time(NULL); if (as->timeout != 0) - ret->timeout = (long)as->timeout; + ret->timeout = (time_t)as->timeout; else ret->timeout = 3; + ssl_session_calculate_timeout(ret); X509_free(ret->peer); ret->peer = as->peer; diff --git a/ssl/ssl_local.h b/ssl/ssl_local.h index 09413a44fa..def53739a1 100644 --- a/ssl/ssl_local.h +++ b/ssl/ssl_local.h @@ -593,8 +593,10 @@ struct ssl_session_st { */ long verify_result; /* only for servers */ CRYPTO_REF_COUNT references; - long timeout; - long time; + time_t timeout; + time_t time; + time_t calc_timeout; + int timeout_ovf; unsigned int compress_meth; /* Need to lookup the method */ const SSL_CIPHER *cipher; unsigned long cipher_id; /* when ASN.1 loaded, this needs to be used to @@ -634,6 +636,7 @@ struct ssl_session_st { unsigned char *ticket_appdata; size_t ticket_appdata_len; uint32_t flags; + SSL_CTX *owner; CRYPTO_RWLOCK *lock; }; @@ -2843,6 +2846,8 @@ int ssl_srp_ctx_init_intern(SSL *s); int ssl_srp_calc_a_param_intern(SSL *s); int ssl_srp_server_param_with_username_intern(SSL *s, int *ad); +void ssl_session_calculate_timeout(SSL_SESSION* ss); + # else /* OPENSSL_UNIT_TEST */ # define ssl_init_wbio_buffer SSL_test_functions()->p_ssl_init_wbio_buffer diff --git a/ssl/ssl_sess.c b/ssl/ssl_sess.c index 3409795628..b526984289 100644 --- a/ssl/ssl_sess.c +++ b/ssl/ssl_sess.c @@ -24,6 +24,58 @@ static void SSL_SESSION_list_remove(SSL_CTX *ctx, SSL_SESSION *s); static void SSL_SESSION_list_add(SSL_CTX *ctx, SSL_SESSION *s); static int remove_session_lock(SSL_CTX *ctx, SSL_SESSION *c, int lck); +DEFINE_STACK_OF(SSL_SESSION) + +__owur static int sess_timedout(time_t t, SSL_SESSION *ss) +{ + /* if timeout overflowed, it can never timeout! */ + if (ss->timeout_ovf) + return 0; + return t > ss->calc_timeout; +} + +/* + * Returns -1/0/+1 as other XXXcmp-type functions + * Takes overflow of calculated timeout into consideration + */ +__owur static int timeoutcmp(SSL_SESSION *a, SSL_SESSION *b) +{ + /* if only one overflowed, then it is greater */ + if (a->timeout_ovf && !b->timeout_ovf) + return 1; + if (!a->timeout_ovf && b->timeout_ovf) + return -1; + /* No overflow, or both overflowed, so straight compare is safe */ + if (a->calc_timeout < b->calc_timeout) + return -1; + if (a->calc_timeout > b->calc_timeout) + return 1; + return 0; +} + +/* + * Calculates effective timeout, saving overflow state + * Locking must be done by the caller of this function + */ +void ssl_session_calculate_timeout(SSL_SESSION *ss) +{ + /* Force positive timeout */ + if (ss->timeout < 0) + ss->timeout = 0; + ss->calc_timeout = ss->time + ss->timeout; + /* + * |timeout| is always zero or positive, so the check for + * overflow only needs to consider if |time| is positive + */ + ss->timeout_ovf = ss->time > 0 && ss->calc_timeout < ss->time; + /* + * N.B. Realistic overflow can only occur in our lifetimes on a + * 32-bit machine in January 2038. + * However, There are no controls to limit the |timeout| + * value, except to keep it positive. + */ +} + /* * SSL_get_session() and SSL_get1_session() are problematic in TLS1.3 because, * unlike in earlier protocol versions, the session ticket may not have been @@ -83,7 +135,8 @@ SSL_SESSION *SSL_SESSION_new(void) ss->verify_result = 1; /* avoid 0 (= X509_V_OK) just in case */ ss->references = 1; ss->timeout = 60 * 5 + 4; /* 5 minute timeout by default */ - ss->time = (unsigned long)time(NULL); + ss->time = time(NULL); + ssl_session_calculate_timeout(ss); ss->lock = CRYPTO_THREAD_lock_new(); if (ss->lock == NULL) { ERR_raise(ERR_LIB_SSL, ERR_R_MALLOC_FAILURE); @@ -587,7 +640,7 @@ int ssl_get_prev_session(SSL *s, CLIENTHELLO_MSG *hello) goto err; } - if (ret->timeout < (long)(time(NULL) - ret->time)) { /* timeout */ + if (sess_timedout(time(NULL), ret)) { tsan_counter(&s->session_ctx->stats.sess_timeout); if (try_session_cache) { /* session was from the cache, so remove it */ @@ -688,9 +741,12 @@ int SSL_CTX_add_session(SSL_CTX *ctx, SSL_SESSION *c) s = c; } - /* Put at the head of the queue unless it is already in the cache */ - if (s == NULL) - SSL_SESSION_list_add(ctx, c); + /* Adjust last used time, and add back into the cache at the appropriate spot */ + if (ctx->session_cache_mode & SSL_SESS_CACHE_UPDATE_TIME) { + c->time = time(NULL); + ssl_session_calculate_timeout(c); + } + SSL_SESSION_list_add(ctx, c); if (s != NULL) { /* @@ -832,9 +888,21 @@ int SSL_SESSION_set1_id(SSL_SESSION *s, const unsigned char *sid, long SSL_SESSION_set_timeout(SSL_SESSION *s, long t) { - if (s == NULL) + time_t new_timeout = (time_t)t; + + if (s == NULL || t < 0) return 0; - s->timeout = t; + if (s->owner != NULL) { + if (!CRYPTO_THREAD_write_lock(s->owner->lock)) + return 0; + s->timeout = new_timeout; + ssl_session_calculate_timeout(s); + SSL_SESSION_list_add(s->owner, s); + CRYPTO_THREAD_unlock(s->owner->lock); + } else { + s->timeout = new_timeout; + ssl_session_calculate_timeout(s); + } return 1; } @@ -842,21 +910,33 @@ long SSL_SESSION_get_timeout(const SSL_SESSION *s) { if (s == NULL) return 0; - return s->timeout; + return (long)s->timeout; } long SSL_SESSION_get_time(const SSL_SESSION *s) { if (s == NULL) return 0; - return s->time; + return (long)s->time; } long SSL_SESSION_set_time(SSL_SESSION *s, long t) { + time_t new_time = (time_t)t; + if (s == NULL) return 0; - s->time = t; + if (s->owner != NULL) { + if (!CRYPTO_THREAD_write_lock(s->owner->lock)) + return 0; + s->time = new_time; + ssl_session_calculate_timeout(s); + SSL_SESSION_list_add(s->owner, s); + CRYPTO_THREAD_unlock(s->owner->lock); + } else { + s->time = new_time; + ssl_session_calculate_timeout(s); + } return t; } @@ -1050,47 +1130,52 @@ int SSL_set_session_ticket_ext(SSL *s, void *ext_data, int ext_len) return 0; } -typedef struct timeout_param_st { - SSL_CTX *ctx; - long time; - LHASH_OF(SSL_SESSION) *cache; -} TIMEOUT_PARAM; - -static void timeout_cb(SSL_SESSION *s, TIMEOUT_PARAM *p) -{ - if ((p->time == 0) || (p->time > (s->time + s->timeout))) { /* timeout */ - /* - * The reason we don't call SSL_CTX_remove_session() is to save on - * locking overhead - */ - (void)lh_SSL_SESSION_delete(p->cache, s); - SSL_SESSION_list_remove(p->ctx, s); - s->not_resumable = 1; - if (p->ctx->remove_session_cb != NULL) - p->ctx->remove_session_cb(p->ctx, s); - SSL_SESSION_free(s); - } -} - -IMPLEMENT_LHASH_DOALL_ARG(SSL_SESSION, TIMEOUT_PARAM); - void SSL_CTX_flush_sessions(SSL_CTX *s, long t) { + STACK_OF(SSL_SESSION) *sk; + SSL_SESSION *current; unsigned long i; - TIMEOUT_PARAM tp; - tp.ctx = s; - tp.cache = s->sessions; - if (tp.cache == NULL) - return; - tp.time = t; if (!CRYPTO_THREAD_write_lock(s->lock)) return; + + sk = sk_SSL_SESSION_new_null(); i = lh_SSL_SESSION_get_down_load(s->sessions); lh_SSL_SESSION_set_down_load(s->sessions, 0); - lh_SSL_SESSION_doall_TIMEOUT_PARAM(tp.cache, timeout_cb, &tp); + + /* + * Iterate over the list from the back (oldest), and stop + * when a session can no longer be removed. + * Add the session to a temporary list to be freed outside + * the SSL_CTX lock. + * But still do the remove_session_cb() within the lock. + */ + while (s->session_cache_tail != NULL) { + current = s->session_cache_tail; + if (t == 0 || sess_timedout((time_t)t, current)) { + lh_SSL_SESSION_delete(s->sessions, current); + SSL_SESSION_list_remove(s, current); + current->not_resumable = 1; + if (s->remove_session_cb != NULL) + s->remove_session_cb(s, current); + /* + * Throw the session on a stack, it's entirely plausible + * that while freeing outside the critical section, the + * session could be re-added, so avoid using the next/prev + * pointers. If the stack failed to create, or the session + * couldn't be put on the stack, just free it here + */ + if (sk == NULL || !sk_SSL_SESSION_push(sk, current)) + SSL_SESSION_free(current); + } else { + break; + } + } + lh_SSL_SESSION_set_down_load(s->sessions, i); CRYPTO_THREAD_unlock(s->lock); + + sk_SSL_SESSION_pop_free(sk, SSL_SESSION_free); } int ssl_clear_bad_session(SSL *s) @@ -1132,10 +1217,13 @@ static void SSL_SESSION_list_remove(SSL_CTX *ctx, SSL_SESSION *s) } } s->prev = s->next = NULL; + s->owner = NULL; } static void SSL_SESSION_list_add(SSL_CTX *ctx, SSL_SESSION *s) { + SSL_SESSION *next; + if ((s->next != NULL) && (s->prev != NULL)) SSL_SESSION_list_remove(ctx, s); @@ -1145,11 +1233,40 @@ static void SSL_SESSION_list_add(SSL_CTX *ctx, SSL_SESSION *s) s->prev = (SSL_SESSION *)&(ctx->session_cache_head); s->next = (SSL_SESSION *)&(ctx->session_cache_tail); } else { - s->next = ctx->session_cache_head; - s->next->prev = s; - s->prev = (SSL_SESSION *)&(ctx->session_cache_head); - ctx->session_cache_head = s; + if (timeoutcmp(s, ctx->session_cache_head) >= 0) { + /* + * if we timeout after (or the same time as) the first + * session, put us first - usual case + */ + s->next = ctx->session_cache_head; + s->next->prev = s; + s->prev = (SSL_SESSION *)&(ctx->session_cache_head); + ctx->session_cache_head = s; + } else if (timeoutcmp(s, ctx->session_cache_tail) < 0) { + /* if we timeout before the last session, put us last */ + s->prev = ctx->session_cache_tail; + s->prev->next = s; + s->next = (SSL_SESSION *)&(ctx->session_cache_tail); + ctx->session_cache_tail = s; + } else { + /* + * we timeout somewhere in-between - if there is only + * one session in the cache it will be caught above + */ + next = ctx->session_cache_head->next; + while (next != (SSL_SESSION*)&(ctx->session_cache_tail)) { + if (timeoutcmp(s, next) >= 0) { + s->next = next; + s->prev = next->prev; + next->prev->next = s; + next->prev = s; + break; + } + next = next->next; + } + } } + s->owner = ctx; } void SSL_CTX_sess_set_new_cb(SSL_CTX *ctx, diff --git a/ssl/statem/statem_clnt.c b/ssl/statem/statem_clnt.c index e8e9f94651..472a4a366b 100644 --- a/ssl/statem/statem_clnt.c +++ b/ssl/statem/statem_clnt.c @@ -2510,11 +2510,8 @@ MSG_PROCESS_RETURN tls_process_new_session_ticket(SSL *s, PACKET *pkt) s->session = new_sess; } - /* - * Technically the cast to long here is not guaranteed by the C standard - - * but we use it elsewhere, so this should be ok. - */ - s->session->time = (long)time(NULL); + s->session->time = time(NULL); + ssl_session_calculate_timeout(s->session); OPENSSL_free(s->session->ext.tick); s->session->ext.tick = NULL; diff --git a/ssl/statem/statem_srvr.c b/ssl/statem/statem_srvr.c index c1c0d455e1..35e023b781 100644 --- a/ssl/statem/statem_srvr.c +++ b/ssl/statem/statem_srvr.c @@ -3633,7 +3633,7 @@ static int create_ticket_prequel(SSL *s, WPACKET *pkt, uint32_t age_add, */ if (!WPACKET_put_bytes_u32(pkt, (s->hit && !SSL_IS_TLS13(s)) - ? 0 : s->session->timeout)) { + ? 0 : (uint32_t)s->session->timeout)) { SSLfatal(s, SSL_AD_INTERNAL_ERROR, ERR_R_INTERNAL_ERROR); return 0; } @@ -3930,7 +3930,8 @@ int tls_construct_new_session_ticket(SSL *s, WPACKET *pkt) } s->session->master_key_length = hashlen; - s->session->time = (long)time(NULL); + s->session->time = time(NULL); + ssl_session_calculate_timeout(s->session); if (s->s3.alpn_selected != NULL) { OPENSSL_free(s->session->ext.alpn_selected); s->session->ext.alpn_selected = diff --git a/test/sslapitest.c b/test/sslapitest.c index 2b73e43305..ba642e6070 100644 --- a/test/sslapitest.c +++ b/test/sslapitest.c @@ -8122,6 +8122,129 @@ end: } #endif /* OPENSSL_NO_TLS1_2 */ +static int test_session_timeout(int test) +{ + /* + * Test session ordering and timeout + * Can't explicitly test performance of the new code, + * but can test to see if the ordering of the sessions + * are correct, and they they are removed as expected + */ + SSL_SESSION *early = NULL; + SSL_SESSION *middle = NULL; + SSL_SESSION *late = NULL; + SSL_CTX *ctx; + int testresult = 0; + long now = (long)time(NULL); +#define TIMEOUT 10 + + if (!TEST_ptr(ctx = SSL_CTX_new_ex(libctx, NULL, TLS_method())) + || !TEST_ptr(early = SSL_SESSION_new()) + || !TEST_ptr(middle = SSL_SESSION_new()) + || !TEST_ptr(late = SSL_SESSION_new())) + goto end; + + /* assign unique session ids */ + early->session_id_length = SSL3_SSL_SESSION_ID_LENGTH; + memset(early->session_id, 1, SSL3_SSL_SESSION_ID_LENGTH); + middle->session_id_length = SSL3_SSL_SESSION_ID_LENGTH; + memset(middle->session_id, 2, SSL3_SSL_SESSION_ID_LENGTH); + late->session_id_length = SSL3_SSL_SESSION_ID_LENGTH; + memset(late->session_id, 3, SSL3_SSL_SESSION_ID_LENGTH); + + if (!TEST_int_eq(SSL_CTX_add_session(ctx, early), 1) + || !TEST_int_eq(SSL_CTX_add_session(ctx, middle), 1) + || !TEST_int_eq(SSL_CTX_add_session(ctx, late), 1)) + goto end; + + /* Make sure they are all added */ + if (!TEST_ptr(early->prev) + || !TEST_ptr(middle->prev) + || !TEST_ptr(late->prev)) + goto end; + + if (!TEST_int_ne(SSL_SESSION_set_time(early, now - 10), 0) + || !TEST_int_ne(SSL_SESSION_set_time(middle, now), 0) + || !TEST_int_ne(SSL_SESSION_set_time(late, now + 10), 0)) + goto end; + + if (!TEST_int_ne(SSL_SESSION_set_timeout(early, TIMEOUT), 0) + || !TEST_int_ne(SSL_SESSION_set_timeout(middle, TIMEOUT), 0) + || !TEST_int_ne(SSL_SESSION_set_timeout(late, TIMEOUT), 0)) + goto end; + + /* Make sure they are all still there */ + if (!TEST_ptr(early->prev) + || !TEST_ptr(middle->prev) + || !TEST_ptr(late->prev)) + goto end; + + /* Make sure they are in the expected order */ + if (!TEST_ptr_eq(late->next, middle) + || !TEST_ptr_eq(middle->next, early) + || !TEST_ptr_eq(early->prev, middle) + || !TEST_ptr_eq(middle->prev, late)) + goto end; + + /* This should remove "early" */ + SSL_CTX_flush_sessions(ctx, now + TIMEOUT - 1); + if (!TEST_ptr_null(early->prev) + || !TEST_ptr(middle->prev) + || !TEST_ptr(late->prev)) + goto end; + + /* This should remove "middle" */ + SSL_CTX_flush_sessions(ctx, now + TIMEOUT + 1); + if (!TEST_ptr_null(early->prev) + || !TEST_ptr_null(middle->prev) + || !TEST_ptr(late->prev)) + goto end; + + /* This should remove "late" */ + SSL_CTX_flush_sessions(ctx, now + TIMEOUT + 11); + if (!TEST_ptr_null(early->prev) + || !TEST_ptr_null(middle->prev) + || !TEST_ptr_null(late->prev)) + goto end; + + /* Add them back in again */ + if (!TEST_int_eq(SSL_CTX_add_session(ctx, early), 1) + || !TEST_int_eq(SSL_CTX_add_session(ctx, middle), 1) + || !TEST_int_eq(SSL_CTX_add_session(ctx, late), 1)) + goto end; + + /* Make sure they are all added */ + if (!TEST_ptr(early->prev) + || !TEST_ptr(middle->prev) + || !TEST_ptr(late->prev)) + goto end; + + /* This should remove all of them */ + SSL_CTX_flush_sessions(ctx, 0); + if (!TEST_ptr_null(early->prev) + || !TEST_ptr_null(middle->prev) + || !TEST_ptr_null(late->prev)) + goto end; + + (void)SSL_CTX_set_session_cache_mode(ctx, SSL_SESS_CACHE_UPDATE_TIME + | SSL_CTX_get_session_cache_mode(ctx)); + + /* make sure |now| is NOT equal to the current time */ + now -= 10; + if (!TEST_int_ne(SSL_SESSION_set_time(early, now), 0) + || !TEST_int_eq(SSL_CTX_add_session(ctx, early), 1) + || !TEST_long_ne(SSL_SESSION_get_time(early), now)) + goto end; + + testresult = 1; + end: + SSL_CTX_free(ctx); + SSL_SESSION_free(early); + SSL_SESSION_free(middle); + SSL_SESSION_free(late); + return testresult; +} + /* * Test 0: Client sets servername and server acknowledges it (TLSv1.2) * Test 1: Client sets servername and server does not acknowledge it (TLSv1.2) @@ -9287,6 +9410,7 @@ int setup_tests(void) #endif ADD_TEST(test_inherit_verify_param); ADD_TEST(test_set_alpn); + ADD_ALL_TESTS(test_session_timeout, 1); return 1; err: -- 2.39.2