krb5 commit: Add memory replay cache facility

https://github.com/krb5/krb5/commit/95c9c02ad5ad5a8ec1d3e709c7c81a82e47ada9f
commit 95c9c02ad5ad5a8ec1d3e709c7c81a82e47ada9f
Author: Greg Hudson <[email protected]>
Date:   Thu Feb 28 11:47:26 2019 -0500

    Add memory replay cache facility
    
    Add a k5_memrcache type which can efficiently detect replayed tags
    without any persistence or inteprocess sharing.  Also add unit tests.

 .gitignore                        |    2 +
 src/lib/krb5/rcache/Makefile.in   |   13 +++
 src/lib/krb5/rcache/deps          |   24 ++++++
 src/lib/krb5/rcache/memrcache.c   |  165 +++++++++++++++++++++++++++++++++++++
 src/lib/krb5/rcache/memrcache.h   |   46 ++++++++++
 src/lib/krb5/rcache/t_memrcache.c |   81 ++++++++++++++++++
 6 files changed, 331 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore
index 9e0546d..8117674 100644
--- a/.gitignore
+++ b/.gitignore
@@ -389,6 +389,8 @@ local.properties
 /src/lib/krb5/os/t_std_conf
 /src/lib/krb5/os/t_trace
 
+/src/lib/krb5/rcache/t_memrcache
+
 /src/lib/krb5/unicode/.links
 /src/lib/krb5/unicode/ucdata.[ch]
 /src/lib/krb5/unicode/ucgendat.c
diff --git a/src/lib/krb5/rcache/Makefile.in b/src/lib/krb5/rcache/Makefile.in
index 5b800c5..e61b657 100644
--- a/src/lib/krb5/rcache/Makefile.in
+++ b/src/lib/krb5/rcache/Makefile.in
@@ -6,6 +6,7 @@ BUILDTOP=$(REL)..$(S)..$(S)..
 ##DOS##OBJFILE=..\$(OUTPRE)$(PREFIXDIR).lst
 
 STLIBOBJS = \
+	memrcache.o	\
 	rc_base.o	\
 	rc_dfl.o 	\
 	rc_io.o		\
@@ -16,6 +17,7 @@ STLIBOBJS = \
 	rcfns.o
 
 OBJS=	\
+	$(OUTPRE)memrcache.$(OBJEXT)	\
 	$(OUTPRE)rc_base.$(OBJEXT)	\
 	$(OUTPRE)rc_dfl.$(OBJEXT) 	\
 	$(OUTPRE)rc_io.$(OBJEXT)	\
@@ -26,6 +28,7 @@ OBJS=	\
 	$(OUTPRE)rcfns.$(OBJEXT)
 
 SRCS=	\
+	$(srcdir)/memrcache.c	\
 	$(srcdir)/rc_base.c	\
 	$(srcdir)/rc_dfl.c 	\
 	$(srcdir)/rc_io.c	\
@@ -34,6 +37,7 @@ SRCS=	\
 	$(srcdir)/rc_conv.c	\
 	$(srcdir)/ser_rc.c	\
 	$(srcdir)/rcfns.c	\
+	$(srcdir)/t_memrcache.c	\
 	$(srcdir)/t_replay.c
 
 ##DOS##LIBOBJS = $(OBJS)
@@ -41,10 +45,19 @@ SRCS=	\
 all-unix: all-libobjs
 clean-unix:: clean-libobjs
 
+t_memrcache: t_memrcache.o $(KRB5_BASE_DEPLIBS)
+	$(CC_LINK) -o $@ t_memrcache.o $(KRB5_BASE_LIBS)
+
 T_REPLAY_OBJS= t_replay.o
 
 t_replay: $(T_REPLAY_OBJS) $(KRB5_BASE_DEPLIBS)
 	$(CC_LINK) -o t_replay $(T_REPLAY_OBJS) $(KRB5_BASE_LIBS)
 
