summaryrefslogtreecommitdiff
path: root/module/storage.c
diff options
context:
space:
mode:
Diffstat (limited to 'module/storage.c')
-rw-r--r--module/storage.c203
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;
+}
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-01 08:32:16 +0000