test_evictionAlgo.c

//
// Created by Juncheng Yang on 11/21/19.
//

#include "common.h"

// Constants
static const uint64_t g_req_cnt_true = 113872;
static const uint64_t g_req_byte_true = 4368040448;
static const uint64_t NUM_TEST_SIZES = 8;

// Test data structure
typedef struct {
  const char *cache_name;
  uint64_t hashpower;
  uint64_t req_cnt_true;
  uint64_t req_byte_true;
  uint64_t miss_cnt_true[8];
  uint64_t miss_byte_true[8];
} cache_test_data_t;

// Test data definitions (ordered alphabetically by algorithm name)
static const cache_test_data_t test_data_truth[] = {
    {.cache_name = "ARC",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90252, 85861, 78168, 74297, 67381, 65685, 64439, 64772},
     .miss_byte_true = {4068098560, 3821026816, 3525644800, 3296890368,
                        2868538880, 2771180032, 2699484672, 2712971264}},
    {.cache_name = "Belady",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {79256, 70724, 65481, 61594, 59645, 57599, 50873, 48974},
     .miss_byte_true = {3472532480, 2995165696, 2726689792, 2537648128,
                        2403427840, 2269212672, 2134992896, 2029769728}},
    {.cache_name = "BeladySize",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {74329, 64553, 60315, 56522, 54546, 52618, 50580, 48974},
     .miss_byte_true = {3510350848, 3046487552, 2774967808, 2537689600,
                        2403425280, 2269210112, 2135005184, 2029769728}},
    {.cache_name = "Cacheus",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90052, 82866, 77130, 77115, 69828, 68435, 67930, 66993},
     .miss_byte_true = {4068200448, 3757362176, 3439912448, 3359079424,
                        3018722816, 2928907776, 2867576832, 2834809856}},
    {.cache_name = "CAR",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90522, 83605, 78063, 75772, 67384, 65687, 64439, 64376},
     .miss_byte_true = {4084188160, 3769425920, 3525660160, 3394717696,
                        2868551168, 2771188224, 2699423232, 2696345600}},
    {.cache_name = "Clock",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93313, 89775, 83411, 81328, 74815, 72283, 71927, 64456},
     .miss_byte_true = {4213887488, 4064512000, 3762650624, 3644467200,
                        3256760832, 3091688448, 3074241024, 2697378816}},
    {.cache_name = "ClockPro",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {96390, 92614, 88911, 85894, 82276, 73203, 63728, 57544},
     .miss_byte_true = {4163599360, 3922361856, 3700721152, 3491452416,
                        3245322240, 2653708288, 2413087744, 2293678592}},
    {.cache_name = "CR_LFU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {92095, 88257, 84839, 81885, 78348, 69281, 61350, 54894},
     .miss_byte_true = {4141293056, 3900042240, 3686207488, 3481216000,
                        3238197760, 2646171648, 2408963072, 2289538048}},
    {.cache_name = "FIFO",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93403, 89386, 84387, 84025, 72498, 72228, 72182, 72140},
     .miss_byte_true = {4213112832, 4052646400, 3829170176, 3807412736,
                        3093146112, 3079525888, 3079210496, 3077547520}},
    {.cache_name = "GDSF",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {89070, 84750, 74850, 70490, 67923, 64180, 61027, 58721},
     .miss_byte_true = {4210726912, 4057058816, 3719176192, 3436855296,
                        3271648256, 3029728768, 2828456448, 2677800448}},
    {.cache_name = "Hyperbolic",
     .hashpower = 18,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {92924, 89470, 83452, 81234, 74544, 71234, 69356, 65338},
     .miss_byte_true = {4213586432, 4064826368, 3766646272, 3644941824,
                        3245021184, 3035783168, 2939981312, 2754100224}},
    {.cache_name = "LeCaR",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93374, 89067, 80230, 81526, 72159, 67712, 65206, 64541},
     .miss_byte_true = {4214303232, 4021100032, 3593971712, 3652036096,
                        3075125760, 2886052864, 2735856128, 2698478080}},
    {.cache_name = "LFU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {91699, 86720, 78578, 76707, 69945, 66221, 64445, 64376},
     .miss_byte_true = {4158632960, 3917211648, 3536227840, 3455379968,
                        3035580416, 2801699328, 2699456000, 2696345600}},
    {.cache_name = "LFUDA",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {92637, 88601, 82001, 80240, 73214, 71386, 70415, 71128},
     .miss_byte_true = {4200012288, 3993467904, 3673375232, 3579174400,
                        3164476928, 3046658048, 2998682624, 3027994112}},
    {.cache_name = "LHD",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90534, 86891, 82334, 77339, 71355, 66938, 63677, 61116},
     .miss_byte_true = {4211037696, 4059153920, 3834546176, 3596945408,
                        3326034944, 3115964416, 2951718912, 2804600832}},
    {.cache_name = "LIRS",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {89819, 79237, 73143, 70363, 68405, 64494, 58640, 53924},
     .miss_byte_true = {4060558336, 3525952512, 3199406080, 3011810816,
                        2848310272, 2580918784, 2361375744, 2288325120}},
    {.cache_name = "LRU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93374, 89783, 83572, 81722, 72494, 72104, 71972, 71704},
     .miss_byte_true = {4214303232, 4061242368, 3778040320, 3660569600,
                        3100927488, 3078128640, 3075403776, 3061662720}},
    {.cache_name = "LRU_K",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {91699, 86720, 78578, 76707, 69945, 66221, 64445, 64376},
     .miss_byte_true = {4158632960, 3917211648, 3536227840, 3455379968,
                        3035580416, 2801699328, 2699456000, 2696345600}},
    {.cache_name = "MRU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {100738, 95058, 89580, 85544, 81725, 77038, 71070, 66919},
     .miss_byte_true = {4105477120, 3784799744, 3493475840, 3280475648,
                        3069635072, 2856241152, 2673937408, 2539762688}},
    {.cache_name = "QDLP-FIFO",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {88746, 80630, 76450, 71638, 67380, 65680, 66125, 64417},
     .miss_byte_true = {4008265728, 3625704960, 3330610176, 3099731456,
                        2868538880, 2771098112, 2734977024, 2697751552}},
    {.cache_name = "Random",
     .hashpower = 12,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {92457, 88582, 84459, 80277, 76132, 72134, 68230, 64225},
     .miss_byte_true = {4170166272, 3975292416, 3757524992, 3539850752,
                        3321110016, 3113551360, 2917275648, 2725705216}},
    {.cache_name = "S3-FIFO",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90117, 80915, 75060, 72191, 69815, 65542, 60799, 56045},
     .miss_byte_true = {4058576896, 3573827584, 3244417024, 3061737984,
                        2898109952, 2628363776, 2425027072, 2327934464}},
    {.cache_name = "S3-FIFOv0",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {89307, 82387, 77041, 76791, 71300, 70343, 70455, 70355},
     .miss_byte_true = {4040718336, 3703628800, 3353047552, 3282235904,
                        3038256128, 2980646912, 2984458752, 2979649536}},
    {.cache_name = "S4-FIFO",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     // with default params S4-FIFO reduces exactly to S3-FIFO, hence
     // identical truth values to the "S3-FIFO" entry above
     .miss_cnt_true = {90117, 80915, 75060, 72191, 69815, 65542, 60799, 56045},
     .miss_byte_true = {4058576896, 3573827584, 3244417024, 3061737984,
                        2898109952, 2628363776, 2425027072, 2327934464}},
    {.cache_name = "Sieve",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {91699, 86720, 78578, 76707, 69945, 66221, 64445, 64376},
     .miss_byte_true = {4158632960, 3917211648, 3536227840, 3455379968,
                        3035580416, 2801699328, 2699456000, 2696345600}},
    {.cache_name = "SLRU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {89624, 86725, 82781, 80203, 75388, 65645, 59035, 56063},
     .miss_byte_true = {4123085312, 3915534848, 3690704896, 3493027840,
                        3174708736, 2661464064, 2507604992, 2439981056}},
    {.cache_name = "SR_LRU",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90043, 83978, 81482, 77727, 72611, 72059, 67836, 65739},
     .miss_byte_true = {4068758016, 3792818176, 3639756288, 3379609600,
                        3165339648, 3058814976, 2862775296, 2774183936}},
    {.cache_name = "Clock2QPlus",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {90600, 81357, 75287, 72430, 70057, 65671, 60864, 55864},
     .miss_byte_true = {4061047808, 3577076736, 3242227712, 3061383680,
                        2898187264, 2624986112, 2422187008, 2322797568}},
    {.cache_name = "MQ",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {92034, 86146, 84751, 82240, 75185, 71503, 68987, 67640},
     .miss_byte_true = {4149330432, 3836459008, 3791890432, 3677849600,
                        3265613824, 3044815360, 2898076160, 2863112704}},
    /* Published prefix-cache policies. Both consult per-request metadata that
     * only prefixsim supplies. Under this driver they get none, and this trace
     * carries no cost, so every object costs 1: WorkloadAware then has a single
     * workload class and AsymCache a constant recompute cost, and both reduce
     * to LRU. These rows are LRU's numbers and pin that reduction; the
     * prefix-cache behaviour itself is not tested here. */
    {.cache_name = "WorkloadAware",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93374, 89783, 83572, 81722, 72494, 72104, 71972, 71704},
     .miss_byte_true = {4214303232, 4061242368, 3778040320, 3660569600,
                        3100927488, 3078128640, 3075403776, 3061662720}},
    {.cache_name = "AsymCache",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93374, 89783, 83572, 81722, 72494, 72104, 71972, 71704},
     .miss_byte_true = {4214303232, 4061242368, 3778040320, 3660569600,
                        3100927488, 3078128640, 3075403776, 3061662720}},