+check-unix: t_memrcache
+	$(RUN_TEST) ./t_memrcache
+
+clean-unix::
+	$(RM) t_memrcache.o t_memrcache
+
 @libobj_frag@
 
diff --git a/src/lib/krb5/rcache/deps b/src/lib/krb5/rcache/deps
index 0fe8808..445439a 100644
--- a/src/lib/krb5/rcache/deps
+++ b/src/lib/krb5/rcache/deps
@@ -1,6 +1,18 @@
 #
 # Generated makefile dependencies follow.
 #
+memrcache.so memrcache.po $(OUTPRE)memrcache.$(OBJEXT): \
+  $(BUILDTOP)/include/autoconf.h $(BUILDTOP)/include/krb5/krb5.h \
+  $(BUILDTOP)/include/osconf.h $(BUILDTOP)/include/profile.h \
+  $(COM_ERR_DEPS) $(top_srcdir)/include/k5-buf.h $(top_srcdir)/include/k5-err.h \
+  $(top_srcdir)/include/k5-gmt_mktime.h $(top_srcdir)/include/k5-hashtab.h \
+  $(top_srcdir)/include/k5-int-pkinit.h $(top_srcdir)/include/k5-int.h \
+  $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-plugin.h \
+  $(top_srcdir)/include/k5-queue.h $(top_srcdir)/include/k5-thread.h \
+  $(top_srcdir)/include/k5-trace.h $(top_srcdir)/include/krb5.h \
+  $(top_srcdir)/include/krb5/authdata_plugin.h $(top_srcdir)/include/krb5/plugin.h \
+  $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
+  memrcache.c memrcache.h
 rc_base.so rc_base.po $(OUTPRE)rc_base.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
   $(BUILDTOP)/include/krb5/krb5.h $(BUILDTOP)/include/osconf.h \
   $(BUILDTOP)/include/profile.h $(COM_ERR_DEPS) $(top_srcdir)/include/k5-buf.h \
@@ -85,6 +97,18 @@ rcfns.so rcfns.po $(OUTPRE)rcfns.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
   $(top_srcdir)/include/krb5.h $(top_srcdir)/include/krb5/authdata_plugin.h \
   $(top_srcdir)/include/krb5/plugin.h $(top_srcdir)/include/port-sockets.h \
   $(top_srcdir)/include/socket-utils.h rc-int.h rcfns.c
+t_memrcache.so t_memrcache.po $(OUTPRE)t_memrcache.$(OBJEXT): \
+  $(BUILDTOP)/include/autoconf.h $(BUILDTOP)/include/krb5/krb5.h \
+  $(BUILDTOP)/include/osconf.h $(BUILDTOP)/include/profile.h \
+  $(COM_ERR_DEPS) $(top_srcdir)/include/k5-buf.h $(top_srcdir)/include/k5-err.h \
+  $(top_srcdir)/include/k5-gmt_mktime.h $(top_srcdir)/include/k5-hashtab.h \
+  $(top_srcdir)/include/k5-int-pkinit.h $(top_srcdir)/include/k5-int.h \
+  $(top_srcdir)/include/k5-platform.h $(top_srcdir)/include/k5-plugin.h \
+  $(top_srcdir)/include/k5-queue.h $(top_srcdir)/include/k5-thread.h \
+  $(top_srcdir)/include/k5-trace.h $(top_srcdir)/include/krb5.h \
+  $(top_srcdir)/include/krb5/authdata_plugin.h $(top_srcdir)/include/krb5/plugin.h \
+  $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
+  memrcache.c memrcache.h t_memrcache.c
 t_replay.so t_replay.po $(OUTPRE)t_replay.$(OBJEXT): \
   $(BUILDTOP)/include/autoconf.h $(BUILDTOP)/include/krb5/krb5.h \
   $(BUILDTOP)/include/osconf.h $(BUILDTOP)/include/profile.h \
