krb5 commit: Add file2 rcache type

https://github.com/krb5/krb5/commit/12117dbc61639ff3fb510f2feb2de8c41dd2bd23
commit 12117dbc61639ff3fb510f2feb2de8c41dd2bd23
Author: Greg Hudson <[email protected]>
Date:   Tue May 14 12:13:35 2019 -0400

    Add file2 rcache type
    
    Add a new replay cache type using a hash-based file format.
    
    ticket: 8786

 .gitignore                         |    2 +
 doc/basic/rcache_def.rst           |   24 ++-
 doc/formats/index.rst              |    1 +
 doc/formats/rcache_file_format.rst |   50 ++++++
 src/lib/krb5/rcache/Makefile.in    |   13 ++-
 src/lib/krb5/rcache/rc-int.h       |    6 +
 src/lib/krb5/rcache/rc_base.c      |    3 +-
 src/lib/krb5/rcache/rc_file2.c     |  306 ++++++++++++++++++++++++++++++++++++
 src/lib/krb5/rcache/t_rcfile2.c    |  212 +++++++++++++++++++++++++
 9 files changed, 607 insertions(+), 10 deletions(-)

diff --git a/.gitignore b/.gitignore
index 140f0f8..bc15f78 100644
--- a/.gitignore
+++ b/.gitignore
@@ -388,6 +388,8 @@ local.properties
 /src/lib/krb5/os/t_trace
 
 /src/lib/krb5/rcache/t_memrcache
+/src/lib/krb5/rcache/t_rcfile2
+/src/lib/krb5/rcache/testrcache
 
 /src/lib/krb5/unicode/.links
 /src/lib/krb5/unicode/ucdata.[ch]
diff --git a/doc/basic/rcache_def.rst b/doc/basic/rcache_def.rst
index 2de9533..56d369d 100644
--- a/doc/basic/rcache_def.rst
+++ b/doc/basic/rcache_def.rst
@@ -9,7 +9,7 @@ request is detected in the replay cache, an error message is sent to
 the application program.
 
 The replay cache interface, like the credential cache and
-:ref:`keytab_definition` interfaces, uses `type:value` strings to
+:ref:`keytab_definition` interfaces, uses `type:residual` strings to
 indicate the type of replay cache and any associated cache naming
 data to use.
 
@@ -57,17 +57,27 @@ additional messages), or if the simple act of presenting the
 authenticator triggers some interesting action in the service being
 attacked.
 
-Default rcache type
--------------------
+Replay cache types
+------------------
+
+Unlike the credential cache and keytab interfaces, replay cache types
+are in lowercase.  The following types are defined:
+
+#. **none** disables the replay cache.  The residual value is ignored.
+
+#. **file2** (new in release 1.18) uses a hash-based format to store
+   replay records.  The file may grow to accomodate hash collisions.
+   The residual value is the filename.
 
-There is currently only one implemented kind of replay cache, called
-**dfl**.  It stores replay data in one file, occasionally rewriting it
-to purge old, expired entries.
+#. **dfl** is the default type if no environment variable or
+   configuration specifies a different type.  It stores replay data in
+   a file, occasionally rewriting it to purge old, expired entries.
 
 The default type can be overridden by the **KRB5RCACHETYPE**
 environment variable.
 
-The placement of the replay cache file is determined by the following:
+For the dfl type, the placement of the replay cache file is determined
+by the following:
 
 #. The **KRB5RCACHEDIR** environment variable;
 
diff --git a/doc/formats/index.rst b/doc/formats/index.rst
index 4ad5344..47dea12 100644
--- a/doc/formats/index.rst
+++ b/doc/formats/index.rst
@@ -6,5 +6,6 @@ Protocols and file formats
 
    ccache_file_format
    keytab_file_format
+   rcache_file_format
    cookie
    freshness_token