#if defined(ENABLE_3L_CACHE) && ENABLE_3L_CACHE == 1
    {.cache_name = "3LCache",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {93374, 89783, 83572, 81722, 72494, 72104, 71972, 71704},
     .miss_byte_true = {4214303232, 4061242368, 3778040320, 3660569600,
                        3100927488, 3078128640, 3075403776, 3061662720}},
#endif /* ENABLE_3L_CACHE */
    {.cache_name = "Merlin",
     .hashpower = 20,
     .req_cnt_true = 113872,
     .req_byte_true = 4368040448,
     .miss_cnt_true = {89842, 79364, 74651, 71671, 69144, 64850, 60371, 56257},
     .miss_byte_true = {4047980032, 3523418112, 3219840512, 3037955072,
                        2874276864, 2597470208, 2426512896, 2333233664}},
};

static void _verify_profiler_results(const cache_stat_t *res,
                                     uint64_t num_of_sizes,
                                     uint64_t req_cnt_true,
                                     const uint64_t *miss_cnt_true,
                                     uint64_t req_byte_true,
                                     const uint64_t *miss_byte_true) {
  for (uint64_t i = 0; i < num_of_sizes; i++) {
    g_assert_cmpuint(req_cnt_true, ==, res[i].n_req);
    g_assert_cmpuint(miss_cnt_true[i], ==, res[i].n_miss);
    g_assert_cmpuint(req_byte_true, ==, res[i].n_req_byte);
    g_assert_cmpuint(miss_byte_true[i], ==, res[i].n_miss_byte);
  }
}

