LRU Cache

lru-cache.c

/* LRU cache
 * gcc -Wall cache.c -lpthread && ./a.out 
 */
#include <pthread.h>

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

struct cache_entry {
    struct cache_entry *hash;
    struct cache_entry *next;
    struct cache_entry *prev;
    unsigned long key;
    unsigned int refs;
};

struct cache {
    struct cache_entry **table;
    struct cache_entry *lru;

    pthread_spinlock_t lock;
    unsigned int size;
    unsigned int used;

    unsigned long hits;
    unsigned long misses;
    unsigned long evictions;
    unsigned long collisions;
    unsigned long starving;
};

#define __cache_lock_init(cache)      pthread_spin_init(&(cache->lock), 0);
#define __cache_lock_destroy(cache)   pthread_spin_destroy(&(cache->lock));
#define __cache_try_lock(cache)       pthread_spin_trylock(&(cache->lock))
#define __cache_lock(cache)           pthread_spin_lock(&(cache->lock))
#define __cache_unlock(cache)         pthread_spin_unlock(&(cache->lock))

#if 0
#define ASSERT(cond)                                                        \
    if (!(cond)) {fprintf(stderr, "ASSERT %d: %s\n", __LINE__, #cond); exit(1);}
#else
    #define ASSERT(cond)
#endif

static void __cache_entry_unlink (struct cache *cache, struct cache_entry *entry) {
    struct cache_entry *enext__ = entry->next;

    if (cache->lru == entry && enext__ == entry) {
        cache->lru = NULL;
    } else {
        struct cache_entry *eprev__ = entry->prev;
        enext__->prev = eprev__;
        eprev__->next = enext__;

        if (cache->lru == entry)
            cache->lru = enext__;
    }

    entry->next = NULL;
    entry->prev = NULL;
}

static unsigned int __cache_entry_hash (struct cache *cache, unsigned long key) {
    key = ~key + (key << 15); // key = (key << 15) - key - 1;
    key = key ^ (key >> 12);
    key = key + (key << 2);
    key = key ^ (key >> 4);
    key = (key + (key << 3)) + (key << 11);
    key = key ^ (key >> 16);
    return(key & (cache->size - 1));
}

struct cache_entry *__cache_entry_alloc (struct cache *cache, unsigned long key) {
    struct cache_entry *entry;

    if ((entry = (struct cache_entry *) malloc(sizeof(struct cache_entry))) == NULL)
        return(NULL);

    entry->next = NULL;
    entry->prev = NULL;
    entry->key = key;
    entry->refs = 1;
    return(entry);
}

int cache_alloc (struct cache *cache, unsigned int size) {
    if ((cache->table = (struct cache_entry **) malloc(size * sizeof(struct cache_entry *))) != NULL) {
        memset(cache->table, 0, size * sizeof(struct cache_entry *));
        cache->lru = NULL;

        __cache_lock_init(cache);
        cache->size = size;
        cache->used = 0;

        cache->hits = 0;
        cache->misses = 0;
        cache->evictions = 0;
        cache->collisions = 0;
        cache->starving = 0;
    }
    return(0);
}

void cache_clear (struct cache *cache) {
    struct cache_entry *entry;
    struct cache_entry *next;
    unsigned int i;

    for (i = 0; i < cache->size; ++i) {        
        for (entry = cache->table[i]; entry != NULL; entry = next) {
            ASSERT(entry != NULL);
            next = entry->hash;
            free(entry);
        }
        cache->table[i] = NULL;
    }

    cache->lru = NULL;
    cache->used = 0;
}


void cache_free (struct cache *cache) {
    cache_clear(cache);
    free(cache->table);
    __cache_lock_destroy(cache);
}

struct cache_entry *cache_try_get (struct cache *cache, unsigned long key) {
    struct cache_entry *entry;
    unsigned int index;

    /* Finf the key */
    index = __cache_entry_hash(cache, key);
    entry = cache->table[index];
    while (entry != NULL && entry->key != key)
        entry = entry->hash;

    /* Key found */
    if (entry != NULL) {
        __cache_lock(cache);

        if (entry->key == key) {
            entry->refs++;

            if (entry->next != NULL) {
                ASSERT(entry->next != NULL);
                ASSERT(entry->prev != NULL);
                __cache_entry_unlink(cache, entry);
            }

            ASSERT(entry->prev == NULL);
            ASSERT(entry->next == NULL);

            cache->hits++;
        }

        __cache_unlock(cache);
        if (entry->key == key)
            return(entry);
    }

    /* Stop if someone is writing */
    if (__cache_try_lock(cache)) {
        __sync_add_and_fetch(&(cache->starving), 1);
        return(NULL);
    }

    if (cache->used < cache->size) {
        /* Add an entry */
        if ((entry = __cache_entry_alloc(cache, key)) != NULL) {
            cache->used++;
            cache->misses++;

            /* push into hash table */
            if ((entry->hash = cache->table[index]) != NULL)
                cache->collisions++;
            cache->table[index] = entry;
        }
    } else if (cache->lru != NULL) {
        struct cache_entry *p;
        unsigned int pindex;

        /* Reclaim an entry */
        entry = cache->lru->prev;
        ASSERT(entry->refs == 0);

        /* Remove from hash table */
        pindex = __cache_entry_hash(cache, entry->key);
        if ((p = cache->table[pindex]) != entry) {
            for (p = cache->table[pindex]; p->hash != entry;)
                p = p->hash;
            p->hash = entry->hash;
        } else {
            cache->table[pindex] = entry->hash;
        }

        cache->misses++;
        cache->evictions++;
        entry->key = key;
        entry->refs = 1;

        /* push into hash table */
        if ((entry->hash = cache->table[index]) != NULL)
            cache->collisions++;
        cache->table[index] = entry;

        /* Unlink from LRU */
        __cache_entry_unlink(cache, entry);
    }

    __cache_unlock(cache);
    return(entry);
}

void cache_put (struct cache *cache, struct cache_entry *entry) {
    if (__sync_sub_and_fetch(&(entry->refs), 1)) 
        return;

    /* Push in the LRU */
    __cache_lock(cache);
    if (entry->refs == 0 && entry->next == NULL) {
        struct cache_entry *head;
        if ((head = cache->lru) != NULL) {
            entry->prev = head->prev; 
            entry->next = head;           
            head->prev = entry;
            entry->prev->next = entry;
        } else {
            entry->prev = entry;
            entry->next = entry;
        }
        cache->lru = entry;
    }
    __cache_unlock(cache);
}

/* ============================================================================
 *  Demo
 */
#include <sys/time.h>
#include <stdint.h>

#define __MSEC_PER_SEC         ((uint64_t)1000U)

#define __TEST_RAND_REQUESTS   (1)
#define __TEST_CACHE_SIZE      (8192)
#define __TEST_NOPS            (1ULL << 19)
#define __TEST_NTHREADS        (8)

static void __print_info (const struct cache *cache) {
    printf("Cache: %u used %lu hits, %lu misses, evictions %lu, collisions %lu, %lu starving\n",
            cache->used, cache->hits, cache->misses, cache->evictions, cache->collisions, cache->starving);
}

static void __print_stats (struct cache *cache) {
    struct cache_entry *p;

    printf("Cache: %u used %lu hits, %lu misses\n",
            cache->used, cache->hits, cache->misses);
    if (cache->lru != NULL) {
        printf(" - F-LRU: ");
        for (p = cache->lru; p->next != cache->lru; p = p->next)
            printf("%lu -> ", p->key);
        printf("%lu\n", p->key);
        printf(" - R-LRU: ");
        for (p = cache->lru->prev; p != cache->lru; p = p->prev)
            printf("%lu -> ", p->key);
        printf("%lu\n", p->key);
    } 
}

static unsigned long __rand (unsigned long *seed) {
    unsigned long next = *seed;
    unsigned long result;

    next *= 1103515245;
    next += 12345;
    result = (next >> 16) & 2047;

    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (next >> 16) & 1023;

    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (next >> 16) & 1023;

    *seed = next;
    return(result);
}

void *__test_func (void *args) {
    unsigned long seed = (unsigned long)pthread_self();
    struct cache *cache = (struct cache *)args;
    struct cache_entry *entry;
    unsigned int blocknr;
    unsigned long count;

    count = __TEST_NOPS;
    while (count--) {
#if __TEST_RAND_REQUESTS
        blocknr = __rand(&seed);
#else
        blocknr = count;
#endif
        blocknr &= (__TEST_CACHE_SIZE << 4) - 1;
        while ((entry = cache_try_get(cache, blocknr)) == NULL);
        cache_put(cache, entry);
    }

    return(NULL);
}

uint64_t z_time_millis (void) {
    struct timeval now;
    gettimeofday(&now, NULL);
    return(now.tv_sec * __MSEC_PER_SEC + (now.tv_usec / __MSEC_PER_SEC));
}

static void __test_simple (struct cache *cache) {
    struct cache_entry *entry;

    entry = cache_try_get(cache, 1);
    cache_put(cache, entry);
    __print_stats(cache);

    entry = cache_try_get(cache, 2);
    cache_put(cache, entry);
    __print_stats(cache);

    entry = cache_try_get(cache, 3);
    cache_put(cache, entry);
    __print_stats(cache);

    entry = cache_try_get(cache, 1);
    cache_put(cache, entry);
    __print_stats(cache);

    entry = cache_try_get(cache, 5);
    cache_put(cache, entry);
    __print_stats(cache);

    cache_clear(cache);
    __print_stats(cache);
}

static void __test_threaded (struct cache *cache) {
    pthread_t threads[__TEST_NTHREADS];
    uint64_t st, et;
    int i;

    st = z_time_millis();
    for (i = 0; i < __TEST_NTHREADS; ++i)
        pthread_create(&(threads[i]), NULL, __test_func, cache);

    for (i = 0; i < __TEST_NTHREADS; ++i)
        pthread_join(threads[i], NULL);
    et = z_time_millis();

    float sec = ((float)(et - st)) / (float)__MSEC_PER_SEC;
    float opsec = (__TEST_NOPS * __TEST_NTHREADS) / sec;
    printf("\nThreaded test: %llu ops/thread, %u threads\n", __TEST_NOPS, __TEST_NTHREADS);
    printf("Total %.3fsec %.2fKop/sec (%.2fMop/sec)\n", 
           sec, opsec / 1000.0f, opsec / 1000000.0f);
    __print_info(cache);
}

int main (int argc, char **argv) {
    struct cache cache;

    cache_alloc(&cache, __TEST_CACHE_SIZE);
    __test_simple(&cache);
    __test_threaded(&cache);
    cache_clear(&cache);

    return(0);
}