How to Contribute New Eviction Algorithms to libCacheSim: A Developer's Guide

To contribute a new eviction algorithm to libCacheSim, implement the cache_t interface callbacks in a C module under libCacheSim/cache/eviction/, register the source file in libCacheSim/cache/CMakeLists.txt, and validate your implementation using the test harness in test/test_evictionAlgo.c.

libCacheSim is a high-performance cache simulation framework that treats eviction policies as pluggable C modules. Contributing a new algorithm requires conforming to the generic cache_t interface defined in include/libCacheSim/cache.h and integrating your code into the CMake-based build system. This guide provides the complete technical workflow using the existing codebase as reference.

Understand the libCacheSim Architecture

The Core cache_t Interface

All eviction algorithms in libCacheSim implement the cache_t structure defined in include/libCacheSim/cache.h. This structure contains function pointers that your algorithm must populate:

struct cache {
    cache_init_func_ptr    cache_init;
    cache_free_func_ptr    cache_free;
    cache_get_func_ptr     get;
    cache_find_func_ptr    find;
    cache_can_insert_func_ptr can_insert;
    cache_insert_func_ptr  insert;
    cache_evict_func_ptr   evict;
    cache_remove_func_ptr  remove;
    cache_to_evict_func_ptr to_evict;
    cache_get_occupied_byte_func_ptr get_occupied_byte;
    cache_get_n_obj_func_ptr get_n_obj;
    void *eviction_params;   // Algorithm-specific state
};

Your implementation must maintain its metadata within the eviction_params field and handle all callback invocations according to the interface contract. The framework uses these callbacks to manage cache objects while your algorithm controls the eviction order.

Algorithm Headers and Prototypes

Public prototypes for all eviction algorithms reside in include/libCacheSim/evictionAlgo.h. When adding a new policy, you will extend this file with your initialization function (e.g., MyAlgo_init) to make it discoverable by the simulator and external applications.

Step-by-Step Implementation Guide

Step 1: Create Your Algorithm Source File

Create a new C file under libCacheSim/cache/eviction/ (e.g., MyAlgo.c). The following boilerplate, based on the SFIFO.c reference implementation, provides the complete skeleton:

/* MyAlgo.c – sample eviction algorithm for libCacheSim */

#include "libCacheSim/evictionAlgo.h"
#include "dataStructure/hashtable/hashtable.h"

#ifdef __cplusplus
extern "C" {
#endif

/* Parameter struct for tunable options and runtime state */
typedef struct {
    double   my_factor;
    uint64_t max_size;
    cache_obj_t **list_head;
    cache_obj_t **list_tail;
    int64_t  n_objs;
    int64_t  n_bytes;
} MyAlgo_params_t;

/* Forward declarations */
static void   MyAlgo_free(cache_t *cache);
static bool   MyAlgo_get(cache_t *cache, const request_t *req);
static cache_obj_t *MyAlgo_find(cache_t *cache, const request_t *req, bool update_cache);
static cache_obj_t *MyAlgo_insert(cache_t *cache, const request_t *req);
static void   MyAlgo_evict(cache_t *cache, const request_t *req);
static bool   MyAlgo_remove(cache_t *cache, obj_id_t obj_id);
static inline int64_t MyAlgo_get_occupied_byte(const cache_t *cache);
static inline int64_t MyAlgo_get_n_obj(const cache_t *cache);
static inline bool   MyAlgo_can_insert(cache_t *cache, const request_t *req);
static void   MyAlgo_parse_params(cache_t *cache, const char *cache_specific_params);

/* Public init function */
cache_t *MyAlgo_init(const common_cache_params_t ccache_params,
                     const char *cache_specific_params)
{
    cache_t *cache = cache_struct_init("MyAlgo", ccache_params, cache_specific_params);
    cache->cache_init        = MyAlgo_init;
    cache->cache_free        = MyAlgo_free;
    cache->get               = MyAlgo_get;
    cache->find              = MyAlgo_find;
    cache->insert            = MyAlgo_insert;
    cache->evict             = MyAlgo_evict;
    cache->remove            = MyAlgo_remove;
    cache->to_evict          = NULL;
    cache->get_occupied_byte = MyAlgo_get_occupied_byte;
    cache->get_n_obj         = MyAlgo_get_n_obj;
    cache->can_insert        = MyAlgo_can_insert;
    cache->obj_md_size       = 0;

    /* Allocate algorithm-specific state */
    cache->eviction_params = malloc(sizeof(MyAlgo_params_t));
    memset(cache->eviction_params, 0, sizeof(MyAlgo_params_t));
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    p->my_factor = 1.0;

    /* Parse parameters like "my-factor=0.8,max-size=268435456" */
    if (cache_specific_params != NULL)
        MyAlgo_parse_params(cache, cache_specific_params);

    /* Initialize data structures */
    p->list_head = calloc(1, sizeof(cache_obj_t *));
    p->list_tail = calloc(1, sizeof(cache_obj_t *));
    p->max_size  = ccache_params.cache_size;

    return cache;
}

/* Free all allocated resources */
static void MyAlgo_free(cache_t *cache)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    free(p->list_head);
    free(p->list_tail);
    free(cache->eviction_params);
    cache_struct_free(cache);
}