static void print_results(const cache_t *cache, const cache_stat_t *res) {
  printf("%s uint64_t cache_size[] = {", cache->cache_name);
  printf("%ld", (long)res[0].cache_size);
  for (uint64_t i = 1; i < CACHE_SIZE / STEP_SIZE; i++) {
    printf(", %ld", (long)res[i].cache_size);
  }
  printf("};\n");

  printf("uint64_t miss_cnt[] = {");
  printf("%ld", (long)res[0].n_miss);
  for (uint64_t i = 1; i < CACHE_SIZE / STEP_SIZE; i++) {
    printf(", %ld", (long)res[i].n_miss);
  }
  printf("};\n");

  printf("uint64_t miss_byte[] = {");
  printf("%ld", (long)res[0].n_miss_byte);
  for (uint64_t i = 1; i < CACHE_SIZE / STEP_SIZE; i++) {
    printf(", %ld", (long)res[i].n_miss_byte);
  }
  printf("};\n");
}

// Generic test function that works for all cache algorithms
static void test_cache_algorithm(gconstpointer user_data,
                                 const cache_test_data_t *test_data) {
  reader_t *reader = (reader_t *)user_data;
  common_cache_params_t cc_params = {.cache_size = CACHE_SIZE,
                                     .hashpower = test_data->hashpower,
                                     .default_ttl = DEFAULT_TTL};

  cache_t *cache =
      create_test_cache(test_data->cache_name, cc_params, reader, NULL);
  g_assert_true(cache != NULL);

  cache_stat_t *res = simulate_at_multi_sizes_with_step_size(
      reader, cache, STEP_SIZE, NULL, 0, 0, _n_cores(), false);

  print_results(cache, res);
  _verify_profiler_results(res, CACHE_SIZE / STEP_SIZE, test_data->req_cnt_true,
                           test_data->miss_cnt_true, test_data->req_byte_true,
                           test_data->miss_byte_true);

  cache->cache_free(cache);
  my_free(sizeof(cache_stat_t) * (CACHE_SIZE / STEP_SIZE), res);
}

