path: root/module/storage.c

/*
 * Copyright (c) 2009, Stefan Walter
 * 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.
 *     * The names of contributors to this software may not be
 *       used to endorse or promote products derived from this
 *       software without specific prior written permission.
 *
 * 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 OWNER 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.
 *
 *
 * CONTRIBUTORS
 *  Stef Walter <stef@memberwebs.com>
 *
 */

#include "mod_auth_singleid.h"

#include <assert.h>
#include <string.h>

#include <apr_sha1.h>

/* Yes, this looks backwards. */
typedef char sid_nonce_t[40];

struct sid_storage {

	/* The association with our server */
	char server[256];
	char handle[256];
	unsigned char secret[256];
	char type[64];
	size_t n_secret;
	time_t expires;

	/* Book keeping for the records */
	sid_nonce_t *records;
	size_t last;
	size_t total;
	size_t count;
};

sid_storage_t*
sid_storage_initialize (void *memory, size_t n_memory)
{
	sid_storage_t *storage;

	if (!memory)
		return NULL;
	if (n_memory < sizeof (sid_storage_t) + (sizeof (sid_nonce_t) * 3))
		return NULL;

	storage = memory;
	memset (storage, 0, sizeof (storage));

	/* Note that we assume that it's all blank */
	storage->records = (sid_nonce_t*)(storage + 1);
	storage->total = (n_memory - sizeof (sid_storage_t)) / sizeof (sid_nonce_t);
	storage->last = 0;
	storage->count = 1;

	return storage;
}

int
sid_storage_store_assoc (sid_storage_t *store, const sid_assoc_t *assoc)
{
	assert (store);
	assert (assoc);

	/* Check that we have enough space to store this information */
	if ((assoc->server && strlen (assoc->server) > sizeof (store->server)) ||
	    (assoc->handle && strlen (assoc->handle) > sizeof (store->handle)) ||
	    (assoc->n_secret && assoc->n_secret > sizeof (store->secret)) ||
	    (assoc->type && strlen (assoc->type) > sizeof (store->type)))
		return 0;

	strcpy (store->server, assoc->server ? assoc->server : "");
	strcpy (store->handle, assoc->handle ? assoc->handle : "");
	memcpy (store->secret, assoc->secret, assoc->n_secret);
	store->n_secret = assoc->n_secret;
	strcpy (store->type, assoc->type ? assoc->type : "");
	store->expires = assoc->expires;
	return 1;
}

int
sid_storage_find_assoc (sid_storage_t *store, const char *server,
                           const char *handle, sid_assoc_t *assoc)
{
	assert (store);
	assert (assoc);

	if (server && (strlen (server) > sizeof (store->server) ||
		       strcmp (server, store->server) != 0))
		return 0;

	if (handle && (strlen (handle) > sizeof (store->handle) ||
	               strcmp (handle, store->handle) != 0))
		return 0;

	assoc->server = store->server;
	assoc->handle = store->handle;
	assoc->type = store->type;
	assoc->secret = store->secret;
	assoc->n_secret = store->n_secret;
	assoc->expires = store->expires;
	return 1;
}

void
sid_storage_invalidate_assoc (sid_storage_t *store, const char *server,
                                 const char *handle)
{
	sid_assoc_t dummy;
	assert (store);

	if (sid_storage_find_assoc (store, server, handle, &dummy)) {
		store->server[0] = 0;
		store->handle[0] = 0;
		store->type[0] = 0;
		memset (store->secret, 0, sizeof (store->secret));
		store->n_secret = 0;
		store->expires = 0;
		store->secret[0] = 0;
	}
}

#define nonce_compare(a, b) \
	memcmp (a, b, sizeof (sid_nonce_t))

static void
nonce_put (sid_nonce_t rec, const char *nonce)
{
	size_t len = strlen (nonce);
	char *dst = (char*)rec;

	assert (sizeof (sid_nonce_t) == 40);

	/* If it's short enough, then just store. Fast */
	if (len < 40) {
		memcpy (dst, nonce, len);
		memset (dst + len, 0, 40 - len);

	/* Too long, need to compress into the record */
	} else {
		apr_sha1_ctx_t ctx;

		assert (APR_SHA1_DIGESTSIZE == 20);

		/* The date prefix we just copy in */
		memcpy (dst, nonce, 20);

		/* Hash the rest into the buffer */
		apr_sha1_init (&ctx);
		apr_sha1_update (&ctx, nonce + 20, len - 20);
		apr_sha1_final ((unsigned char*)dst + 20, &ctx);
	}
}

