krb5 commit: Add file2 rcache type
Greg Hudson
ghudson at mit.edu
Fri May 31 15:45:11 EDT 2019
https://github.com/krb5/krb5/commit/12117dbc61639ff3fb510f2feb2de8c41dd2bd23
commit 12117dbc61639ff3fb510f2feb2de8c41dd2bd23
Author: Greg Hudson <ghudson at mit.edu>
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;
+}
More information about the cvs-krb5
mailing list