// Individual test functions (ordered alphabetically)
static void test_ARC(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[0]);
}

static void test_Belady(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[1]);
}

static void test_BeladySize(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[2]);
}

static void test_Cacheus(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[3]);
}

static void test_CAR(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[4]);
}

static void test_Clock(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[5]);
}

static void test_ClockPro(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[6]);
}

static void test_CR_LFU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[7]);
}

static void test_FIFO(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[8]);
}

static void test_GDSF(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[9]);
}

static void test_Hyperbolic(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[10]);
}

static void test_LeCaR(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[11]);
}

static void test_LFU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[12]);
}

static void test_LFUCpp(gconstpointer user_data) {
  // LFUCpp uses the same test data as LFU
  test_cache_algorithm(user_data, &test_data_truth[12]);
}

static void test_LFUDA(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[13]);
}

static void test_LHD(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[14]);
}

static void test_LIRS(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[15]);
}

static void test_LRU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[16]);
}

static void test_LRUv0(gconstpointer user_data) {
  // LRUv0 is the older GLib-based LRU, so it must match LRU exactly
  cache_test_data_t test_data = test_data_truth[16];
  test_data.cache_name = "LRUv0";
  test_cache_algorithm(user_data, &test_data);
}

static void test_LRU_K(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[17]);
}

static void test_Merlin(gconstpointer user_data) {
  test_cache_algorithm(user_data,
                       &test_data_truth[G_N_ELEMENTS(test_data_truth) - 1]);
}

static void test_MRU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[18]);
}

// Evicting the only object empties the queue. MRU_evict used to write through
// the new, NULL, head and leave the tail pointing at the freed object, so the
// second miss in a one-object cache segfaulted.
static void test_MRU_evict_only_object(void) {
  common_cache_params_t cc_params = {.cache_size = 1, .hashpower = 8};
  cache_t *cache = MRU_init(cc_params, NULL);
  request_t *req = new_request();
  req->obj_size = 1;

  for (obj_id_t id = 1; id <= 4; id++) {
    req->obj_id = id;
    g_assert_false(cache->get(cache, req));
    g_assert_cmpint(cache->get_n_obj(cache), ==, 1);
    g_assert_nonnull(cache->find(cache, req, false));
    req->obj_id = id - 1;
    g_assert_null(cache->find(cache, req, false));
  }

  free_request(req);
  cache->cache_free(cache);
}

static void test_QDLP_FIFO(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[19]);
}

static void test_Random(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[20]);
}

static void test_S3FIFO(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[21]);
}

