replay.c

/* -*- 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 */