policy_scanresist.c

Go to the documentation of this file.

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

typedef enum : uint8_t {
  k_slru_probation = 0U, 
  k_slru_protected = 1U, 
} slru_seg_t;

typedef enum : uint32_t {
  k_slru_protected_pct  = 75U,  
  k_slru_pct_full_scale = 100U, 
  k_slru_meta_bytes     = 9U,   
} slru_dim_t;

typedef struct {
  int32_t* prev;     
  int32_t* next;     
  int32_t  pb_head;  
  int32_t  pb_tail;  
  int32_t  pt_head;  
  int32_t  pt_tail;  
  uint32_t pt_count; 
  uint32_t pt_cap;   
} slru_t;

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

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

RA8_INTERNAL
static int internal_slru_init(cb_cache_t* c)
{
  const size_t required = sizeof(slru_t) + ((size_t)c->capacity * 2U * sizeof(int32_t));
  if ((c->policy_workspace == nullptr) || (c->policy_workspace_bytes < required)) {
    return 1;
  }
  slru_t* l      = (slru_t*)c->policy_workspace;
  l->prev        = (int32_t*)&l[1];
  l->next        = &l->prev[c->capacity];
  l->pb_head     = -1;
  l->pb_tail     = -1;
  l->pt_head     = -1;
  l->pt_tail     = -1;
  l->pt_cap      = (c->capacity * (uint32_t)k_slru_protected_pct) / (uint32_t)k_slru_pct_full_scale;
  c->policy_data = l;
  return 0;
}

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

RA8_INTERNAL
static void internal_slru_insert(cb_cache_t* c, uint32_t frame)
{
  slru_t* l                = (slru_t*)c->policy_data;
  c->frames[frame].meta[0] = (uint8_t)k_slru_probation;
  internal_slru_push_head(l, (int32_t)frame, &l->pb_head, &l->pb_tail);
}

RA8_INTERNAL
static void internal_slru_access(cb_cache_t* c, uint32_t frame)
{
  slru_t*       l = (slru_t*)c->policy_data;
  const int32_t f = (int32_t)frame;
  if (c->frames[frame].meta[0] == (uint8_t)k_slru_protected) {
    internal_slru_unlink(l, f, &l->pt_head, &l->pt_tail);
    internal_slru_push_head(l, f, &l->pt_head, &l->pt_tail);
    return;
  }
  /* Promote probationary -> protected; demote protected LRU if over cap. */
  internal_slru_unlink(l, f, &l->pb_head, &l->pb_tail);
  if ((l->pt_cap > 0U) && (l->pt_count == l->pt_cap)) {
    const int32_t d = l->pt_tail;
    internal_slru_unlink(l, d, &l->pt_head, &l->pt_tail);
    c->frames[d].meta[0] = (uint8_t)k_slru_probation;
    internal_slru_push_head(l, d, &l->pb_head, &l->pb_tail);
    l->pt_count--;
  }
  c->frames[frame].meta[0] = (uint8_t)k_slru_protected;
  internal_slru_push_head(l, f, &l->pt_head, &l->pt_tail);
  l->pt_count++;
}

RA8_INTERNAL
static uint32_t internal_slru_victim(cb_cache_t* c, uint32_t* scanned)
{
  slru_t* l = (slru_t*)c->policy_data;
  *scanned  = 1U;
  if (l->pb_tail != -1) {
    const int32_t f = l->pb_tail;
    internal_slru_unlink(l, f, &l->pb_head, &l->pb_tail);
    return (uint32_t)f;
  }
  const int32_t f = l->pt_tail;
  internal_slru_unlink(l, f, &l->pt_head, &l->pt_tail);
  l->pt_count--;
  return (uint32_t)f;
}
 
const cache_policy_t g_cb_policy_slru = {
  .name              = "SLRU",
  .meta_bytes        = (size_t)k_slru_meta_bytes,
  .state_base_bytes  = sizeof(slru_t),
  .state_frame_bytes = 2U * sizeof(int32_t),
  .init              = internal_slru_init,
  .deinit            = internal_slru_deinit,
  .on_access         = internal_slru_access,
  .on_insert         = internal_slru_insert,
  .pick_victim       = internal_slru_victim,
};
 
/* ----------------------------------------------------------------- SRRIP -- */

typedef enum : uint8_t {
  k_rrip_near = 0U, 
  k_rrip_long = 2U, 
  k_rrip_max  = 3U, 
} rrip_rrpv_t;

RA8_INTERNAL
static int internal_srrip_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_srrip_deinit(cb_cache_t* c)
{
  c->policy_data = nullptr;
}

RA8_INTERNAL
static void internal_srrip_insert(cb_cache_t* c, uint32_t frame)
{
  c->frames[frame].meta[0] = (uint8_t)k_rrip_long;
}

RA8_INTERNAL
static void internal_srrip_access(cb_cache_t* c, uint32_t frame)
{
  c->frames[frame].meta[0] = (uint8_t)k_rrip_near;
}

RA8_INTERNAL
static uint32_t internal_srrip_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] == (uint8_t)k_rrip_max) {
      *scanned = seen;
      return f;
    }
    /* Age toward the max so a victim is guaranteed within two ring passes. */
    if (c->frames[f].meta[0] < (uint8_t)k_rrip_max) {
      c->frames[f].meta[0]++;
    }
  }
}
 
const cache_policy_t g_cb_policy_srrip = {
  .name              = "SRRIP",
  .meta_bytes        = 1U,
  .state_base_bytes  = sizeof(uint32_t),
  .state_frame_bytes = 0U,
  .init              = internal_srrip_init,
  .deinit            = internal_srrip_deinit,
  .on_access         = internal_srrip_access,
  .on_insert         = internal_srrip_insert,
  .pick_victim       = internal_srrip_victim,
};