// An object read more than INT32_MAX times since the main FIFO last passed it
// is the hottest object in the cache. Its 64-bit counter must survive the
// eviction loop's local copy, or the loop sees a negative count and evicts it.
static void test_S3FIFO_main_freq_beyond_int32(void) {
  common_cache_params_t cc_params = {.cache_size = 100, .hashpower = 8};
  cache_t *cache = S3FIFO_init(cc_params, NULL);
  request_t *req = new_request();
  req->obj_size = 1;

  // Objects 1 to 10 fill the small FIFO and 11 to 100 go straight to main,
  // since nothing has been evicted yet. Two reads each promote 1 to 10.
  for (obj_id_t id = 1; id <= 100; id++) {
    req->obj_id = id;
    cache->get(cache, req);
  }
  for (int round = 0; round < 2; round++) {
    for (obj_id_t id = 1; id <= 10; id++) {
      req->obj_id = id;
      cache->get(cache, req);
    }
  }

  // Object 11 is the oldest in main. Give it 2^31 reads.
  req->obj_id = 11;
  cache_obj_t *hot = cache->find(cache, req, false);
  g_assert_nonnull(hot);
  hot->S3FIFO.freq = (int64_t)INT32_MAX + 1;

  // The next miss promotes 1 to 10, overfilling main, so main evicts from its
  // head. Object 11 must be reinserted, and object 12 evicted in its place.
  req->obj_id = 101;
  cache->get(cache, req);
  req->obj_id = 11;
  g_assert_nonnull(cache->find(cache, req, false));
  req->obj_id = 12;
  g_assert_null(cache->find(cache, req, false));

  free_request(req);
  cache->cache_free(cache);
}

#ifdef SUPPORT_TTL
// S3FIFO moves an object between its queues by re-inserting it through a
// local request that carries no TTL. Both moves, promotion from the small FIFO
// and reinsertion at the main tail, must keep the object's own expiry.
static void test_S3FIFO_keeps_expiry_across_moves(void) {
  common_cache_params_t cc_params = {.cache_size = 100, .hashpower = 8};
  cache_t *cache = S3FIFO_init(cc_params, NULL);
  request_t *req = new_request();
  req->obj_size = 1;
  req->clock_time = 0;

  // As in test_S3FIFO_main_freq_beyond_int32: objects 1 to 10 fill the small
  // FIFO and 11 to 100 go straight to main. Objects 1 and 11 expire at 1000.
  for (obj_id_t id = 1; id <= 100; id++) {
    req->obj_id = id;
    req->ttl = (id == 1 || id == 11) ? 1000 : 0;
    cache->get(cache, req);
  }
  req->ttl = 0;
  // Two reads each will promote 1 to 10; one read lets 11, the oldest object
  // in main, survive the main tail once.
  for (int round = 0; round < 2; round++) {
    for (obj_id_t id = 1; id <= 10; id++) {
      req->obj_id = id;
      cache->get(cache, req);
    }
  }
  req->obj_id = 11;
  cache->get(cache, req);

  // The next miss promotes 1 to 10 and makes main reinsert 11.
  req->obj_id = 101;
  cache->get(cache, req);

  req->obj_id = 1;
  cache_obj_t *obj = cache->find(cache, req, false);
  g_assert_nonnull(obj);
  g_assert_cmpuint(obj->exp_time, ==, 1000);
  req->obj_id = 11;
  obj = cache->find(cache, req, false);
  g_assert_nonnull(obj);
  g_assert_cmpuint(obj->exp_time, ==, 1000);

  free_request(req);
  cache->cache_free(cache);
}
#endif

static void test_S3FIFOv0(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[22]);
}

#if defined(ENABLE_S4FIFO) && ENABLE_S4FIFO == 1
static void test_S4FIFO(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[23]);
}
#endif

static void test_Sieve(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[24]);
}

static void test_SLRU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[25]);
}

static void test_SR_LRU(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[26]);
}

static void test_Clock2QPlus(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[27]);
}

static void test_MQ(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[28]);
}

#if defined(ENABLE_3L_CACHE) && ENABLE_3L_CACHE == 1
static void test_3LCache(gconstpointer user_data) {
  // Index must name the 3LCache row: test_cache_algorithm() builds the cache
  // from test_data_truth[i].cache_name, so a wrong index silently tests a
  // different algorithm rather than failing.
  test_cache_algorithm(user_data, &test_data_truth[31]);
}
#endif /* ENABLE_3L_CACHE */