/* Process a cache request */
static bool MyAlgo_get(cache_t *cache, const request_t *req)
{
    return cache_get_base(cache, req);
}

/* Locate an object and optionally update metadata */
static cache_obj_t *MyAlgo_find(cache_t *cache, const request_t *req, bool update_cache)
{
    cache_obj_t *obj = hashtable_find(cache->hashtable, req);
    if (!obj || !update_cache) return obj;
    /* Insert promotion logic here */
    return obj;
}

/* Insert a new object into the cache */
static cache_obj_t *MyAlgo_insert(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = cache_insert_base(cache, req);
    prepend_obj_to_head(&(p->list_head[0]), &(p->list_tail[0]), obj);
    p->n_objs++;
    p->n_bytes += obj->obj_size + cache->obj_md_size;
    return obj;
}

/* Evict an object when space is needed */
static void MyAlgo_evict(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = p->list_tail[0];
    DEBUG_ASSERT(obj != NULL);
    p->n_objs--;
    p->n_bytes -= obj->obj_size + cache->obj_md_size;
    remove_obj_from_list(&(p->list_head[0]), &(p->list_tail[0]), obj);
    cache_evict_base(cache, obj, true);
}

/* Remove a specific object by ID */
static bool MyAlgo_remove(cache_t *cache, obj_id_t obj_id)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    cache_obj_t *obj = hashtable_find_obj_id(cache->hashtable, obj_id);
    if (!obj) return false;
    cache->occupied_byte -= obj->obj_size + cache->obj_md_size;
    cache->n_obj--;
    remove_obj_from_list(&(p->list_head[0]), &(p->list_tail[0]), obj);
    hashtable_delete(cache->hashtable, obj);
    return true;
}

/* Statistics helpers */
static inline int64_t MyAlgo_get_occupied_byte(const cache_t *cache)
{
    return ((MyAlgo_params_t *)cache->eviction_params)->n_bytes;
}

static inline int64_t MyAlgo_get_n_obj(const cache_t *cache)
{
    return ((MyAlgo_params_t *)cache->eviction_params)->n_objs;
}

static inline bool MyAlgo_can_insert(cache_t *cache, const request_t *req)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    return (req->obj_size + cache->obj_md_size <= p->max_size) &&
           cache_can_insert_default(cache, req);
}

/* Parse comma-separated key=value parameters */
static void MyAlgo_parse_params(cache_t *cache, const char *cache_specific_params)
{
    MyAlgo_params_t *p = (MyAlgo_params_t *)cache->eviction_params;
    char *tmp = strdup(cache_specific_params);
    char *orig = tmp;
    while (tmp && *tmp) {
        char *key   = strsep(&tmp, "=");
        char *value = strsep(&tmp, ",");
        while (tmp && *tmp == ' ') ++tmp;

        if (strcasecmp(key, "my-factor") == 0) {
            p->my_factor = strtod(value, NULL);
        } else if (strcasecmp(key, "max-size") == 0) {
            p->max_size = strtoull(value, NULL, 0);
        } else {
            ERROR("%s does not have parameter %s\n", cache->cache_name, key);
            exit(1);
        }
    }
    free(orig);
}

#ifdef __cplusplus
}
#endif

Key implementation patterns from the source code:

• Use helper functions: Leverage cache_get_base, cache_insert_base, cache_evict_base, and cache_struct_init to maintain consistent bookkeeping across algorithms.
• Track state internally: Store algorithm-specific data (like queue pointers or access frequencies) in your custom struct pointed to by eviction_params.
• Parameter parsing: Accept configuration via comma-separated key=value strings passed through cache_specific_params.

