From 7b14b2f01fd0218c0bbe0a5c4071fff190c91ce1 Mon Sep 17 00:00:00 2001 From: Ziv Scully Date: Wed, 11 Nov 2015 20:01:48 -0500 Subject: Rewrite LRU cache. Now uses one big hash table and is less buggy. --- include/urweb/types_cpp.h | 29 +++--- include/urweb/urweb_cpp.h | 8 +- src/c/urweb.c | 240 ++++++++++++++++++++++++---------------------- src/lru_cache.sml | 15 +-- 4 files changed, 147 insertions(+), 145 deletions(-) diff --git a/include/urweb/types_cpp.h b/include/urweb/types_cpp.h index 84423105..4847a3fd 100644 --- a/include/urweb/types_cpp.h +++ b/include/urweb/types_cpp.h @@ -123,31 +123,24 @@ typedef struct { #include "uthash.h" -typedef struct uw_Sqlcache_CacheValue { +typedef struct uw_Sqlcache_Value { char *result; char *output; -} uw_Sqlcache_CacheValue; + unsigned long timeValid; +} uw_Sqlcache_Value; -typedef struct uw_Sqlcache_CacheEntry { +typedef struct uw_Sqlcache_Entry { char *key; - void *value; - time_t timeValid; - struct uw_Sqlcache_CacheEntry *prev; - struct uw_Sqlcache_CacheEntry *next; + uw_Sqlcache_Value *value; + unsigned long timeInvalid; UT_hash_handle hh; -} uw_Sqlcache_CacheEntry; - -typedef struct uw_Sqlcache_CacheList { - uw_Sqlcache_CacheEntry *first; - uw_Sqlcache_CacheEntry *last; - int size; -} uw_Sqlcache_CacheList; +} uw_Sqlcache_Entry; typedef struct uw_Sqlcache_Cache { - uw_Sqlcache_CacheEntry *table; - time_t timeInvalid; - uw_Sqlcache_CacheList *lru; - int height; + struct uw_Sqlcache_Entry *table; + unsigned long timeInvalid; + unsigned long timeNow; + UT_hash_handle hh; } uw_Sqlcache_Cache; #endif diff --git a/include/urweb/urweb_cpp.h b/include/urweb/urweb_cpp.h index ab2a91c1..52e54372 100644 --- a/include/urweb/urweb_cpp.h +++ b/include/urweb/urweb_cpp.h @@ -405,10 +405,8 @@ void uw_Basis_writec(struct uw_context *, char); // Sqlcache. -#include "uthash.h" - -uw_Sqlcache_CacheValue *uw_Sqlcache_check(uw_Sqlcache_Cache *, char **); -uw_Sqlcache_CacheValue *uw_Sqlcache_store(uw_Sqlcache_Cache *, char **, uw_Sqlcache_CacheValue *); -uw_Sqlcache_CacheValue *uw_Sqlcache_flush(uw_Sqlcache_Cache *, char **); +uw_Sqlcache_Value *uw_Sqlcache_check(uw_Sqlcache_Cache *, char **, int); +void *uw_Sqlcache_store(uw_Sqlcache_Cache *, char **, int, uw_Sqlcache_Value *); +void *uw_Sqlcache_flush(uw_Sqlcache_Cache *, char **, int); #endif diff --git a/src/c/urweb.c b/src/c/urweb.c index ef7eb9bb..09d04f1c 100644 --- a/src/c/urweb.c +++ b/src/c/urweb.c @@ -4532,144 +4532,154 @@ void uw_set_remoteSock(uw_context ctx, int sock) { // Sqlcache -void uw_Sqlcache_listDelete(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) { - if (list->first == entry) { - list->first = entry->next; - } - if (list->last == entry) { - list->last = entry->prev; - } - if (entry->prev) { - entry->prev->next = entry->next; - } - if (entry->next) { - entry->next->prev = entry->prev; +void uw_Sqlcache_freeValue(uw_Sqlcache_Value *value) { + if (value) { + free(value->result); + free(value->output); + free(value); } - entry->prev = NULL; - entry->next = NULL; - --(list->size); } -void uw_Sqlcache_listAdd(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) { - if (list->last) { - list->last->next = entry; - entry->prev = list->last; - list->last = entry; - } else { - list->first = entry; - list->last = entry; +void uw_Sqlcache_freeEntry(uw_Sqlcache_Entry* entry) { + if (entry) { + free(entry->key); + uw_Sqlcache_freeValue(entry->value); + free(entry); } - ++(list->size); -} - -void uw_Sqlcache_listBump(uw_Sqlcache_CacheList *list, uw_Sqlcache_CacheEntry *entry) { - uw_Sqlcache_listDelete(list, entry); - uw_Sqlcache_listAdd(list, entry); } -// TODO: deal with time properly. +// TODO: pick a number. +unsigned int uw_Sqlcache_maxSize = 1234567890; -time_t uw_Sqlcache_getTimeNow() { - return time(NULL); +void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry) { + HASH_DEL(cache->table, entry); + uw_Sqlcache_freeEntry(entry); } -time_t uw_Sqlcache_timeMax(time_t x, time_t y) { - return difftime(x, y) > 0 ? x : y; +uw_Sqlcache_Entry *uw_Sqlcache_find(uw_Sqlcache_Cache *cache, char *key, size_t len, int bump) { + uw_Sqlcache_Entry *entry = NULL; + HASH_FIND(hh, cache->table, key, len, entry); + if (entry && bump) { + // Bump for LRU purposes. + HASH_DEL(cache->table, entry); + // Important that we use [entry->key], because [key] might be ephemeral. + HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry); + } + return entry; } -void uw_Sqlcache_free(uw_Sqlcache_CacheValue *value) { - if (value) { - free(value->result); - free(value->output); - free(value); +void uw_Sqlcache_add(uw_Sqlcache_Cache *cache, uw_Sqlcache_Entry *entry, size_t len) { + HASH_ADD_KEYPTR(hh, cache->table, entry->key, len, entry); + if (HASH_COUNT(cache->table) > uw_Sqlcache_maxSize) { + // Deletes the first element of the cache. + uw_Sqlcache_delete(cache, cache->table); } } -void uw_Sqlcache_delete(uw_Sqlcache_Cache *cache, uw_Sqlcache_CacheEntry* entry) { - //uw_Sqlcache_listUw_Sqlcache_Delete(cache->lru, entry); - HASH_DELETE(hh, cache->table, entry); - uw_Sqlcache_free(entry->value); - free(entry->key); - free(entry); -} - -uw_Sqlcache_CacheValue *uw_Sqlcache_checkHelper(uw_Sqlcache_Cache *cache, char **keys, int timeInvalid) { - char *key = keys[cache->height]; - uw_Sqlcache_CacheEntry *entry; - HASH_FIND(hh, cache->table, key, strlen(key), entry); - timeInvalid = uw_Sqlcache_timeMax(timeInvalid, cache->timeInvalid); - if (entry && difftime(entry->timeValid, timeInvalid) > 0) { - if (cache->height == 0) { - // At height 0, entry->value is the desired value. - //uw_Sqlcache_listBump(cache->lru, entry); - return entry->value; - } else { - // At height n+1, entry->value is a pointer to a cache at heignt n. - return uw_Sqlcache_checkHelper(entry->value, keys, timeInvalid); - } - } else { - return NULL; - } +unsigned long uw_Sqlcache_getTimeNow(uw_Sqlcache_Cache *cache) { + return ++cache->timeNow; } -uw_Sqlcache_CacheValue *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys) { - return uw_Sqlcache_checkHelper(cache, keys, 0); +unsigned long uw_Sqlcache_timeMax(unsigned long x, unsigned long y) { + return x > y ? x : y; } -void uw_Sqlcache_storeHelper(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value, int timeNow) { - uw_Sqlcache_CacheEntry *entry; - char *key = keys[cache->height]; - HASH_FIND(hh, cache->table, key, strlen(key), entry); - if (!entry) { - entry = malloc(sizeof(uw_Sqlcache_CacheEntry)); - entry->key = strdup(key); - entry->value = NULL; - HASH_ADD_KEYPTR(hh, cache->table, entry->key, strlen(entry->key), entry); +char uw_Sqlcache_keySep = '_'; + +char *uw_Sqlcache_allocKeyBuffer(char **keys, int numKeys) { + size_t len = 0; + while (numKeys-- > 0) { + char* k = keys[numKeys]; + if (!k) { + // Can only happen when flushihg, in which case we don't need anything past the null key. + break; + } + // Leave room for separator. + len += 1 + strlen(k); } - entry->timeValid = timeNow; - if (cache->height == 0) { - //uw_Sqlcache_listAdd(cache->lru, entry); - uw_Sqlcache_free(entry->value); - entry->value = value; - //if (cache->lru->size > MAX_SIZE) { - //uw_Sqlcache_delete(cache, cache->lru->first); - // TODO: return flushed value. - //} - } else { - if (!entry->value) { - uw_Sqlcache_Cache *newuw_Sqlcache_Cache = malloc(sizeof(uw_Sqlcache_Cache)); - newuw_Sqlcache_Cache->table = NULL; - newuw_Sqlcache_Cache->timeInvalid = timeNow; - newuw_Sqlcache_Cache->lru = cache->lru; - newuw_Sqlcache_Cache->height = cache->height - 1; - entry->value = newuw_Sqlcache_Cache; + char *buf = malloc(len+1); + // If nothing is copied into the buffer, it should look like it has length 0. + buf[0] = 0; + return buf; +} + +char *uw_Sqlcache_keyCopy(char *buf, char *key) { + *buf++ = uw_Sqlcache_keySep; + return stpcpy(buf, key); +} + +// The NUL-terminated prefix of [key] below always looks something like "_k1_k2_k3..._kn". +// TODO: strlen(key) = buf - key? + +uw_Sqlcache_Value *uw_Sqlcache_check(uw_Sqlcache_Cache *cache, char **keys, int numKeys) { + char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys); + char *buf = key; + time_t timeInvalid = cache->timeInvalid; + uw_Sqlcache_Entry *entry; + while (numKeys-- > 0) { + buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]); + size_t len = buf - key; + entry = uw_Sqlcache_find(cache, key, len, 1); + if (!entry) { + free(key); + return NULL; } - uw_Sqlcache_storeHelper(entry->value, keys, value, timeNow); + timeInvalid = uw_Sqlcache_timeMax(timeInvalid, entry->timeInvalid); } -} - -void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, uw_Sqlcache_CacheValue *value) { - uw_Sqlcache_storeHelper(cache, keys, value, uw_Sqlcache_getTimeNow()); -} - -void uw_Sqlcache_flushHelper(uw_Sqlcache_Cache *cache, char **keys, int timeNow) { - uw_Sqlcache_CacheEntry *entry; - char *key = keys[cache->height]; - if (key) { - HASH_FIND(hh, cache->table, key, strlen(key), entry); - if (entry) { - if (cache->height == 0) { - uw_Sqlcache_delete(cache, entry); + free(key); + uw_Sqlcache_Value *value = entry->value; + return value && value->timeValid > timeInvalid ? value : NULL; +} + +void uw_Sqlcache_store(uw_Sqlcache_Cache *cache, char **keys, int numKeys, uw_Sqlcache_Value *value) { + char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys); + char *buf = key; + time_t timeNow = uw_Sqlcache_getTimeNow(cache); + uw_Sqlcache_Entry *entry; + while (numKeys-- > 0) { + buf = uw_Sqlcache_keyCopy(buf, keys[numKeys]); + size_t len = buf - key; + entry = uw_Sqlcache_find(cache, key, len, 1); + if (!entry) { + entry = malloc(sizeof(uw_Sqlcache_Entry)); + entry->key = strdup(key); + entry->value = NULL; + entry->timeInvalid = 0; // ASK: is this okay? + uw_Sqlcache_add(cache, entry, len); + } + } + free(key); + uw_Sqlcache_freeValue(entry->value); + entry->value = value; + entry->value->timeValid = timeNow; +} + +void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys, int numKeys) { + char *key = uw_Sqlcache_allocKeyBuffer(keys, numKeys); + char *buf = key; + time_t timeNow = uw_Sqlcache_getTimeNow(cache); + uw_Sqlcache_Entry *entry; + while (numKeys-- > 0) { + char *k = keys[numKeys]; + if (!k) { + if (entry) { + entry->timeInvalid = timeNow; } else { - uw_Sqlcache_flushHelper(entry->value, keys, timeNow); + // Haven't found an entry yet, so the first key was null. + cache->timeInvalid = timeNow; } + free(key); + return; + } + buf = uw_Sqlcache_keyCopy(buf, k); + size_t len = buf - key; + entry = uw_Sqlcache_find(cache, key, len, 0); + if (!entry) { + free(key); + return; } - } else { - // Null key means invalidate the entire subtree. - cache->timeInvalid = timeNow; } -} - -void uw_Sqlcache_flush(uw_Sqlcache_Cache *cache, char **keys) { - uw_Sqlcache_flushHelper(cache, keys, uw_Sqlcache_getTimeNow()); + free(key); + // All the keys were non-null and the relevant entry is present, so we delete it. + uw_Sqlcache_delete(cache, entry); } diff --git a/src/lru_cache.sml b/src/lru_cache.sml index e69624d8..6fcfdc55 100644 --- a/src/lru_cache.sml +++ b/src/lru_cache.sml @@ -62,6 +62,8 @@ fun setupQuery {index, params} = val revArgs = paramRepeatRev (fn p => "p" ^ p) ", " + val numArgs = Int.toString params + in Print.box [string ("static uw_Sqlcache_Cache cacheStruct" ^ i ^ " = {"), @@ -70,9 +72,7 @@ fun setupQuery {index, params} = newline, string " .timeInvalid = 0,", newline, - string " .lru = NULL,", - newline, - string (" .height = " ^ Int.toString (params - 1) ^ "};"), + string " .timeNow = 0};", newline, string ("static uw_Sqlcache_Cache *cache" ^ i ^ " = &cacheStruct" ^ i ^ ";"), newline, @@ -83,7 +83,8 @@ fun setupQuery {index, params} = newline, string (" char *ks[] = {" ^ revArgs ^ "};"), newline, - string (" uw_Sqlcache_CacheValue *v = uw_Sqlcache_check(cache" ^ i ^ ", ks);"), + string " uw_Sqlcache_Value *v = ", + string ("uw_Sqlcache_check(cache" ^ i ^ ", ks, " ^ numArgs ^ ");"), newline, (* If the output is null, it means we had too much recursion, so it's a miss. *) string " if (v && v->output != NULL) {", @@ -113,7 +114,7 @@ fun setupQuery {index, params} = newline, string (" char *ks[] = {" ^ revArgs ^ "};"), newline, - string (" uw_Sqlcache_CacheValue *v = malloc(sizeof(uw_Sqlcache_CacheValue));"), + string (" uw_Sqlcache_Value *v = malloc(sizeof(uw_Sqlcache_Value));"), newline, string " v->result = strdup(s);", newline, @@ -121,7 +122,7 @@ fun setupQuery {index, params} = newline, string (" puts(\"SQLCACHE: stored " ^ i ^ ".\");"), newline, - string (" uw_Sqlcache_store(cache" ^ i ^ ", ks, v);"), + string (" uw_Sqlcache_store(cache" ^ i ^ ", ks, " ^ numArgs ^ ", v);"), newline, string " return uw_unit_v;", newline, @@ -134,7 +135,7 @@ fun setupQuery {index, params} = newline, string (" char *ks[] = {" ^ revArgs ^ "};"), newline, - string (" uw_Sqlcache_flush(cache" ^ i ^ ", ks);"), + string (" uw_Sqlcache_flush(cache" ^ i ^ ", ks, " ^ numArgs ^ ");"), newline, string " return uw_unit_v;", newline, -- cgit v1.2.3