Make tests for storage, and fix problems

1 files changed, 153 insertions, 50 deletions

diff --git a/module/storage.c b/module/storage.c
index cb1085d..67863eb 100644
--- a/module/storage.c
+++ b/module/storage.c
@@ -21,12 +21,33 @@ struct sid_storage {
 
 	/* Book keeping for the records */
 	sid_nonce_t *records;
-	size_t first;
+	size_t last;
 	size_t total;
 	size_t count;
-	int wrapped;
 };
 
+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)
 {
@@ -43,6 +64,7 @@ sid_storage_store_assoc (sid_storage_t *store, const sid_assoc_t *assoc)
 	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;
@@ -99,17 +121,18 @@ 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 < sizeof (rec)) {
+	if (len < 40) {
 		memcpy (dst, nonce, len);
-		memset (dst + len, 0, sizeof (rec) - len);
+		memset (dst + len, 0, 40 - len);
 
 	/* Too long, need to compress into the record */
 	} else {
 		apr_sha1_ctx_t ctx;
 
-		assert (sizeof (sid_nonce_t) == APR_SHA1_DIGESTSIZE + 20);
-		assert (len > 20);
+		assert (APR_SHA1_DIGESTSIZE == 20);
 
 		/* The date prefix we just copy in */
 		memcpy (dst, nonce, 20);
@@ -122,39 +145,94 @@ nonce_put (sid_nonce_t rec, const char *nonce)
 }
 
 static void
-insert_nonce_record (sid_storage_t *store, sid_nonce_t rec, size_t at)
+bump_ring_forwards (sid_storage_t *store, size_t beg, size_t end)
 {
-	sid_nonce_t *records = store->records;
+	sid_nonce_t *records;
 
-	assert (store->total > 2);
-	assert (at < store->total);
-	assert (at != store->first);
+	assert (store);
+	assert (end <= store->total);
 
-	/* Insertion right after latest, either ancient, more likely top */
-	if (at == store->first + 1 % store->total) {
-		/* We can just copy in at this point */
+	if (beg == end)
+		return;
 
-	/* Our ring has empty space in it, so always push forwards, but only until first */
-	} else if (!store->wrapped) {
-		memmove (records + at + 1, records + at, sizeof (rec) * (store->first - at));
-		store->first += 1;
+	records = store->records;
+	assert (beg < store->total);
 
-	/* Move data backwards to make space */
-	} else if (store->first < at) {
-		memmove (records + store->first + 2, records + store->first + 1,
-		         sizeof (rec) * (at - store->first));
+	/* Simple memmove forward? */
+	if (end < store->total && beg < end) {
+		memmove (store->records + beg + 1, store->records + beg,
+		         (end - beg) * sizeof (sid_nonce_t));
 
-	/* Move data forwards to make space simply */
+	/* We wrap, far more complex */
 	} else {
-		memmove (records + at + 1, records + at, sizeof (rec) * (store->first - at - 1));
+		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));
 	}
+}
 
-	memcpy (records[at], rec, sizeof (rec));
-	++store->count;
+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));
 
-	/* Track whether we have a full ring or not. */
-	if (!store->wrapped && store->count > store->total)
-		store->wrapped = 1;
+	/* 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
@@ -162,45 +240,70 @@ sid_storage_check_nonce (sid_storage_t *store, const char *server, const char *n
 {
 	sid_nonce_t *records;
 	sid_nonce_t rec;
-	size_t at, lower, upper, mid;
+	size_t idx, lower, upper, mid;
 	int res;
 
 	assert (store);
 	assert (nonce);
 	assert (store->records);
-	assert (store->first < store->total);
+	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->first]);
+	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) {
-		at = (store->first + 1) % store->total;
-		insert_nonce_record (store, rec, at);
-		store->first = at;
-		return 0;
-	}
+	} else if (res > 0) {
+		store->last = (store->last + 1) % store->total;
+		memcpy (records + store->last, rec, sizeof (sid_nonce_t));
+
+	} else {
 
-	/* Do a binary search for the item */
-	for (lower = 0, upper = store->total; lower < upper; ) {
-		mid = lower + ((upper - lower) / 2);  // Note: not (low + high) / 2 !!
-		at = at + store->first % store->total;
-		res = nonce_compare (rec, records[at]);
-		if (res == 0)
-			return 1; /* Have the nonce */
-		else if (res > 0)
-			lower = mid + 1;
-		else
-			upper = mid;
+		/* 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);
+		}
 	}
 
-	insert_nonce_record (store, rec, at);
+	++store->count;
 	return 0; /* Didn't find nonce */
 }
+
+size_t
+sid_storage_nonce_capacity (sid_storage_t *storage)
+{
+	assert (storage);
+	return storage->total;
+}
+
+