policies.c

Go to the documentation of this file.

#include "cache_bench.h"
#include "ra8_attributes.h"
 
/* ------------------------------------------------------------------ FIFO -- */

RA8_INTERNAL
static int internal_fifo_init(cb_cache_t* c)
{
  uint32_t* hand = (uint32_t*)c->policy_workspace;
  c->policy_data = hand;
  return (hand == nullptr) ? 1 : 0;
}

RA8_INTERNAL
static void internal_fifo_deinit(cb_cache_t* c)
{
  c->policy_data = nullptr;
}

RA8_INTERNAL
static uint32_t internal_fifo_victim(cb_cache_t* c, uint32_t* scanned)
{
  uint32_t*      hand = (uint32_t*)c->policy_data;
  const uint32_t f    = *hand;
  *hand               = (*hand + 1U) % c->capacity;
  *scanned            = 1U;
  return f;
}
static const cache_policy_t s_cb_policy_fifo = {
  .name              = "FIFO",
  .meta_bytes        = 0U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_fifo_init,
  .deinit            = internal_fifo_deinit,
  .on_access         = nullptr,
  .on_insert         = nullptr,
  .pick_victim       = internal_fifo_victim,
};
 
/* ---------------------------------------------------------------- Random -- */

typedef enum : uint64_t {
  k_rand_seed = 0x123456789ABCDEF0ULL, 
} cb_rand_seed_t;

typedef enum : uint8_t {
  k_rand_shift_a = 13U, 
  k_rand_shift_b = 7U,  
  k_rand_shift_c = 17U, 
} cb_rand_shift_t;

RA8_INTERNAL
static int internal_rand_init(cb_cache_t* c)
{
  uint64_t* s = (uint64_t*)c->policy_workspace;
  if (s != nullptr) {
    *s = (uint64_t)k_rand_seed;
  }
  c->policy_data = s;
  return (s == nullptr) ? 1 : 0;
}

RA8_INTERNAL
static void internal_rand_deinit(cb_cache_t* c)
{
  c->policy_data = nullptr;
}

RA8_INTERNAL
static uint32_t internal_rand_victim(cb_cache_t* c, uint32_t* scanned)
{
  uint64_t* s = (uint64_t*)c->policy_data;
  uint64_t  x = *s;
  x ^= x << (uint8_t)k_rand_shift_a;
  x ^= x >> (uint8_t)k_rand_shift_b;
  x ^= x << (uint8_t)k_rand_shift_c;
  *s       = x;
  *scanned = 1U;
  return (uint32_t)(x % (uint64_t)c->capacity);
}
static const cache_policy_t s_cb_policy_random = {
  .name              = "Random",
  .meta_bytes        = 0U,
  .state_base_bytes  = sizeof(uint64_t),
  .state_frame_bytes = 0U,
  .init              = internal_rand_init,
  .deinit            = internal_rand_deinit,
  .on_access         = nullptr,
  .on_insert         = nullptr,
  .pick_victim       = internal_rand_victim,
};
 
/* ------------------------------------------------------------------- LRU -- */

typedef struct {
  int32_t* prev; 
  int32_t* next; 
  int32_t  head; 
  int32_t  tail; 
} cb_lru_t;

RA8_INTERNAL
static int internal_lru_init(cb_cache_t* c)
{
  const size_t required = sizeof(cb_lru_t) + ((size_t)c->capacity * 2U * sizeof(int32_t));
  if ((c->policy_workspace == nullptr) || (c->policy_workspace_bytes < required)) {
    return 1;
  }
  cb_lru_t* l    = (cb_lru_t*)c->policy_workspace;
  l->prev        = (int32_t*)&l[1];
  l->next        = &l->prev[c->capacity];
  l->head        = -1;
  l->tail        = -1;
  c->policy_data = l;
  return 0;
}

RA8_INTERNAL
static void internal_lru_deinit(cb_cache_t* c)
{
  c->policy_data = nullptr;
}