diff --git a/doc/formats/rcache_file_format.rst b/doc/formats/rcache_file_format.rst
new file mode 100644
index 0000000..42ee828
--- /dev/null
+++ b/doc/formats/rcache_file_format.rst
@@ -0,0 +1,50 @@
+Replay cache file format
+========================
+
+This section documents the second version of the replay cache file
+format, used by the "file2" replay cache type (new in release 1.18).
+The first version of the file replay cache format is not documented.
+
+All accesses to the replay cache file take place under an exclusive
+POSIX or Windows file lock, obtained when the file is opened and
+released when it is closed.  Replay cache files are automatically
+created when first accessed.
+
+For each store operation, a tag is derived from the checksum part of
+the :RFC:`3961` ciphertext of the authenticator.  The checksum is
+coerced to a fixed length of 12 bytes, either through truncation or
+right-padding with zero bytes.  A four-byte timestamp is appended to
+the tag to produce a total record length of 16 bytes.
+
+Bytes 0 through 15 of the file contain a hash seed for the SipHash-2-4
+algorithm (siphash_); this field is populated with random bytes when
+the file is first created.  All remaining bytes are divided into a
+series of expanding hash tables:
+
+* Bytes 16-16383: hash table 1 (1023 slots)
+* Bytes 16384-49151: hash table 2 (2048 slots)
+* Bytes 49152-114687: hash table 3 (4096 slots)
+* ...
+
+Only some hash tables will be present in the file at any specific
+time, and the final table may be only partially filled.  Replay cache
+files may be sparse if the filesystem supports it.
+
+For each table present in the file, the tag is hashed with SipHash-2-4
+using the seed recorded in the file.  The first byte of the seed is
+incremented by one (modulo 256) for each table after the first.  The
+resulting hash value is taken modulo one less than the table size
+(1022 for the first hash table, 2047 for the second) to produce the
+index.  The record may be found at the slot given by the index or at
+the next slot.
+
+All candidate locations for the record must be searched until a slot
+is found with a timestamp of zero (indicating a slot which has never
+been written to) or an offset is reached at or beyond the end of the
+file.  Any candidate location with a timestamp value of zero, with a
+timestamp value less than the current time minus clockskew, or at or
+beyond the end of the file is available for writing.  When all
+candidate locations have been searched without finding a match, the
+new entry is written to the earliest candidate available for writing.
+
+.. _siphash: https://131002.net/siphash/siphash.pdf
diff --git a/src/lib/krb5/rcache/Makefile.in b/src/lib/krb5/rcache/Makefile.in
index e61b657..0513937 100644
--- a/src/lib/krb5/rcache/Makefile.in
+++ b/src/lib/krb5/rcache/Makefile.in
@@ -9,6 +9,7 @@ STLIBOBJS = \
 	memrcache.o	\
 	rc_base.o	\
 	rc_dfl.o 	\
+	rc_file2.o	\
 	rc_io.o		\
 	rcdef.o		\
 	rc_none.o	\
@@ -20,6 +21,7 @@ OBJS=	\
 	$(OUTPRE)memrcache.$(OBJEXT)	\
 	$(OUTPRE)rc_base.$(OBJEXT)	\
 	$(OUTPRE)rc_dfl.$(OBJEXT) 	\
+	$(OUTPRE)rc_file2.$(OBJEXT) 	\
 	$(OUTPRE)rc_io.$(OBJEXT)	\
 	$(OUTPRE)rcdef.$(OBJEXT)	\
 	$(OUTPRE)rc_none.$(OBJEXT)	\
@@ -31,6 +33,7 @@ SRCS=	\
 	$(srcdir)/memrcache.c	\
 	$(srcdir)/rc_base.c	\
 	$(srcdir)/rc_dfl.c 	\
+	$(srcdir)/rc_file2.c 	\
 	$(srcdir)/rc_io.c	\
 	$(srcdir)/rcdef.c	\
 	$(srcdir)/rc_none.c	\