// W-TinyLFU counts every access, so a hit in the window must raise an object's
// frequency just as a hit in the main cache does. Object 102 is read six times
// while it sits in the window; when it reaches the window's tail it must beat
// the main cache's victim, counted twice, and be admitted.
static void test_WTinyLFU_counts_window_hits(void) {
  // 1000-byte objects: 100 fit, half in the window and half in the main cache.
  // The sketch is sized from the main cache's bytes, so with this few objects
  // its counts are exact.
  common_cache_params_t cc_params = {.cache_size = 100 * 1000, .hashpower = 8};
  cache_t *cache = WTinyLFU_init(cc_params, "main-cache=LRU,window-size=0.5");
  request_t *req = new_request();
  req->obj_size = 1000;

  // The window holds everything until the cache is full. Object 101 triggers
  // the first eviction, which moves 1 to 50 into the main cache; from then on
  // each new object pushes the window's oldest out, and it is dropped unless
  // its count beats that of object 1, the main cache's LRU victim.
  for (obj_id_t id = 1; id <= 102; id++) {
    req->obj_id = id;
    g_assert_false(cache->get(cache, req));
  }
  req->obj_id = 102;
  for (int i = 0; i < 5; i++) {
    g_assert_true(cache->get(cache, req));
  }

  // 49 new objects bring 102 to the window's tail, and the 50th evicts it.
  for (obj_id_t id = 103; id <= 152; id++) {
    req->obj_id = id;
    g_assert_false(cache->get(cache, req));
  }

  // 102 won: it is in the main cache, and object 1 was evicted for it.
  req->obj_id = 102;
  g_assert_nonnull(cache->find(cache, req, false));
  req->obj_id = 1;
  g_assert_null(cache->find(cache, req, false));

  free_request(req);
  cache->cache_free(cache);
}

// The first hill climbing decision, after 10 x cache size requests, grows the
// window from 1% to 5%, and the main cache evicts down to its new size.
static void test_WTinyLFU_hill_climb_grows_window(void) {
  common_cache_params_t cc_params = {.cache_size = 100, .hashpower = 8};
  cache_t *cache = WTinyLFU_init(cc_params, "main-cache=LRU,hill-climb=1");
  request_t *req = new_request();
  req->obj_size = 1;

  // 101 moves 1 to 99 into the main cache
  for (obj_id_t id = 1; id <= 101; id++) {
    req->obj_id = id;
    g_assert_false(cache->get(cache, req));
  }
  g_assert_cmpint(cache->get_n_obj(cache), ==, 100);

  // hits on the main cache until the 1000th request
  for (int i = 0; i < 899; i++) {
    req->obj_id = 2 + i % 98;
    g_assert_true(cache->get(cache, req));
  }

  // the main cache is now 95 objects instead of 99
  g_assert_cmpint(cache->get_n_obj(cache), ==, 96);

  // the window grows into the free space
  for (obj_id_t id = 102; id <= 105; id++) {
    req->obj_id = id;
    g_assert_false(cache->get(cache, req));
  }
  g_assert_cmpint(cache->get_n_obj(cache), ==, 100);

  free_request(req);
  cache->cache_free(cache);
}

// A period without hits must not trap the climber: 30-byte objects fit neither
// the 1% nor the 5% window of a 400-byte cache, so it must grow it to 10%.
static void test_WTinyLFU_hill_climb_no_hits(void) {
  common_cache_params_t cc_params = {.cache_size = 400, .hashpower = 8};
  cache_t *cache = WTinyLFU_init(cc_params, "main-cache=LRU,hill-climb=1");
  request_t *req = new_request();
  req->obj_size = 30;

  int64_t n_hit = 0;
  for (int i = 0; i < 1000; i++) {
    req->obj_id = 1 + i % 5;
    bool hit = cache->get(cache, req);
    // a period is 134 requests; the window holds an object from the third on
    if (i < 268) g_assert_false(hit);
    n_hit += hit;
  }
  g_assert_cmpint(n_hit, >, 0);

  free_request(req);
  cache->cache_free(cache);
}

// SLRU_resize keeps the 1:4 shares: the first segment, which caps the object
// size, is 14 at size 71, 6 at size 30, and 14 again back at size 71.
static void test_SLRU_resize(void) {
  common_cache_params_t cc_params = {.cache_size = 71, .hashpower = 8};
  cache_t *cache = SLRU_init(cc_params, "seg-size=1:4");
  request_t *req = new_request();
  req->obj_id = 1;

  SLRU_resize(cache, 30);
  g_assert_cmpint(cache->cache_size, ==, 30);
  req->obj_size = 6;
  g_assert_true(cache->can_insert(cache, req));
  req->obj_size = 7;
  g_assert_false(cache->can_insert(cache, req));

  SLRU_resize(cache, 71);
  req->obj_size = 14;
  g_assert_true(cache->can_insert(cache, req));
  req->obj_size = 15;
  g_assert_false(cache->can_insert(cache, req));

  free_request(req);
  cache->cache_free(cache);
}