RA8_INTERNAL
static void internal_lru_unlink(cb_lru_t* l, int32_t f)
{
  if (l->prev[f] != -1) {
    l->next[l->prev[f]] = l->next[f];
  } else if (l->head == f) {
    l->head = l->next[f];
  }
  if (l->next[f] != -1) {
    l->prev[l->next[f]] = l->prev[f];
  } else if (l->tail == f) {
    l->tail = l->prev[f];
  }
}

RA8_INTERNAL
static void internal_lru_to_head(cb_lru_t* l, int32_t f)
{
  l->prev[f] = -1;
  l->next[f] = l->head;
  if (l->head != -1) {
    l->prev[l->head] = f;
  }
  l->head = f;
  if (l->tail == -1) {
    l->tail = f;
  }
}

RA8_INTERNAL
static void internal_lru_touch(cb_cache_t* c, uint32_t frame)
{
  cb_lru_t* l = (cb_lru_t*)c->policy_data;
  internal_lru_unlink(l, (int32_t)frame);
  internal_lru_to_head(l, (int32_t)frame);
}

RA8_INTERNAL
static void internal_lru_insert(cb_cache_t* c, uint32_t frame)
{
  cb_lru_t* l = (cb_lru_t*)c->policy_data;
  internal_lru_to_head(l, (int32_t)frame);
}

RA8_INTERNAL
static uint32_t internal_lru_victim(cb_cache_t* c, uint32_t* scanned)
{
  cb_lru_t*     l = (cb_lru_t*)c->policy_data;
  const int32_t f = l->tail;
  internal_lru_unlink(l, f);
  *scanned = 1U;
  return (uint32_t)f;
}
static const cache_policy_t s_cb_policy_lru = {
  .name              = "LRU",
  .meta_bytes        = 8U,
  .state_base_bytes  = sizeof(cb_lru_t),
  .state_frame_bytes = 2U * sizeof(int32_t),
  .init              = internal_lru_init,
  .deinit            = internal_lru_deinit,
  .on_access         = internal_lru_touch,
  .on_insert         = internal_lru_insert,
  .pick_victim       = internal_lru_victim,
};
 
/* ----------------------------------------------------------------- CLOCK -- */

RA8_INTERNAL
static int internal_clock_init(cb_cache_t* c)
{
  uint32_t* hand = (uint32_t*)c->policy_workspace;
  c->policy_data = hand;
  return (hand == nullptr) ? 1 : 0;
}

RA8_INTERNAL
static void internal_clock_deinit(cb_cache_t* c)
{
  c->policy_data = nullptr;
}

RA8_INTERNAL
static void internal_clock_set(cb_cache_t* c, uint32_t frame)
{
  c->frames[frame].meta[0] = 1U;
}

RA8_INTERNAL
static uint32_t internal_clock_victim(cb_cache_t* c, uint32_t* scanned)
{
  uint32_t* hand = (uint32_t*)c->policy_data;
  uint32_t  seen = 0U;
  for (;;) {
    const uint32_t f = *hand;
    *hand            = (*hand + 1U) % c->capacity;
    seen++;
    if (c->frames[f].meta[0] != 0U) {
      c->frames[f].meta[0] = 0U; /* second chance */
    } else {
      *scanned = seen;
      return f;
    }
  }
}
static const cache_policy_t s_cb_policy_clock = {
  .name              = "CLOCK",
  .meta_bytes        = 1U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_clock_init,
  .deinit            = internal_clock_deinit,
  .on_access         = internal_clock_set,
  .on_insert         = internal_clock_set,
  .pick_victim       = internal_clock_victim,
};
 
/* -------------------------------------------------------------- registry -- */
 
const cache_policy_t* const g_cb_policies[] = {
  &s_cb_policy_fifo,
  &s_cb_policy_random,
  &s_cb_policy_lru,
  &s_cb_policy_clock,
  &g_cb_policy_slru,
  &g_cb_policy_srrip,
};
const uint32_t g_cb_policy_count = (uint32_t)(sizeof(g_cb_policies) / sizeof(g_cb_policies[0]));