/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/* kdc/replay.c - Replay lookaside cache for the KDC, to avoid extra work */
/*
* Copyright 1991 by the Massachusetts Institute of Technology.
* All Rights Reserved.
*
* Export of this software from the United States of America may
* require a specific license from the United States Government.
* It is the responsibility of any person or organization contemplating
* export to obtain such a license before exporting.
*
* WITHIN THAT CONSTRAINT, permission to use, copy, modify, and
* distribute this software and its documentation for any purpose and
* without fee is hereby granted, provided that the above copyright
* notice appear in all copies and that both that copyright notice and
* this permission notice appear in supporting documentation, and that
* the name of M.I.T. not be used in advertising or publicity pertaining
* to distribution of the software without specific, written prior
* permission. Furthermore if you modify this software you must label
* your software as modified software and not distribute it in such a
* fashion that it might be confused with the original M.I.T. software.
* M.I.T. makes no representations about the suitability of
* this software for any purpose. It is provided "as is" without express
* or implied warranty.
*/
#include "k5-int.h"
#include "k5-queue.h"
#include "k5-hashtab.h"
#include "kdc_util.h"
#include "extern.h"
#ifndef NOCACHE
struct entry {
K5_TAILQ_ENTRY(entry) links;
int num_hits;
krb5_timestamp timein;
krb5_data req_packet;
krb5_data reply_packet;
};
#ifndef LOOKASIDE_MAX_SIZE
#define LOOKASIDE_MAX_SIZE (10 * 1024 * 1024)
#endif
K5_LIST_HEAD(entry_list, entry);
K5_TAILQ_HEAD(entry_queue, entry);
static struct k5_hashtab *hash_table;
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 size_t total_size = 0;
#define STALE_TIME (2*60) /* two minutes */
#define STALE(ptr, now) (ts_after(now, ts_incr((ptr)->timein, STALE_TIME)))
/* Return the rough memory footprint of an entry containing req and rep. */
static size_t
entry_size(const krb5_data *req, const krb5_data *rep)
{
return sizeof(struct entry) + req->length +
((rep == NULL) ? 0 : rep->length);
}
/* Insert an entry into the cache. */
static struct entry *
insert_entry(krb5_context context, krb5_data *req, krb5_data *rep,
krb5_timestamp time)
{
krb5_error_code ret;
struct entry *entry;
size_t esize = entry_size(req, rep);
entry = calloc(1, sizeof(*entry));
if (entry == NULL)
goto error;
entry->timein = time;
ret = krb5int_copy_data_contents(context, req, &entry->req_packet);
if (ret)
goto error;
if (rep != NULL) {
ret = krb5int_copy_data_contents(context, rep, &entry->reply_packet);
if (ret)
goto error;
}
ret = k5_hashtab_add(hash_table, entry->req_packet.data,
entry->req_packet.length, entry);
if (ret)
goto error;
K5_TAILQ_INSERT_TAIL(&expiration_queue, entry, links);
num_entries++;
total_size += esize;
return entry;
error:
if (entry != NULL) {
krb5_free_data_contents(context, &entry->req_packet);
krb5_free_data_contents(context, &entry->reply_packet);
free(entry);
}
return NULL;
}
/* Remove entry from its hash bucket and the expiration queue, and free it. */
static void
discard_entry(krb5_context context, struct entry *entry)
{
total_size -= entry_size(&entry->req_packet, &entry->reply_packet);
num_entries--;
k5_hashtab_remove(hash_table, entry->req_packet.data,
entry->req_packet.length);
K5_TAILQ_REMOVE(&expiration_queue, entry, links);
krb5_free_data_contents(context, &entry->req_packet);
krb5_free_data_contents(context, &entry->reply_packet);
free(entry);
}
/* Initialize the lookaside cache structures and randomize the hash seed. */
krb5_error_code
kdc_init_lookaside(krb5_context context)
{
krb5_error_code ret;
uint8_t seed[K5_HASH_SEED_LEN];
krb5_data d = make_data(seed, sizeof(seed));
ret = krb5_c_random_make_octets(context, &d);
if (ret)
return ret;
ret = k5_hashtab_create(seed, 8192, &hash_table);
if (ret)
return ret;
K5_TAILQ_INIT(&expiration_queue);
return 0;
}
/* Remove the lookaside cache entry for a packet. */
void
kdc_remove_lookaside(krb5_context kcontext, krb5_data *req_packet)
{
struct entry *e;
e = k5_hashtab_get(hash_table, req_packet->data, req_packet->length);
if (e != NULL)
discard_entry(kcontext, e);
}
/*
* Return true and fill in reply_packet_out if req_packet is in the lookaside
* cache; otherwise return false.
*
* If the request was inserted with a NULL reply_packet to indicate that a
* request is still being processed, then return TRUE with reply_packet_out set
* to NULL.
*/
krb5_boolean
kdc_check_lookaside(krb5_context kcontext, krb5_data *req_packet,
krb5_data **reply_packet_out)
{
struct entry *e;
*reply_packet_out = NULL;
calls++;
e = k5_hashtab_get(hash_table, req_packet->data, req_packet->length);
if (e == NULL)
return FALSE;
e->num_hits++;
hits++;
/* Leave *reply_packet_out as NULL for an in-progress entry. */
if (e->reply_packet.length == 0)
return TRUE;
return (krb5_copy_data(kcontext, &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. Also discard old
* entries in the cache.
*
* The reply_packet may be NULL to indicate a request that is still processing.
*/
void
kdc_insert_lookaside(krb5_context kcontext, krb5_data *req_packet,
krb5_data *reply_packet)
{
struct entry *e, *next;
krb5_timestamp timenow;
size_t esize = entry_size(req_packet, reply_packet);
if (krb5_timeofday(kcontext, &timenow))
return;
/* Purge stale entries and limit the total size of the entries. */
K5_TAILQ_FOREACH_SAFE(e, &expiration_queue, links, next) {
if (!STALE(e, timenow) && total_size + esize <= LOOKASIDE_MAX_SIZE)
break;
max_hits_per_entry = max(max_hits_per_entry, e->num_hits);
discard_entry(kcontext, e);
}
insert_entry(kcontext, req_packet, reply_packet, timenow);
return;
}
/* Free all entries in the lookaside cache. */
void
kdc_free_lookaside(krb5_context kcontext)
{
struct entry *e, *next;
K5_TAILQ_FOREACH_SAFE(e, &expiration_queue, links, next) {
discard_entry(kcontext, e);
}
k5_hashtab_free(hash_table);
}
#endif /* NOCACHE */