// After SLRU_resize an object can be larger than the next segment. A hit must
// keep it, not promote it, cool it back down and evict it.
static void test_SLRU_resize_keeps_large_object(void) {
  common_cache_params_t cc_params = {.cache_size = 100, .hashpower = 8};
  cache_t *cache = SLRU_init(cc_params, "seg-size=1:4");
  request_t *req = new_request();
  req->obj_id = 1;
  req->obj_size = 20;

  g_assert_false(cache->get(cache, req));
  SLRU_resize(cache, 20);  // segments of 4 and 16 bytes
  g_assert_true(cache->get(cache, req));
  g_assert_nonnull(cache->find(cache, req, false));

  free_request(req);
  cache->cache_free(cache);
}

/* The MINISIM profiler only knows an algorithm by its name and reaches it
 * through create_cache_using_plugin(). That used to go straight to dlsym(),
 * which cannot see a built-in constructor in a statically linked build — the
 * archive member holding it is never pulled in — so every built-in name failed
 * with "undefined symbol: lru_init" (issue #304). The registry lookup that
 * replaced it matches names case-insensitively, the same way cachesim does. */
static void test_create_cache_by_name(gconstpointer user_data) {
  common_cache_params_t cc_params = {
      .cache_size = CACHE_SIZE, .hashpower = 20, .default_ttl = DEFAULT_TTL};

  static const struct {
    const char *requested;
    const char *expected_name;
  } names[] = {
      {"lru", "LRU"},   {"LRU", "LRU"},   {"Lru", "LRU"}, {"fifo", "FIFO"},
      {"FIFO", "FIFO"}, {"fIfO", "FIFO"}, {"mru", "MRU"}, {"MRU", "MRU"},
  };

  for (size_t i = 0; i < sizeof(names) / sizeof(names[0]); i++) {
    cache_t *cache =
        create_cache_using_plugin(names[i].requested, cc_params, NULL);
    g_assert_nonnull(cache);
    g_assert_cmpstr(cache->cache_name, ==, names[i].expected_name);
    cache->cache_free(cache);
  }

  // left out of the registry on purpose, see cacheAlgoRegistry.c
  g_assert_null(create_cache_by_name("lruv0", cc_params, NULL));
}

static void empty_test(gconstpointer user_data) { ; }

static void test_WorkloadAware(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[29]);
}

static void test_AsymCache(gconstpointer user_data) {
  test_cache_algorithm(user_data, &test_data_truth[30]);
}

