cache_bench.c

Go to the documentation of this file.

#include "cache_bench.h"
 
#include <string.h>
 
#include "cache_bench_io.h"
#include "ra8_attributes.h"
#include "trace.h"

RA8_INTERNAL
static uint32_t internal_pow2_ceil(uint32_t v)
{
  uint32_t p = 1U;
  while (p < v) {
    p <<= 1U;
  }
  return p;
}

typedef enum : uint64_t {
  k_hash_mix_mul = 0xFF51AFD7ED558CCDULL, 
} cb_hash_mul_t;

typedef enum : uint8_t {
  k_hash_shift = 33U, 
} cb_hash_shift_t;

RA8_INTERNAL
static uint32_t internal_hash(cb_key_t k)
{
  uint64_t h = ((uint64_t)k.object_id << 32U) | (uint64_t)k.page;
  h ^= h >> (uint8_t)k_hash_shift;
  h *= (uint64_t)k_hash_mix_mul;
  h ^= h >> (uint8_t)k_hash_shift;
  return (uint32_t)h;
}

RA8_INTERNAL
static bool internal_key_eq(cb_key_t a, cb_key_t b)
{
  return (a.object_id == b.object_id) && (a.page == b.page);
}

typedef struct {
  int32_t* bucket; 
  int32_t* next;   
  uint32_t mask;   
} cb_index_t;

RA8_INTERNAL
static int32_t internal_index_find(const cb_index_t* idx, const cb_frame_t* frames, cb_key_t key)
{
  for (int32_t j = idx->bucket[internal_hash(key) & idx->mask]; j != -1; j = idx->next[j]) {
    if (internal_key_eq(frames[j].key, key)) {
      return j;
    }
  }
  return -1;
}

RA8_INTERNAL
static void internal_index_remove(cb_index_t* idx, const cb_frame_t* frames, uint32_t frame)
{
  const uint32_t ob   = internal_hash(frames[frame].key) & idx->mask;
  int32_t        prev = -1;
  for (int32_t j = idx->bucket[ob]; j != -1; prev = j, j = idx->next[j]) {
    if (j == (int32_t)frame) {
      if (prev == -1) {
        idx->bucket[ob] = idx->next[j];
      } else {
        idx->next[prev] = idx->next[j];
      }
      break;
    }
  }
}

RA8_INTERNAL
static void internal_index_push(cb_index_t* idx, uint32_t frame, cb_key_t key)
{
  const uint32_t b = internal_hash(key) & idx->mask;
  idx->next[frame] = idx->bucket[b];
  idx->bucket[b]   = (int32_t)frame;
}

RA8_INTERNAL
static uint32_t internal_replay_take_frame(const cache_policy_t* pol,
                                           cb_cache_t*           cache,
                                           cb_index_t*           idx,
                                           uint32_t*             filled,
                                           cb_result_t*          out)
{
  if (*filled < cache->capacity) {
    const uint32_t frame = *filled;
    (*filled)++;
    return frame;
  }
  uint32_t       scanned = 0U;
  const uint32_t frame   = pol->pick_victim(cache, &scanned);
  out->evictions++;
  out->total_scan += scanned;
  if (scanned > out->worst_scan) {
    out->worst_scan = scanned;
  }
  internal_index_remove(idx, cache->frames, frame);
  return frame;
}

RA8_INTERNAL
static size_t internal_align_size(size_t value)
{
  const size_t alignment = alignof(max_align_t);
  if (value > (SIZE_MAX - (alignment - 1U))) {
    return 0U;
  }
  return (value + alignment - 1U) & ~(alignment - 1U);
}

RA8_INTERNAL
static bool internal_size_multiply(size_t left, size_t right, size_t* result)
{
  if ((result == nullptr) || ((left != 0U) && (right > (SIZE_MAX / left)))) {
    return false;
  }
  *result = left * right;
  return true;
}
 
typedef enum : uint32_t {
  k_cb_max_hash_capacity = UINT32_C(1) << 29U, 
} cb_hash_limit_t;
 
size_t cb_replay_workspace_required(const cache_policy_t* pol, uint32_t capacity)
{
  if ((pol == nullptr) || (capacity == 0U) || (capacity > (uint32_t)k_cb_max_hash_capacity)) {
    return 0U;
  }
  const uint32_t hsize = internal_pow2_ceil(capacity * 4U);
  size_t         frame_bytes;
  size_t         hash_bytes;
  size_t         link_bytes;
  size_t         policy_frame_bytes;
  if (!internal_size_multiply(capacity, sizeof(cb_frame_t), &frame_bytes) ||
      !internal_size_multiply(hsize, sizeof(int32_t), &hash_bytes) ||
      !internal_size_multiply(capacity, sizeof(int32_t), &link_bytes) ||
      !internal_size_multiply(capacity, pol->state_frame_bytes, &policy_frame_bytes) ||
      (pol->state_base_bytes > (SIZE_MAX - policy_frame_bytes))) {
    return 0U;
  }
  const size_t parts[] = {
    frame_bytes,
    hash_bytes,
    link_bytes,
    pol->state_base_bytes + policy_frame_bytes,
  };
  size_t total = 0U;
  for (size_t i = 0U; i < (sizeof(parts) / sizeof(parts[0])); ++i) {
    const size_t aligned = internal_align_size(parts[i]);
    if ((aligned == 0U) || (total > (SIZE_MAX - aligned))) {
      return 0U;
    }
    total += aligned;
  }
  return total;
}
 
