[30450] in CVS-changelog-for-Kerberos-V5
krb5 commit: Add memory replay cache facility
daemon@ATHENA.MIT.EDU (Greg Hudson)
Tue Mar 12 14:14:02 2019
Date: Tue, 12 Mar 2019 14:13:32 -0400
From: Greg Hudson <ghudson@mit.edu>
Message-ID: <201903121813.x2CIDWiJ007776@drugstore.mit.edu>
To: <cvs-krb5@mit.edu>
MIME-Version: 1.0
Reply-To: krbdev@mit.edu
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Errors-To: cvs-krb5-bounces@mit.edu
https://github.com/krb5/krb5/commit/95c9c02ad5ad5a8ec1d3e709c7c81a82e47ada9f
commit 95c9c02ad5ad5a8ec1d3e709c7c81a82e47ada9f
Author: Greg Hudson <ghudson@mit.edu>
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;
+}
_______________________________________________
cvs-krb5 mailing list
cvs-krb5@mit.edu
https://mailman.mit.edu/mailman/listinfo/cvs-krb5