static void
bump_ring_forwards (sid_storage_t *store, size_t beg, size_t end)
{
	sid_nonce_t *records;

	assert (store);
	assert (end <= store->total);

	if (beg == end)
		return;

	records = store->records;
	assert (beg < store->total);

	/* Simple memmove forward? */
	if (end < store->total && beg < end) {
		memmove (store->records + beg + 1, store->records + beg,
		         (end - beg) * sizeof (sid_nonce_t));

	/* We wrap, far more complex */
	} else {
		if (end < beg)
			memmove (store->records + 1, store->records,
			         end * sizeof (sid_nonce_t));
		memcpy (store->records, store->records + store->total - 1,
		        sizeof (sid_nonce_t));
		memmove (store->records + beg + 1, store->records + beg,
		         (store->total - beg - 1) * sizeof (sid_nonce_t));
	}
}

static void
bump_ring_backwards (sid_storage_t *store, size_t beg, size_t end)
{
	sid_nonce_t *records;

	assert (store);
	assert (end <= store->total);

	if (beg == end)
		return;

	records = store->records;
	assert (beg < store->total);

	/* Simple memmove backwards? */
	if (beg > 0 && beg < end) {
		memmove (store->records + beg - 1, store->records + beg,
		         (end - beg) * sizeof (sid_nonce_t));

	/* We wrap, far more complex */
	} else {
		if (end < beg)
			memmove (store->records + beg - 1, store->records + beg,
			         (store->total - beg) * sizeof (sid_nonce_t));
		memcpy (store->records + store->total - 1, store->records,
		        sizeof (sid_nonce_t));
		memmove (store->records, store->records + 1,
		         (end - 1) * sizeof (sid_nonce_t));
	}
}

static void
insert_nonce_ring (sid_storage_t *store, sid_nonce_t rec, size_t idx)
{
	sid_nonce_t *records = store->records;
	size_t off, top, bottom;

	assert (store->total > 2);
	assert (idx < store->total);

	/* Calculate the distance on either side of last */
	bottom = store->last;
	top = store->last + store->total;
	off = idx;
	if (off <= bottom)
		off += store->total;

	/* Backwards move */
	if (off - bottom < top - off) {
		bump_ring_backwards (store, (store->last + 2) % store->total, idx);
		memcpy (records + idx - 1, rec, sizeof (sid_nonce_t));

	/* Forwards or no move */
	} else {
		bump_ring_forwards (store, idx, (store->last + 1) % store->total);
		memcpy (records + idx, rec, sizeof (sid_nonce_t));
		store->last = (store->last + 1) % store->total;
	}
}

int
sid_storage_check_nonce (sid_storage_t *store, const char *server, const char *nonce)
{
	sid_nonce_t *records;
	sid_nonce_t rec;
	size_t idx, lower, upper, mid;
	int res;

	assert (store);
	assert (nonce);
	assert (store->records);
	assert (store->last < store->total);

	nonce_put (rec, nonce);
	records = store->records;


	/* Best case scenario, new nonce is higher than our latest one */
	res = nonce_compare (rec, records[store->last]);

	/* Was the last nonce */
	if (res == 0) {
		return 1;

	/* Newer than anything, push on top */
	} else if (res > 0) {
		store->last = (store->last + 1) % store->total;
		memcpy (records + store->last, rec, sizeof (sid_nonce_t));

	} else {

		/* Check if it's before our last one, assume expired if so */
		idx = (store->last + 1) % store->total;
		res = nonce_compare (rec, records[idx]);
		if (res < 0) {
			return 1;

		/* Do a binary search for the item */
		} else {
			lower = 0;
			if (store->count < store->total)
				lower = store->total - store->count;
			upper = store->total;
			while (lower < upper) {
				mid = lower + ((upper - lower) / 2);  // Note: not (low + high) / 2 !!
				idx = (store->last + mid) % store->total;
				res = nonce_compare (rec, records[idx]);
				if (res == 0)
					return 1; /* Have the nonce */
				else if (res > 0)
					lower = mid + 1;
				else
					upper = mid;
			}

			idx = (store->last + upper) % store->total;
			insert_nonce_ring (store, rec, idx);
		}
	}

	++store->count;
	return 0; /* Didn't find nonce */
}

size_t
sid_storage_nonce_capacity (sid_storage_t *storage)
{
	assert (storage);
	return storage->total;
}