RA8_INTERNAL
static void* internal_workspace_take(cb_workspace_t* workspace, size_t* used, size_t bytes)
{
  const size_t span = internal_align_size(bytes);
  if ((span == 0U) || (*used > workspace->capacity) || (span > (workspace->capacity - *used))) {
    return nullptr;
  }
  void* result = &workspace->data[*used];
  *used += span;
  return result;
}

RA8_INTERNAL
static bool internal_replay_open(cb_index_t*           idx,
                                 cb_frame_t**          frames,
                                 void**                policy_data,
                                 const cache_policy_t* pol,
                                 uint32_t              capacity,
                                 cb_workspace_t*       workspace)
{
  const size_t required = cb_replay_workspace_required(pol, capacity);
  workspace->required   = required;
  if ((required == 0U) || (workspace->data == nullptr) ||
      (((uintptr_t)workspace->data % alignof(max_align_t)) != 0U) ||
      (workspace->capacity < required)) {
    return false;
  }
  size_t         used  = 0U;
  const uint32_t hsize = internal_pow2_ceil(capacity * 4U);
  *frames =
    (cb_frame_t*)internal_workspace_take(workspace, &used, (size_t)capacity * sizeof(cb_frame_t));
  idx->bucket =
    (int32_t*)internal_workspace_take(workspace, &used, (size_t)hsize * sizeof(int32_t));
  idx->next =
    (int32_t*)internal_workspace_take(workspace, &used, (size_t)capacity * sizeof(int32_t));
  *policy_data =
    internal_workspace_take(workspace,
                            &used,
                            pol->state_base_bytes + ((size_t)capacity * pol->state_frame_bytes));
  idx->mask = hsize - 1U;
  if ((*frames == nullptr) || (idx->bucket == nullptr) || (idx->next == nullptr) ||
      (*policy_data == nullptr)) {
    return false;
  }
  memset(*frames, 0, (size_t)capacity * sizeof(cb_frame_t));
  memset(*policy_data, 0, pol->state_base_bytes + ((size_t)capacity * pol->state_frame_bytes));
  for (uint32_t i = 0U; i < hsize; ++i) {
    idx->bucket[i] = -1;
  }
  if (used > workspace->high_water) {
    workspace->high_water = used;
  }
  return true;
}

RA8_INTERNAL
static void internal_replay_close(cb_index_t* idx, cb_frame_t* frames)
{
  (void)frames;
  *idx = (cb_index_t){};
}

RA8_INTERNAL
static int internal_replay_stream(const cache_policy_t* pol,
                                  const cb_trace_t*     trace,
                                  cb_cache_t*           cache,
                                  cb_index_t*           index,
                                  cb_result_t*          out)
{
  cb_trace_cursor_t cursor = {};
  if (cb_trace_cursor_open(trace, &cursor) != k_cb_io_ok) {
    return 1;
  }
  uint32_t filled = 0U;
  bool     done   = false;
  while (!done) {
    cb_key_t key = {};
    if (cb_trace_cursor_next(&cursor, &key, &done) != k_cb_io_ok) {
      return 1;
    }
    if (done) {
      break;
    }
    const int32_t found = internal_index_find(index, cache->frames, key);
    out->accesses++;
    if (found != -1) {
      out->hits++;
      if (pol->on_access != nullptr) {
        pol->on_access(cache, (uint32_t)found);
      }
      continue;
    }
    const uint32_t frame      = internal_replay_take_frame(pol, cache, index, &filled, out);
    cache->frames[frame].key  = key;
    cache->frames[frame].live = true;
    internal_index_push(index, frame, key);
    if (pol->on_insert != nullptr) {
      pol->on_insert(cache, frame);
    }
  }
  return (cb_trace_cursor_finish(&cursor) == k_cb_io_ok) ? 0 : 1;
}
 
int cb_replay(const cache_policy_t* pol,
              const cb_trace_t*     trace,
              uint32_t              capacity,
              cb_workspace_t*       workspace,
              cb_result_t*          out)
{
  if (out != nullptr) {
    *out = (cb_result_t){};
  }
  if ((pol == nullptr) || (trace == nullptr) || (capacity == 0U) || (workspace == nullptr) ||
      (out == nullptr)) {
    return 1;
  }
 
  cb_frame_t* frames      = nullptr;
  cb_index_t  idx         = {};
  void*       policy_data = nullptr;
  const bool  ready = internal_replay_open(&idx, &frames, &policy_data, pol, capacity, workspace);
  cb_cache_t  cache = {.frames           = frames,
                       .capacity         = capacity,
                       .policy_data      = nullptr,
                       .policy_workspace = policy_data,
                       .policy_workspace_bytes =
                         pol->state_base_bytes + ((size_t)capacity * pol->state_frame_bytes)};
  if (!ready || ((pol->init != nullptr) && (pol->init(&cache) != 0))) {
    internal_replay_close(&idx, frames);
    return 1;
  }
 
  const int result = internal_replay_stream(pol, trace, &cache, &idx, out);
  if (pol->deinit != nullptr) {
    pol->deinit(&cache);
  }
  internal_replay_close(&idx, frames);
  return result;
}