int main(int argc, char *argv[]) {
  g_test_init(&argc, &argv, NULL);
  srand(0);           // for reproducibility
  set_rand_seed(42);  // Use fixed seed for cross-platform consistency

  reader_t *reader;

  // do not use these two because object size change over time and
  // not all algorithms can handle the object size change correctly
  // reader = setup_csv_reader_obj_num();
  // reader = setup_vscsi_reader();

  reader = setup_oracleGeneralBin_reader();

  // Test registrations (ordered alphabetically)
  g_test_add_data_func("/libCacheSim/cacheAlgo_ARC", reader, test_ARC);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Cacheus", reader, test_Cacheus);
  g_test_add_data_func("/libCacheSim/cacheAlgo_CAR", reader, test_CAR);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Clock", reader, test_Clock);
  g_test_add_data_func("/libCacheSim/cacheAlgo_ClockPro", reader,
                       test_ClockPro);
  g_test_add_data_func("/libCacheSim/cacheAlgo_CR_LFU", reader, test_CR_LFU);
  g_test_add_data_func("/libCacheSim/cacheAlgo_FIFO", reader, test_FIFO);
  g_test_add_data_func("/libCacheSim/cacheAlgo_GDSF", reader, test_GDSF);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Hyperbolic", reader,
                       test_Hyperbolic);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LeCaR", reader, test_LeCaR);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LFU", reader, test_LFU);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LFUCpp", reader, test_LFUCpp);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LFUDA", reader, test_LFUDA);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LHD", reader, test_LHD);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LIRS", reader, test_LIRS);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LRU", reader, test_LRU);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LRUv0", reader, test_LRUv0);
  g_test_add_data_func("/libCacheSim/cacheAlgo_LRU_K", reader, test_LRU_K);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Merlin", reader, test_Merlin);
  g_test_add_data_func("/libCacheSim/cacheAlgo_MQ", reader, test_MQ);
  g_test_add_data_func("/libCacheSim/cacheAlgo_MRU", reader, test_MRU);
  g_test_add_func("/libCacheSim/cacheAlgo_MRU_evict_only_object",
                  test_MRU_evict_only_object);
  g_test_add_data_func("/libCacheSim/cacheAlgo_QDLP_FIFO", reader,
                       test_QDLP_FIFO);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Random", reader, test_Random);
  g_test_add_data_func("/libCacheSim/cacheAlgo_S3FIFO", reader, test_S3FIFO);
  g_test_add_func("/libCacheSim/cacheAlgo_S3FIFO_main_freq_beyond_int32",
                  test_S3FIFO_main_freq_beyond_int32);
#ifdef SUPPORT_TTL
  g_test_add_func("/libCacheSim/cacheAlgo_S3FIFO_keeps_expiry_across_moves",
                  test_S3FIFO_keeps_expiry_across_moves);
#endif
  g_test_add_data_func("/libCacheSim/cacheAlgo_S3FIFOv0", reader,
                       test_S3FIFOv0);
#if defined(ENABLE_S4FIFO) && ENABLE_S4FIFO == 1
  g_test_add_data_func("/libCacheSim/cacheAlgo_S4FIFO", reader, test_S4FIFO);
#endif
  g_test_add_data_func("/libCacheSim/cacheAlgo_Sieve", reader, test_Sieve);
  g_test_add_data_func("/libCacheSim/cacheAlgo_SLRU", reader, test_SLRU);
  g_test_add_data_func("/libCacheSim/cacheAlgo_SR_LRU", reader, test_SR_LRU);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Clock2QPlus", reader,
                       test_Clock2QPlus);
  g_test_add_func("/libCacheSim/cacheAlgo_WTinyLFU_counts_window_hits",
                  test_WTinyLFU_counts_window_hits);
  g_test_add_func("/libCacheSim/cacheAlgo_WTinyLFU_hill_climb_grows_window",
                  test_WTinyLFU_hill_climb_grows_window);
  g_test_add_func("/libCacheSim/cacheAlgo_WTinyLFU_hill_climb_no_hits",
                  test_WTinyLFU_hill_climb_no_hits);
  g_test_add_func("/libCacheSim/cacheAlgo_SLRU_resize", test_SLRU_resize);
  g_test_add_func("/libCacheSim/cacheAlgo_SLRU_resize_keeps_large_object",
                  test_SLRU_resize_keeps_large_object);

#if defined(ENABLE_3L_CACHE) && ENABLE_3L_CACHE == 1
  g_test_add_data_func("/libCacheSim/cacheAlgo_3LCache", reader, test_3LCache);
#endif /* ENABLE_3L_CACHE */

  // Belady algorithms require reader that has next access information
  // and can only use oracleGeneral trace (which we're using)
  g_test_add_data_func("/libCacheSim/cacheAlgo_WorkloadAware", reader,
                       test_WorkloadAware);
  g_test_add_data_func("/libCacheSim/cacheAlgo_AsymCache", reader,
                       test_AsymCache);
  g_test_add_data_func("/libCacheSim/cacheAlgo_Belady", reader, test_Belady);
  g_test_add_data_func("/libCacheSim/cacheAlgo_BeladySize", reader,
                       test_BeladySize);

  g_test_add_data_func("/libCacheSim/create_cache_by_name", reader,
                       test_create_cache_by_name);

  g_test_add_data_func_full("/libCacheSim/empty", reader, empty_test,
                            test_teardown);

  return g_test_run();
}