krb5 commit: Use a hash table in the KDC lookaside cache
Greg Hudson
ghudson at MIT.EDU
Wed May 30 00:26:24 EDT 2012
https://github.com/krb5/krb5/commit/231cd500ed85897b69e598bb7bc7818dcc98ccb4
commit 231cd500ed85897b69e598bb7bc7818dcc98ccb4
Author: Greg Hudson <ghudson at mit.edu>
Date: Thu May 24 02:07:18 2012 -0400
Use a hash table in the KDC lookaside cache
Add a hash table to kdc/replay.c for fast lookup of incoming packets.
Continue to keep a time-ordered linked list of all entries for fast
expiry of stale entries. The preprocessor constant
LOOKASIDE_HASH_SIZE can be used to change the size of the hash table.
src/kdc/deps | 14 ++--
src/kdc/kdc_util.h | 1 +
src/kdc/main.c | 9 ++
src/kdc/replay.c | 246 ++++++++++++++++++++++++++++++----------------------
4 files changed, 160 insertions(+), 110 deletions(-)
diff --git a/src/kdc/deps b/src/kdc/deps
index b35f887..b88fd0c 100644
--- a/src/kdc/deps
+++ b/src/kdc/deps
@@ -153,13 +153,13 @@ $(OUTPRE)replay.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
$(top_srcdir)/include/k5-buf.h $(top_srcdir)/include/k5-err.h \
$(top_srcdir)/include/k5-gmt_mktime.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-thread.h \
- $(top_srcdir)/include/k5-trace.h $(top_srcdir)/include/kdb.h \
- $(top_srcdir)/include/krb5.h $(top_srcdir)/include/krb5/authdata_plugin.h \
- $(top_srcdir)/include/krb5/plugin.h $(top_srcdir)/include/krb5/preauth_plugin.h \
- $(top_srcdir)/include/net-server.h $(top_srcdir)/include/port-sockets.h \
- $(top_srcdir)/include/socket-utils.h extern.h kdc_util.h \
- replay.c
+ $(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/kdb.h $(top_srcdir)/include/krb5.h \
+ $(top_srcdir)/include/krb5/authdata_plugin.h $(top_srcdir)/include/krb5/plugin.h \
+ $(top_srcdir)/include/krb5/preauth_plugin.h $(top_srcdir)/include/net-server.h \
+ $(top_srcdir)/include/port-sockets.h $(top_srcdir)/include/socket-utils.h \
+ extern.h kdc_util.h replay.c
$(OUTPRE)kdc_authdata.$(OBJEXT): $(BUILDTOP)/include/autoconf.h \
$(BUILDTOP)/include/krb5/krb5.h $(BUILDTOP)/include/osconf.h \
$(BUILDTOP)/include/profile.h $(COM_ERR_DEPS) $(VERTO_DEPS) \
diff --git a/src/kdc/kdc_util.h b/src/kdc/kdc_util.h
index 982508a..55aafae 100644
--- a/src/kdc/kdc_util.h
+++ b/src/kdc/kdc_util.h
@@ -231,6 +231,7 @@ handle_authdata (krb5_context context,
krb5_enc_tkt_part *enc_tkt_reply);
/* replay.c */
+krb5_error_code kdc_init_lookaside(krb5_context context);
krb5_boolean kdc_check_lookaside (krb5_data *, krb5_data **);
void kdc_insert_lookaside (krb5_data *, krb5_data *);
void kdc_remove_lookaside (krb5_context kcontext, krb5_data *);
diff --git a/src/kdc/main.c b/src/kdc/main.c
index 5b31bd3..36753b7 100644
--- a/src/kdc/main.c
+++ b/src/kdc/main.c
@@ -1006,6 +1006,15 @@ int main(int argc, char **argv)
*/
initialize_realms(kcontext, argc, argv);
+#ifndef NOCACHE
+ retval = kdc_init_lookaside(kcontext);
+ if (retval) {
+ kdc_err(kcontext, retval, _("while initializing lookaside cache"));
+ finish_realms();
+ return 1;
+ }
+#endif
+
ctx = loop_init(VERTO_EV_TYPE_NONE);
if (!ctx) {
kdc_err(kcontext, ENOMEM, _("while creating main loop"));
diff --git a/src/kdc/replay.c b/src/kdc/replay.c
index 63ff95e..225320e 100644
--- a/src/kdc/replay.c
+++ b/src/kdc/replay.c
@@ -25,161 +25,201 @@
*/
#include "k5-int.h"
+#include "k5-queue.h"
#include "kdc_util.h"
#include "extern.h"
#ifndef NOCACHE
-typedef struct _krb5_kdc_replay_ent {
- struct _krb5_kdc_replay_ent *next;
+struct entry {
+ LIST_ENTRY(entry) bucket_links;
+ TAILQ_ENTRY(entry) expire_links;
int num_hits;
- krb5_int32 timein;
+ krb5_timestamp timein;
krb5_data *req_packet;
krb5_data *reply_packet;
-} krb5_kdc_replay_ent;
+};
-static krb5_kdc_replay_ent root_ptr = {0};
+#ifndef LOOKASIDE_HASH_SIZE
+#define LOOKASIDE_HASH_SIZE 16384
+#endif
+
+LIST_HEAD(entry_list, entry);
+TAILQ_HEAD(entry_queue, entry);
+
+static struct entry_list hash_table[LOOKASIDE_HASH_SIZE];
+static struct entry_queue expiration_queue;
static int hits = 0;
static int calls = 0;
static int max_hits_per_entry = 0;
static int num_entries = 0;
+static krb5_ui_4 seed;
-#define STALE_TIME 2*60 /* two minutes */
-#define STALE(ptr) (abs((ptr)->timein - timenow) >= STALE_TIME)
+#define STALE_TIME (2*60) /* two minutes */
+#define STALE(ptr, now) (abs((ptr)->timein - (now)) >= STALE_TIME)
-#define MATCH(ptr) (((ptr)->req_packet->length == inpkt->length) && \
- !memcmp((ptr)->req_packet->data, inpkt->data, \
- inpkt->length))
-/* XXX
- Todo: quench the size of the queue...
-*/
+/* Return x rotated to the left by r bits. */
+static inline krb5_ui_4
+rotl32(krb5_ui_4 x, int r)
+{
+ return (x << r) | (x >> (32 - r));
+}
-/* Removes the most recent cache entry for a given packet. */
-void
-kdc_remove_lookaside(krb5_context kcontext, krb5_data *inpkt)
+/*
+ * Return a non-cryptographic hash of data, seeded by seed (the global
+ * variable), using the MurmurHash3 algorithm by Austin Appleby. Return the
+ * result modulo LOOKASIDE_HASH_SIZE.
+ */
+static int
+murmurhash3(const krb5_data *data)
{
- register krb5_kdc_replay_ent *eptr, *last;
+ const krb5_ui_4 c1 = 0xcc9e2d51, c2 = 0x1b873593;
+ const unsigned char *start = (unsigned char *)data->data, *endblocks, *p;
+ int tail_len = (data->length % 4);
+ krb5_ui_4 h = seed, final;
+
+ endblocks = start + data->length - tail_len;
+ for (p = start; p < endblocks; p += 4) {
+ h ^= rotl32(load_32_le(p) * c1, 15) * c2;
+ h = rotl32(h, 13) * 5 + 0xe6546b64;
+ }
- if (!root_ptr.next)
- return;
+ final = 0;
+ final |= (tail_len >= 3) ? p[2] << 16 : 0;
+ final |= (tail_len >= 2) ? p[1] << 8 : 0;
+ final |= (tail_len >= 1) ? p[0] : 0;
+ h ^= rotl32(final * c1, 15) * c2;
+
+ h ^= data->length;
+ h = (h ^ (h >> 16)) * 0x85ebca6b;
+ h = (h ^ (h >> 13)) * 0xc2b2ae35;
+ h ^= h >> 16;
+ return h % LOOKASIDE_HASH_SIZE;
+}
- for (last = &root_ptr, eptr = root_ptr.next;
- eptr;
- last = eptr, eptr = eptr->next) {
- if (!MATCH(eptr))
- continue;
+/* Remove entry from its hash bucket and the expiration queue, and free it. */
+static void
+discard_entry(krb5_context context, struct entry *entry)
+{
+ LIST_REMOVE(entry, bucket_links);
+ TAILQ_REMOVE(&expiration_queue, entry, expire_links);
+ krb5_free_data(context, entry->req_packet);
+ krb5_free_data(context, entry->reply_packet);
+ free(entry);
+}
- last->next = eptr->next;
- krb5_free_data(kcontext, eptr->req_packet);
- krb5_free_data(kcontext, eptr->reply_packet);
- free(eptr);
- return;
+/* Return the entry for req_packet, or NULL if we don't have one. */
+static struct entry *
+find_entry(krb5_data *req_packet)
+{
+ krb5_ui_4 hash = murmurhash3(req_packet);
+ struct entry *e;
+
+ LIST_FOREACH(e, &hash_table[hash], bucket_links) {
+ if (data_eq(*e->req_packet, *req_packet))
+ return e;
}
+ return NULL;
}
-/* return TRUE if outpkt is filled in with a packet to reply with,
- FALSE if the caller should do the work */
+/* Initialize the lookaside cache structures and randomize the hash seed. */
+krb5_error_code
+kdc_init_lookaside(krb5_context context)
+{
+ krb5_data d = make_data(&seed, sizeof(seed));
+ int i;
+
+ for (i = 0; i < LOOKASIDE_HASH_SIZE; i++)
+ LIST_INIT(&hash_table[i]);
+ TAILQ_INIT(&expiration_queue);
+ return krb5_c_random_make_octets(context, &d);
+}
+/* Remove the lookaside cache entry for a packet. */
+void
+kdc_remove_lookaside(krb5_context kcontext, krb5_data *req_packet)
+{
+ struct entry *e;
+
+ e = find_entry(req_packet);
+ if (e != NULL)
+ discard_entry(kdc_context, e);
+}
+
+/* Return true and fill in reply_packet_out if req_packet is in the lookaside
+ * cache; otherwise return false. Also discard old entries in the cache. */
krb5_boolean
-kdc_check_lookaside(krb5_data *inpkt, krb5_data **outpkt)
+kdc_check_lookaside(krb5_data *req_packet, krb5_data **reply_packet_out)
{
krb5_int32 timenow;
- register krb5_kdc_replay_ent *eptr, *last, *hold;
-
- if (krb5_timeofday(kdc_context, &timenow))
- return FALSE;
+ struct entry *e, *next;
+ *reply_packet_out = NULL;
calls++;
- /* search for a replay entry in the queue, possibly removing
- stale entries while we're here */
-
- if (root_ptr.next) {
- for (last = &root_ptr, eptr = root_ptr.next;
- eptr;
- eptr = eptr->next) {
- if (MATCH(eptr)) {
- eptr->num_hits++;
- hits++;
-
- if (krb5_copy_data(kdc_context, eptr->reply_packet, outpkt))
- return FALSE;
- else
- return TRUE;
- /* return here, don't bother flushing even if it is stale.
- if we just matched, we may get another retransmit... */
- }
- if (STALE(eptr)) {
- /* flush it and collect stats */
- max_hits_per_entry = max(max_hits_per_entry, eptr->num_hits);
- krb5_free_data(kdc_context, eptr->req_packet);
- krb5_free_data(kdc_context, eptr->reply_packet);
- hold = eptr;
- last->next = eptr->next;
- eptr = last;
- free(hold);
- } else {
- /* this isn't it, just move along */
- last = eptr;
- }
- }
+ if (krb5_timeofday(kdc_context, &timenow) != 0)
+ return FALSE;
+
+ /* Purge stale entries using the expiration queue. */
+ TAILQ_FOREACH_SAFE(e, &expiration_queue, expire_links, next) {
+ if (!STALE(e, timenow))
+ break;
+ max_hits_per_entry = max(max_hits_per_entry, e->num_hits);
+ discard_entry(kdc_context, e);
}
- return FALSE;
-}
-/* insert a request & reply into the lookaside queue. assumes it's not
- already there, and can fail softly due to other weird errors. */
+ e = find_entry(req_packet);
+ if (e == NULL)
+ return FALSE;
+
+ e->num_hits++;
+ hits++;
+ return (krb5_copy_data(kdc_context, e->reply_packet,
+ reply_packet_out) == 0);
+}
+/* Insert a request and reply into the lookaside cache. Assumes it's not
+ * already there, and can fail silently on memory exhaustion. */
void
-kdc_insert_lookaside(krb5_data *inpkt, krb5_data *outpkt)
+kdc_insert_lookaside(krb5_data *req_packet, krb5_data *reply_packet)
{
- register krb5_kdc_replay_ent *eptr;
- krb5_int32 timenow;
+ struct entry *e;
+ krb5_timestamp timenow;
+ krb5_ui_4 hash = murmurhash3(req_packet);
if (krb5_timeofday(kdc_context, &timenow))
return;
- /* this is a new entry */
- eptr = (krb5_kdc_replay_ent *)calloc(1, sizeof(*eptr));
- if (!eptr)
+ /* Create a new entry for this request and reply. */
+ e = calloc(1, sizeof(*e));
+ if (e == NULL)
return;
- eptr->timein = timenow;
- /*
- * This is going to hurt a lot malloc()-wise due to the need to
- * allocate memory for the krb5_data and krb5_address elements.
- * ARGH!
- */
- if (krb5_copy_data(kdc_context, inpkt, &eptr->req_packet)) {
- free(eptr);
+ e->timein = timenow;
+ if (krb5_copy_data(kdc_context, req_packet, &e->req_packet)) {
+ free(e);
return;
}
- if (krb5_copy_data(kdc_context, outpkt, &eptr->reply_packet)) {
- krb5_free_data(kdc_context, eptr->req_packet);
- free(eptr);
+ if (krb5_copy_data(kdc_context, reply_packet, &e->reply_packet)) {
+ krb5_free_data(kdc_context, e->req_packet);
+ free(e);
return;
}
- eptr->next = root_ptr.next;
- root_ptr.next = eptr;
+
+ TAILQ_INSERT_TAIL(&expiration_queue, e, expire_links);
+ LIST_INSERT_HEAD(&hash_table[hash], e, bucket_links);
num_entries++;
return;
}
-/* frees memory associated with the lookaside queue for memory profiling */
+/* Free all entries in the lookaside cache. */
void
kdc_free_lookaside(krb5_context kcontext)
{
- register krb5_kdc_replay_ent *eptr, *last, *hold;
- if (root_ptr.next) {
- for (last = &root_ptr, eptr = root_ptr.next;
- eptr; eptr = eptr->next) {
- krb5_free_data(kcontext, eptr->req_packet);
- krb5_free_data(kcontext, eptr->reply_packet);
- hold = eptr;
- last->next = eptr->next;
- eptr = last;
- free(hold);
- }
+ struct entry *e, *next;
+
+ TAILQ_FOREACH_SAFE(e, &expiration_queue, expire_links, next) {
+ discard_entry(kdc_context, e);
}
}
More information about the cvs-krb5
mailing list