@@ -48,16 +51,22 @@ clean-unix:: clean-libobjs
 t_memrcache: t_memrcache.o $(KRB5_BASE_DEPLIBS)
 	$(CC_LINK) -o $@ t_memrcache.o $(KRB5_BASE_LIBS)
 
+t_rcfile2: t_rcfile2.o $(KRB5_BASE_DEPLIBS)
+	$(CC_LINK) -o $@ t_rcfile2.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
+check-unix: t_memrcache t_rcfile2
 	$(RUN_TEST) ./t_memrcache
+	$(RUN_TEST) ./t_rcfile2 testrcache expiry 10000
+	$(RUN_TEST) ./t_rcfile2 testrcache concurrent 10 1000
+	$(RUN_TEST) ./t_rcfile2 testrcache race 10 100
 
 clean-unix::
-	$(RM) t_memrcache.o t_memrcache
+	$(RM) t_memrcache.o t_memrcache t_rcfile2.o t_rcfile2 testrcache
 
 @libobj_frag@
 
diff --git a/src/lib/krb5/rcache/rc-int.h b/src/lib/krb5/rcache/rc-int.h
index 72a9483..599b736 100644
--- a/src/lib/krb5/rcache/rc-int.h
+++ b/src/lib/krb5/rcache/rc-int.h
@@ -86,6 +86,12 @@ typedef struct _krb5_rc_ops krb5_rc_ops;
 krb5_error_code krb5_rc_register_type(krb5_context, const krb5_rc_ops *);
 
 extern const krb5_rc_ops krb5_rc_dfl_ops;
+extern const krb5_rc_ops krb5_rc_file2_ops;
 extern const krb5_rc_ops krb5_rc_none_ops;
 
+/* Check and store a replay record in an open (but not locked) file descriptor,
+ * using the file2 format.  fd is assumed to be at offset 0. */
+krb5_error_code k5_rcfile2_store(krb5_context context, int fd,
+                                 krb5_donot_replay *rep);
+
 #endif /* __KRB5_RCACHE_INT_H__ */
diff --git a/src/lib/krb5/rcache/rc_base.c b/src/lib/krb5/rcache/rc_base.c
index 9fa4643..c5f1d23 100644
--- a/src/lib/krb5/rcache/rc_base.c
+++ b/src/lib/krb5/rcache/rc_base.c
@@ -19,7 +19,8 @@ struct krb5_rc_typelist {
     struct krb5_rc_typelist *next;
 };
 static struct krb5_rc_typelist none = { &krb5_rc_none_ops, 0 };
-static struct krb5_rc_typelist krb5_rc_typelist_dfl = { &krb5_rc_dfl_ops, &none };
+static struct krb5_rc_typelist file2 = { &krb5_rc_file2_ops, &none };
+static struct krb5_rc_typelist krb5_rc_typelist_dfl = { &krb5_rc_dfl_ops, &file2 };
 static struct krb5_rc_typelist *typehead = &krb5_rc_typelist_dfl;
 static k5_mutex_t rc_typelist_lock = K5_MUTEX_PARTIAL_INITIALIZER;
 