Step 2: Register in the Build System

Edit libCacheSim/cache/CMakeLists.txt to include your source file in the eviction_sources_c list:

set(eviction_sources_c
    # ... existing entries ...

    eviction/MyAlgo.c   # Add your algorithm here

)

CMake automatically compiles this into the cache_lib_c object library. For C++ implementations, add the file to eviction_sources_cpp instead.

Step 3: Update Public Headers

Add your initialization function prototype to include/libCacheSim/evictionAlgo.h to expose the algorithm to external callers:

cache_t *MyAlgo_init(const common_cache_params_t ccache_params,
                     const char *cache_specific_params);

Step 4: Add Test Coverage

Append a test case to test/test_evictionAlgo.c using the existing pattern:

static void test_MyAlgo(gconstpointer user_data) {
    test_cache_algorithm(user_data, &test_data_truth[0]);
}

/* In the test suite registration: */
g_test_add_data_func("/libCacheSim/cacheAlgo_MyAlgo", reader, test_MyAlgo);

This ensures continuous integration validates that your algorithm compiles, links, and produces consistent results.

Practical Usage Example

Once built and installed, instantiate your algorithm using the standard libCacheSim API:

#include "libCacheSim/cache.h"
#include "libCacheSim/evictionAlgo.h"

int main(void) {
    common_cache_params_t params = default_common_cache_params();
    params.cache_size = 256 * MiB;
    params.hashpower = 18;

    const char *algo_params = "my-factor=0.75,max-size=268435456";
    cache_t *my_cache = MyAlgo_init(params, algo_params);
    
    if (!my_cache) {
        fprintf(stderr, "Failed to create MyAlgo cache\n");
        return 1;
    }

    request_t req = {.obj_id = 42, .obj_size = 4096, .obj_time = 0};
    bool hit = my_cache->get(my_cache, &req);
    printf("Cache hit: %s\n", hit ? "yes" : "no");

    my_cache->cache_free(my_cache);
    return 0;
}

Compile using:

gcc -Wall -I/usr/local/include -o demo demo.c -lCacheSim -ldl -lpthread -lm

Summary

• Implement the cache_t interface callbacks in a new C file under libCacheSim/cache/eviction/.
• Store algorithm-specific state in a custom struct assigned to eviction_params.
• Parse configuration via cache_specific_params using comma-separated key=value syntax.
• Register the source file in libCacheSim/cache/CMakeLists.txt under eviction_sources_c.
• Declare the init function in include/libCacheSim/evictionAlgo.h for public API exposure.
• Add test cases to test/test_evictionAlgo.c to ensure CI validation.
• Reference existing implementations like SFIFO.c for production-ready patterns regarding parameter parsing and list management.

Frequently Asked Questions

What is the minimum set of callbacks I must implement to contribute a new eviction algorithm?

You must implement cache_init, cache_free, get, find, insert, evict, and remove. Optional callbacks include to_evict (for peeking at the next eviction victim without removing it), get_occupied_byte, get_n_obj, and can_insert. The get callback typically delegates to cache_get_base, while insert and evict require your algorithm-specific logic for managing the replacement policy.

How do I make my algorithm configurable via command-line parameters?

Parse the cache_specific_params string in your *_init function using strsep to split comma-separated key=value pairs. Store parsed values in your algorithm's parameter struct (e.g., MyAlgo_params_t). Follow the pattern in SFIFO_parse_params from libCacheSim/cache/eviction/SFIFO.c, which handles type conversion and error reporting for unknown keys.

Can I implement an eviction algorithm in C++ instead of C?

Yes. Place C++ source files in libCacheSim/cache/eviction/ and add them to eviction_sources_cpp in libCacheSim/cache/CMakeLists.txt. Wrap C-compatible function declarations in extern "C" blocks to ensure the init function is linkable from C code. The cache_t interface uses C function pointers, so your methods must conform to C calling conventions while internally using C++ features.

Where should I add tests for my new eviction algorithm?

Add test functions to test/test_evictionAlgo.c following the glib testing framework patterns used throughout the repository. Use g_test_add_data_func to register your test with a unique path like /libCacheSim/cacheAlgo_MyAlgo. Provide a ground-truth dataset or at minimum verify that your algorithm initializes without errors and processes a sequence of requests without crashing.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}