cache.c

Go to the documentation of this file.

 
#include "common/infix_internals.h"
#include <stdlib.h>
#include <string.h>
 
#define CACHE_BUCKETS 1021
 
#define CACHE_MAX_ENTRIES INFIX_CACHE_MAX_ENTRIES
 
typedef struct _cache_entry_t {
    infix_forward_t * trampoline;     
    struct _cache_entry_t * next;     
    struct _cache_entry_t * lru_prev; 
    struct _cache_entry_t * lru_next; 
} _cache_entry_t;
 
static _cache_entry_t * g_trampoline_cache[CACHE_BUCKETS];
static _cache_entry_t * g_cache_lru_head;
static _cache_entry_t * g_cache_lru_tail;
static size_t g_cache_count = 0;
static infix_mutex_t g_cache_mutex = INFIX_MUTEX_INITIALIZER;
 
static void _cache_lru_unlink(_cache_entry_t * entry) {
    if (entry->lru_prev)
        entry->lru_prev->lru_next = entry->lru_next;
    else
        g_cache_lru_head = entry->lru_next;
    if (entry->lru_next)
        entry->lru_next->lru_prev = entry->lru_prev;
    else
        g_cache_lru_tail = entry->lru_prev;
    entry->lru_prev = nullptr;
    entry->lru_next = nullptr;
}
 
static void _cache_lru_push_front(_cache_entry_t * entry) {
    entry->lru_prev = nullptr;
    entry->lru_next = g_cache_lru_head;
    if (g_cache_lru_head)
        g_cache_lru_head->lru_prev = entry;
    g_cache_lru_head = entry;
    if (g_cache_lru_tail == nullptr)
        g_cache_lru_tail = entry;
}
 
static uint64_t _cache_hash(const char * sig, void * target_fn, bool is_safe) {
    uint64_t h = 5381;
    int c;
    while ((c = *sig++))
        h = ((h << 5) + h) + c;
    h ^= (uint64_t)(uintptr_t)target_fn;
    if (is_safe)
        h ^= 0x123456789ABCDEF0ULL;
    return h;
}
 
infix_forward_t * _infix_cache_lookup(const char * signature, void * target_fn, bool is_safe) {
    uint64_t h = _cache_hash(signature, target_fn, is_safe);
    size_t index = h % CACHE_BUCKETS;
 
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    for (_cache_entry_t * entry = g_trampoline_cache[index]; entry; entry = entry->next) {
        if (entry->trampoline->target_fn == target_fn && entry->trampoline->is_safe == is_safe &&
            strcmp(entry->trampoline->signature, signature) == 0) {
            // Cache hit: promote the entry to the MRU end of the LRU list.
            _cache_lru_unlink(entry);
            _cache_lru_push_front(entry);
            entry->trampoline->ref_count++;
            INFIX_MUTEX_UNLOCK(&g_cache_mutex);
            return entry->trampoline;
        }
    }
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
    return NULL;
}
 
static bool _cache_remove_no_lock(infix_forward_t * trampoline);
 
void _infix_cache_insert(infix_forward_t * trampoline) {
    uint64_t h = _cache_hash(trampoline->signature, trampoline->target_fn, trampoline->is_safe);
    size_t index = h % CACHE_BUCKETS;
 
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    // Double check it's not already there
    for (_cache_entry_t * entry = g_trampoline_cache[index]; entry; entry = entry->next) {
        if (entry->trampoline->target_fn == trampoline->target_fn &&
            entry->trampoline->is_safe == trampoline->is_safe &&
            strcmp(entry->trampoline->signature, trampoline->signature) == 0) {
            INFIX_MUTEX_UNLOCK(&g_cache_mutex);
            return;
        }
    }
 
    _cache_entry_t * entry = infix_malloc(sizeof(_cache_entry_t));
    if (!entry) {
        INFIX_MUTEX_UNLOCK(&g_cache_mutex);
        return;
    }
 
    entry->trampoline = trampoline;
    trampoline->ref_count++;  // Cache reference
    entry->next = g_trampoline_cache[index];
    entry->lru_prev = nullptr;
    entry->lru_next = nullptr;
    g_trampoline_cache[index] = entry;
    _cache_lru_push_front(entry);
    g_cache_count++;
 
    // Evict least-recently-used entries until the cache is back within its bound.
    while (g_cache_count > CACHE_MAX_ENTRIES && g_cache_lru_tail) {
        infix_forward_t * victim = g_cache_lru_tail->trampoline;
        // The victim is guaranteed to be in the hash table; if not, bail out to
        // avoid spinning on an inconsistent LRU list.
        if (!_cache_remove_no_lock(victim))
            break;
        if (victim->ref_count == 0)
            _infix_forward_destroy_internal(victim);
    }
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
}
 
void _infix_cache_clear(void) {
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    for (size_t i = 0; i < CACHE_BUCKETS; ++i) {
        _cache_entry_t * entry = g_trampoline_cache[i];
        while (entry) {
            _cache_entry_t * next = entry->next;
            if (--entry->trampoline->ref_count == 0)
                _infix_forward_destroy_internal(entry->trampoline);
            infix_free(entry);
            entry = next;
        }
        g_trampoline_cache[i] = nullptr;
    }
    g_cache_lru_head = nullptr;
    g_cache_lru_tail = nullptr;
    g_cache_count = 0;
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
}
 
size_t _infix_cache_count(void) {
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    size_t count = g_cache_count;
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
    return count;
}
 
static bool _cache_remove_no_lock(infix_forward_t * trampoline) {
    if (!trampoline->signature)
        return false;
    uint64_t h = _cache_hash(trampoline->signature, trampoline->target_fn, trampoline->is_safe);
    size_t index = h % CACHE_BUCKETS;
 
    _cache_entry_t ** p = &g_trampoline_cache[index];
    while (*p) {
        if ((*p)->trampoline == trampoline) {
            _cache_entry_t * to_free = *p;
            *p = to_free->next;
            _cache_lru_unlink(to_free);
            g_cache_count--;
            infix_free(to_free);
            trampoline->ref_count--;  // Decrement since cache no longer holds it
            return true;
        }
        p = &((*p)->next);
    }
    return false;
}
 
bool _infix_cache_remove(infix_forward_t * trampoline) {
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    bool result = _cache_remove_no_lock(trampoline);
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
    return result;
}
 
void _infix_cache_release(infix_forward_t * trampoline) {
    if (!trampoline)
        return;
 
    INFIX_MUTEX_LOCK(&g_cache_mutex);
    if (--trampoline->ref_count > 0) {
        INFIX_MUTEX_UNLOCK(&g_cache_mutex);
        return;
    }
 
    // Reference count is 0. Remove from cache and destroy.
    _cache_remove_no_lock(trampoline);
    INFIX_MUTEX_UNLOCK(&g_cache_mutex);
 
    _infix_forward_destroy_internal(trampoline);
}