diff --git a/src/lib/krb5/rcache/rc_file2.c b/src/lib/krb5/rcache/rc_file2.c
new file mode 100644
index 0000000..e34c43a
--- /dev/null
+++ b/src/lib/krb5/rcache/rc_file2.c
@@ -0,0 +1,306 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/krb5/rcache/rc_file2.c - file-based replay cache, version 2 */
+/*
+ * 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-hashtab.h"
+#include "rc-int.h"
+#ifndef _WIN32
+#include <sys/types.h>
+#include <sys/stat.h>
+#endif
+
+#define MAX_SIZE INT32_MAX
+#define TAG_LEN 12
+#define RECORD_LEN (TAG_LEN + 4)
+#define FIRST_TABLE_RECORDS 1023
+
+/* Return the offset and number of records in the next table.  *offset should
+ * initially be -1. */
+static inline krb5_error_code
+next_table(off_t *offset, off_t *nrecords)
+{
+    if (*offset == -1) {
+        *offset = K5_HASH_SEED_LEN;
+        *nrecords = FIRST_TABLE_RECORDS;
+    } else if (*offset == K5_HASH_SEED_LEN) {
+        *offset += *nrecords * RECORD_LEN;
+        *nrecords = (FIRST_TABLE_RECORDS + 1) * 2;
+    } else {
+        *offset += *nrecords * RECORD_LEN;
+        *nrecords *= 2;
+    }
+
+    /* Make sure the next table fits within the maximum file size. */
+    if (*nrecords > MAX_SIZE / RECORD_LEN)
+        return EOVERFLOW;
+    if (*offset > MAX_SIZE - (*nrecords * RECORD_LEN))
+        return EOVERFLOW;
+
+    return 0;
+}
+
+/* Read up to two records from fd at offset, and parse them out into tags and
+ * timestamps.  Place the number of records read in *nread. */
+static krb5_error_code
+read_records(int fd, off_t offset, uint8_t tag1_out[TAG_LEN],
+             uint32_t *timestamp1_out, uint8_t tag2_out[TAG_LEN],
+             uint32_t *timestamp2_out, int *nread)
+{
+    uint8_t buf[RECORD_LEN * 2];
+    ssize_t st;
+
+    *nread = 0;
+
+    st = lseek(fd, offset, SEEK_SET);
+    if (st == -1)
+        return errno;
+    st = read(fd, buf, RECORD_LEN * 2);
+    if (st == -1)
+        return errno;
+
+    if (st >= RECORD_LEN) {
+        memcpy(tag1_out, buf, TAG_LEN);
+        *timestamp1_out = load_32_be(buf + TAG_LEN);
+        *nread = 1;
+    }
+    if (st == RECORD_LEN * 2) {
+        memcpy(tag2_out, buf + RECORD_LEN, TAG_LEN);
+        *timestamp2_out = load_32_be(buf + RECORD_LEN + TAG_LEN);
+        *nread = 2;
+    }
+    return 0;
+}
+
+/* Write one record to fd at offset, marshalling the tag and timestamp. */
+static krb5_error_code
+write_record(int fd, off_t offset, const uint8_t tag[TAG_LEN],
+             uint32_t timestamp)
+{
+    uint8_t record[RECORD_LEN];
+    ssize_t st;
+
+    memcpy(record, tag, TAG_LEN);
+    store_32_be(timestamp, record + TAG_LEN);
+
+    st = lseek(fd, offset, SEEK_SET);
+    if (st == -1)
+        return errno;
+    st = write(fd, record, RECORD_LEN);
+    if (st == -1)
+        return errno;
+    if (st != RECORD_LEN) /* Unexpected for a regular file */
+        return EIO;
+
+    return 0;
+}
+
+/* Check and store a record into an open and locked file.  fd is assumed to be
+ * at offset 0. */
+static krb5_error_code
+store(krb5_context context, int fd, const uint8_t tag[TAG_LEN], uint32_t now,
+      uint32_t skew)
+{
+    krb5_error_code ret;
+    krb5_data d;
+    off_t table_offset = -1, nrecords = 0, avail_offset = -1, record_offset;
+    ssize_t st;
+    int ind, nread;
+    uint8_t seed[K5_HASH_SEED_LEN], rec1_tag[TAG_LEN], rec2_tag[TAG_LEN];
+    uint32_t rec1_stamp, rec2_stamp;
+
+    /* Read or generate the hash seed. */
+    st = read(fd, seed, sizeof(seed));
+    if (st < 0)
+        return errno;
+    if ((size_t)st < sizeof(seed)) {
+        d = make_data(seed, sizeof(seed));
+        ret = krb5_c_random_make_octets(context, &d);
+        if (ret)
+            return ret;
+        st = write(fd, seed, sizeof(seed));
+        if (st < 0)
+            return errno;
+        if ((size_t)st != sizeof(seed))
+            return EIO;
+    }
+
+    for (;;) {
+        ret = next_table(&table_offset, &nrecords);
+        if (ret)
+            return ret;
+
+        ind = k5_siphash24(tag, TAG_LEN, seed) % nrecords;
+        record_offset = table_offset + ind * RECORD_LEN;
+
+        ret = read_records(fd, record_offset, rec1_tag, &rec1_stamp, rec2_tag,
+                           &rec2_stamp, &nread);
+        if (ret)
+            return ret;
+
+        if ((nread >= 1 && memcmp(rec1_tag, tag, TAG_LEN) == 0) ||
+            (nread == 2 && memcmp(rec2_tag, tag, TAG_LEN) == 0))
+            return KRB5KRB_AP_ERR_REPEAT;
+
+        if (avail_offset == -1) {
+            if (nread == 0 || ts_after(now, ts_incr(rec1_stamp, skew)))
+                avail_offset = record_offset;
+            else if (nread == 1 || ts_after(now, ts_incr(rec2_stamp, skew)))
+                avail_offset = record_offset + RECORD_LEN;
+        }
+
+        if (nread < 2 || rec1_stamp == 0 || rec2_stamp == 0)
+            return write_record(fd, avail_offset, tag, now);
+
+        /* Use a different hash seed for the next table we search. */
+        seed[0]++;
+    }
+}
+
+krb5_error_code
+k5_rcfile2_store(krb5_context context, int fd, krb5_donot_replay *rep)
+{
+    krb5_error_code ret;
+    krb5_timestamp now;
+    uint8_t tag[TAG_LEN];
+
+    if (rep->tag.length == 0)
+        return EINVAL;
+
+    ret = krb5_timeofday(context, &now);
+    if (ret)
+        return ret;
+
+    if (rep->tag.length >= TAG_LEN) {
+        memcpy(tag, rep->tag.data, TAG_LEN);
+    } else {
+        memcpy(tag, rep->tag.data, rep->tag.length);
+        memset(tag + rep->tag.length, 0, TAG_LEN - rep->tag.length);
+    }
+
+    ret = krb5_lock_file(context, fd, KRB5_LOCKMODE_EXCLUSIVE);
+    if (ret)
+        return ret;
+    ret = store(context, fd, tag, now, context->clockskew);
+    (void)krb5_unlock_file(NULL, fd);
+    return ret;
+}
+
+static char * KRB5_CALLCONV
+file2_get_name(krb5_context context, krb5_rcache rc)
+{
+    return (char *)rc->data;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_get_span(krb5_context context, krb5_rcache rc, krb5_deltat *lifespan)
+{
+    *lifespan = context->clockskew;
+    return 0;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_init(krb5_context context, krb5_rcache rc, krb5_deltat lifespan)
+{
+    return 0;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_close(krb5_context context, krb5_rcache rc)
+{
+    k5_mutex_destroy(&rc->lock);
+    free(rc->data);
+    free(rc);
+    return 0;
+}
+
+#define file2_destroy file2_close
+
+static krb5_error_code KRB5_CALLCONV
+file2_resolve(krb5_context context, krb5_rcache rc, char *name)
+{
+    rc->data = strdup(name);
+    return (rc->data == NULL) ? ENOMEM : 0;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_recover(krb5_context context, krb5_rcache rc)
+{
+    return 0;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_recover_or_init(krb5_context context, krb5_rcache rc,
+                      krb5_deltat lifespan)
+{
+    return 0;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_store(krb5_context context, krb5_rcache rc, krb5_donot_replay *rep)
+{
+    krb5_error_code ret;
+    const char *filename = rc->data;
+    int fd;
+
+    fd = open(filename, O_CREAT | O_RDWR | O_BINARY, 0600);
+    if (fd < 0) {
+        ret = errno;
+        k5_setmsg(context, ret, "%s (filename: %s)", error_message(ret),
+                  filename);
+        return ret;
+    }
+    ret = k5_rcfile2_store(context, fd, rep);
+    close(fd);
+    return ret;
+}
+
+static krb5_error_code KRB5_CALLCONV
+file2_expunge(krb5_context context, krb5_rcache rc)
+{
+    return 0;
+}
+
+const krb5_rc_ops krb5_rc_file2_ops =
+{
+    0,
+    "file2",
+    file2_init,
+    file2_recover,
+    file2_recover_or_init,
+    file2_destroy,
+    file2_close,
+    file2_store,
+    file2_expunge,
+    file2_get_span,
+    file2_get_name,
+    file2_resolve
+};
diff --git a/src/lib/krb5/rcache/t_rcfile2.c b/src/lib/krb5/rcache/t_rcfile2.c
new file mode 100644
index 0000000..cc32719
--- /dev/null
+++ b/src/lib/krb5/rcache/t_rcfile2.c
@@ -0,0 +1,212 @@
+/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+/* lib/krb5/rcache/t_rcfile2.c - rcache file version 2 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.
+ */
+
+/*
+ * Usage:
+ *
+ *   t_rcfile2 <filename> expiry <nreps>
+ *     store <nreps> records spaced far enough apart that all records appear
+ *     expired; verify that the file size doesn't increase beyond one table.
+ *
+ *   t_rcfile2 <filename> concurrent <nprocesses> <nreps>
+ *     spawn <nprocesses> subprocesses, each of which stores <nreps> unique
+ *     tags.  As each process completes, the master process tests that the
+ *     records stored by the subprocess appears as replays.
+ *
+ *   t_rcfile2 <filename> race <nprocesses> <nreps>
+ *     spawn <nprocesses> subprocesses, each of which tries to store the same
+ *     tag and reports success or failure.  The master process verifies that
+ *     exactly one subprocess succeeds.  Repeat <reps> times.
+ */
+
+#include "rc_file2.c"
+#include <sys/wait.h>
+#include <sys/time.h>
+
+krb5_context ctx;
+
+static krb5_error_code
+test_store(krb5_rcache rc, uint8_t *tag, krb5_timestamp timestamp,
+           const uint32_t clockskew)
+{
+    krb5_donot_replay rep = { 0 };
+
+    ctx->clockskew = clockskew;
+    (void)krb5_set_debugging_time(ctx, timestamp, 0);
+    rep.tag = make_data(tag, TAG_LEN);
+    return file2_store(ctx, rc, &rep);
+}
+
+/* Store a sequence of unique tags, with timestamps far enough apart that all
+ * previous records appear expired.  Verify that we only use one table. */
+static void
+expiry_test(krb5_rcache rc, int reps, const char *filename)
+{
+    krb5_error_code ret;
+    struct stat statbuf;
+    uint8_t tag[TAG_LEN] = { 0 }, seed[K5_HASH_SEED_LEN] = { 0 }, data[4];
+    uint32_t timestamp;
+    const uint32_t clockskew = 5, start = 1000;
+    uint64_t hashval;
+    int i, st;
+
+    assert((uint32_t)reps < (UINT32_MAX - start) / clockskew / 2);
+    for (i = 0, timestamp = start; i < reps; i++, timestamp += clockskew * 2) {
+        store_32_be(i, data);
+        hashval = k5_siphash24(data, 4, seed);
+        store_64_be(hashval, tag);
+
+        ret = test_store(rc, tag, timestamp, clockskew);
+        assert(ret == 0);
+
+        /* Since we increment timestamp enough to expire every record between
+         * each call, we should never create a second hash table. */
+        st = stat(filename, &statbuf);
+        assert(st == 0);
+        assert(statbuf.st_size <= (FIRST_TABLE_RECORDS + 1) * RECORD_LEN);
+    }
+}
+
+/* Store a sequence of unique tags with the same timestamp.  Exit with failure
+ * if any store operation doesn't succeed or fail as given by expect_fail. */
+static void
+store_records(krb5_rcache rc, int id, int reps, int expect_fail)
+{
+    krb5_error_code ret;
+    uint8_t tag[TAG_LEN] = { 0 };
+    int i;
+
+    store_32_be(id, tag);
+    for (i = 0; i < reps; i++) {
+        store_32_be(i, tag + 4);
+        ret = test_store(rc, tag, 1000, 100);
+        if (ret != (expect_fail ? KRB5KRB_AP_ERR_REPEAT : 0)) {
+            fprintf(stderr, "store %d %d %sfail\n", id, i,
+                    expect_fail ? "didn't " : "");
+            _exit(1);
+        }
+    }
+}
+
+/* Spawn multiple child processes, each storing a sequence of unique tags.
+ * After each process completes, verify that its tags appear as replays. */
+static void
+concurrency_test(krb5_rcache rc, int nchildren, int reps)
+{
+    pid_t *pids, pid;
+    int i, nprocs, status;
+
+    pids = calloc(nchildren, sizeof(*pids));
+    assert(pids != NULL);
+    for (i = 0; i < nchildren; i++) {
+        pids[i] = fork();
+        assert(pids[i] != -1);
+        if (pids[i] == 0) {
+            store_records(rc, i, reps, 0);
+            _exit(0);
+        }
+    }
+    for (nprocs = nchildren; nprocs > 0; nprocs--) {
+        pid = wait(&status);
+        assert(pid != -1 && WIFEXITED(status) && WEXITSTATUS(status) == 0);
+        for (i = 0; i < nchildren; i++) {
+            if (pids[i] == pid)
+                store_records(rc, i, reps, 1);
+        }
+    }
+    free(pids);
+}
+
+/* Spawn multiple child processes, all trying to store the same tag.  Verify
+ * that only one of the processes succeeded.  Repeat reps times. */
+static void
+race_test(krb5_rcache rc, int nchildren, int reps)
+{
+    int i, j, status, nsuccess;
+    uint8_t tag[TAG_LEN] = { 0 };
+    pid_t pid;
+
+    for (i = 0; i < reps; i++) {
+        store_32_be(i, tag);
+        for (j = 0; j < nchildren; j++) {
+            pid = fork();
+            assert(pid != -1);
+            if (pid == 0)
+                _exit(test_store(rc, tag, 1000, 100) != 0);
+        }
+
+        nsuccess = 0;
+        for (j = 0; j < nchildren; j++) {
+            pid = wait(&status);
+            assert(pid != -1);
+            if (WIFEXITED(status) && WEXITSTATUS(status) == 0)
+                nsuccess++;
+        }
+        assert(nsuccess == 1);
+    }
+}
+
+int
+main(int argc, char **argv)
+{
+    const char *filename, *cmd;
+    struct krb5_rc_st rc = { 0 };
+
+    argv++;
+    assert(*argv != NULL);
+
+    if (krb5_init_context(&ctx) != 0)
+        abort();
+
+    assert(*argv != NULL);
+    filename = *argv++;
+    unlink(filename);
+    rc.data = (void *)filename;
+
+    assert(*argv != NULL);
+    cmd = *argv++;
+    if (strcmp(cmd, "expiry") == 0) {
+        assert(argv[0] != NULL);
+        expiry_test(&rc, atoi(argv[0]), filename);
+    } else if (strcmp(cmd, "concurrent") == 0) {
+        assert(argv[0] != NULL && argv[1] != NULL);
+        concurrency_test(&rc, atoi(argv[0]), atoi(argv[1]));
+    } else if (strcmp(cmd, "race") == 0) {
+        assert(argv[0] != NULL && argv[1] != NULL);
+        race_test(&rc, atoi(argv[0]), atoi(argv[1]));
+    } else {
+        abort();
+    }
+
+    krb5_free_context(ctx);
+    return 0;
+}