diff --git a/src/lib/krb5/rcache/memrcache.c b/src/lib/krb5/rcache/memrcache.c
new file mode 100644
index 0000000..90f855a
--- /dev/null
+++ b/src/lib/krb5/rcache/memrcache.c
@@ -0,0 +1,165 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/krb5/rcache/memrcache.c - in-memory replay cache implementation */
+/*
+ * Copyright (C) 2019 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "k5-int.h"
+#include "k5-queue.h"
+#include "k5-hashtab.h"
+#include "memrcache.h"
+
+struct entry {
+    K5_TAILQ_ENTRY(entry) links;
+    krb5_timestamp timestamp;
+    krb5_data tag;
+};
+
+K5_LIST_HEAD(entry_list, entry);
+K5_TAILQ_HEAD(entry_queue, entry);
+
+struct k5_memrcache_st {
+    struct k5_hashtab *hash_table;
+    struct entry_queue expiration_queue;
+};
+
+static krb5_error_code
+insert_entry(krb5_context context, k5_memrcache mrc, const krb5_data *tag,
+             krb5_timestamp now)
+{
+    krb5_error_code ret;
+    struct entry *entry = NULL;
+
+    entry = calloc(1, sizeof(*entry));
+    if (entry == NULL)
+        return ENOMEM;
+    entry->timestamp = now;
+
+    ret = krb5int_copy_data_contents(context, tag, &entry->tag);
+    if (ret)
+        goto error;
+
+    ret = k5_hashtab_add(mrc->hash_table, entry->tag.data, entry->tag.length,
+                         entry);
+    if (ret)
+        goto error;
+    K5_TAILQ_INSERT_TAIL(&mrc->expiration_queue, entry, links);
+
+    return 0;
+
+error:
+    if (entry != NULL) {
+        krb5_free_data_contents(context, &entry->tag);
+        free(entry);
+    }
+    return ret;
+}
+
+
+/* Remove entry from its hash bucket and the expiration queue, and free it. */
+static void
+discard_entry(krb5_context context, k5_memrcache mrc, struct entry *entry)
+{
+    k5_hashtab_remove(mrc->hash_table, entry->tag.data, entry->tag.length);
+    K5_TAILQ_REMOVE(&mrc->expiration_queue, entry, links);
+    krb5_free_data_contents(context, &entry->tag);
+    free(entry);
+}
+
+/* Initialize the lookaside cache structures and randomize the hash seed. */
+krb5_error_code
+k5_memrcache_create(krb5_context context, k5_memrcache *mrc_out)
+{
+    krb5_error_code ret;
+    k5_memrcache mrc;
+    uint8_t seed[K5_HASH_SEED_LEN];
+    krb5_data seed_data = make_data(seed, sizeof(seed));
+
+    *mrc_out = NULL;
+
+    ret = krb5_c_random_make_octets(context, &seed_data);
+    if (ret)
+        return ret;
+
+    mrc = calloc(1, sizeof(*mrc));
+    if (mrc == NULL)
+        return ENOMEM;
+    ret = k5_hashtab_create(seed, 64, &mrc->hash_table);
+    if (ret) {
+        free(mrc);
+        return ret;
+    }
+    K5_TAILQ_INIT(&mrc->expiration_queue);
+
+    *mrc_out = mrc;
+    return 0;
+}
+
+krb5_error_code
+k5_memrcache_store(krb5_context context, k5_memrcache mrc,
+                   const krb5_data *tag)
+{
+    krb5_error_code ret;
+    krb5_timestamp now;
+    struct entry *e, *next;
+
+    ret = krb5_timeofday(context, &now);
+    if (ret)
+        return ret;
+
+    /* Check if we already have a matching entry. */
+    e = k5_hashtab_get(mrc->hash_table, tag->data, tag->length);
+    if (e != NULL)
+        return KRB5KRB_AP_ERR_REPEAT;
+
+    /* Discard stale entries. */
+    K5_TAILQ_FOREACH_SAFE(e, &mrc->expiration_queue, links, next) {
+        if (!ts_after(now, ts_incr(e->timestamp, context->clockskew)))
+            break;
+        discard_entry(context, mrc, e);
+    }
+
+    /* Add the new entry. */
+    return insert_entry(context, mrc, tag, now);
+}
+
+/* Free all entries in the lookaside cache. */
+void
+k5_memrcache_free(krb5_context context, k5_memrcache mrc)
+{
+    struct entry *e, *next;
+
+    if (mrc == NULL)
+        return;
+    K5_TAILQ_FOREACH_SAFE(e, &mrc->expiration_queue, links, next) {
+        discard_entry(context, mrc, e);
+    }
+    k5_hashtab_free(mrc->hash_table);
+    free(mrc);
+}
diff --git a/src/lib/krb5/rcache/memrcache.h b/src/lib/krb5/rcache/memrcache.h
new file mode 100644
index 0000000..02ef730
--- /dev/null
+++ b/src/lib/krb5/rcache/memrcache.h
@@ -0,0 +1,46 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/krb5/rcache/memrcache.h - declarations for in-memory replay cache */
+/*
+ * Copyright (C) 2019 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef MEMRCACHE_H
+#define MEMRCACHE_H
+
+typedef struct k5_memrcache_st *k5_memrcache;
+
+krb5_error_code k5_memrcache_create(krb5_context context,
+                                    k5_memrcache *mrc_out);
+
+krb5_error_code k5_memrcache_store(krb5_context context, k5_memrcache mrc,
+                                   const krb5_data *tag);
+
+void k5_memrcache_free(krb5_context context, k5_memrcache mrc);
+
+#endif /* MEMRCACHE_H */
diff --git a/src/lib/krb5/rcache/t_memrcache.c b/src/lib/krb5/rcache/t_memrcache.c
new file mode 100644
index 0000000..a086042
--- /dev/null
+++ b/src/lib/krb5/rcache/t_memrcache.c
@@ -0,0 +1,81 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/krb5/rcache/t_memrcache.c - memory replay cache tests */
+/*
+ * Copyright (C) 2019 by the Massachusetts Institute of Technology.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "memrcache.c"
+
+int
+main()
+{
+    krb5_error_code ret;
+    krb5_context context;
+    k5_memrcache mrc;
+    int i;
+    uint8_t tag[4];
+    krb5_data tag_data = make_data(tag, 4);
+    struct entry *e;
+
+    ret = krb5_init_context(&context);
+    assert(ret == 0);
+
+    /* Store a thousand unique tags, then verify that they all appear as
+     * replays. */
+    ret = k5_memrcache_create(context, &mrc);
+    assert(ret == 0);
+    for (i = 0; i < 1000; i++) {
+        store_32_be(i, tag);
+        ret = k5_memrcache_store(context, mrc, &tag_data);
+        assert(ret == 0);
+    }
+    for (i = 0; i < 1000; i++) {
+        store_32_be(i, tag);
+        ret = k5_memrcache_store(context, mrc, &tag_data);
+        assert(ret == KRB5KRB_AP_ERR_REPEAT);
+    }
+    k5_memrcache_free(context, mrc);
+
+    /* Store a thousand unique tags, each spaced out so that previous entries
+     * appear as expired.  Verify that the expiration queue has one entry. */
+    ret = k5_memrcache_create(context, &mrc);
+    assert(ret == 0);
+    context->clockskew = 100;
+    for (i = 1; i < 1000; i++) {
+        krb5_set_debugging_time(context, i * 200, 0);
+        store_32_be(i, tag);
+        ret = k5_memrcache_store(context, mrc, &tag_data);
+        assert(ret == 0);
+    }
+    e = K5_TAILQ_FIRST(&mrc->expiration_queue);
+    assert(e != NULL && K5_TAILQ_NEXT(e, links) == NULL);
+    k5_memrcache_free(context, mrc);
+
+    return 0;
+}