ra8_keycache.c

Go to the documentation of this file.

 
#include "ra8_keycache.h"
 
#include <stddef.h>
#include <stdint.h>
#include <string.h>
 
#include "ra8_attributes.h"
#include "ra8_check.h"
#include "ra8_err.h"

static const char* const s_tag = "ra8_keycache";

typedef enum : uint32_t {
  k_keycache_fnv_offset        = 2166136261U, 
  k_keycache_fnv_prime         = 16777619U,   
  k_keycache_protected_pct_def = 75U,         
  k_keycache_percent_full      = 100U,        
} ra8_keycache_const_t;

typedef enum : uint8_t {
  k_keycache_seg_probation = 0U, 
  k_keycache_seg_protected = 1U, 
} ra8_keycache_seg_t;

RA8_INTERNAL
RA8_INTERNAL static uint8_t* internal_cell_ptr(const ra8_keycache_t* kc, uint32_t idx)
{
  return &kc->cfg.cell_mem[(size_t)idx * (size_t)kc->cfg.cell_bytes];
}

RA8_INTERNAL
RA8_INTERNAL static uint8_t* internal_key_ptr(const ra8_keycache_t* kc, uint32_t idx)
{
  return &kc->cfg.key_mem[(size_t)idx * (size_t)kc->cfg.key_bytes];
}

RA8_INTERNAL
RA8_INTERNAL static void* internal_user_ptr(const ra8_keycache_t* kc, uint32_t idx)
{
  if (kc->cfg.user_bytes == 0U) {
    return nullptr;
  }
  return &kc->cfg.user_mem[(size_t)idx * (size_t)kc->cfg.user_bytes];
}

RA8_INTERNAL
RA8_INTERNAL static bool internal_key_eq(const ra8_keycache_t* kc, const void* a, const void* b)
{
  return memcmp(a, b, (size_t)kc->cfg.key_bytes) == 0;
}

RA8_INTERNAL
RA8_INTERNAL static uint32_t internal_fnv1a(const void* key, uint32_t key_bytes)
{
  const uint8_t* p = (const uint8_t*)key;
  uint32_t       h = (uint32_t)k_keycache_fnv_offset;
  for (uint32_t i = 0U; i < key_bytes; ++i) {
    h ^= (uint32_t)p[i];
    h *= (uint32_t)k_keycache_fnv_prime;
  }
  return h;
}

RA8_INTERNAL
RA8_INTERNAL static uint32_t internal_hash(const ra8_keycache_t* kc, const void* key)
{
  uint32_t raw;
  if (kc->cfg.hash != nullptr) {
    raw = kc->cfg.hash(key, kc->cfg.key_bytes, kc->cfg.hash_ctx);
  } else {
    raw = internal_fnv1a(key, kc->cfg.key_bytes);
  }
  return raw % kc->cfg.bucket_count;
}

RA8_INTERNAL
RA8_INTERNAL static void
internal_unlink(ra8_keycache_t* kc, int32_t f, int32_t* head, int32_t* tail)
{
  ra8_keycache_cell_t* m = kc->cfg.meta;
  if (m[f].prev != -1) {
    m[m[f].prev].next = m[f].next;
  } else if (*head == f) {
    *head = m[f].next;
  } else {
    /* not the head and has no prev: already detached -- nothing to do */
  }
  if (m[f].next != -1) {
    m[m[f].next].prev = m[f].prev;
  } else if (*tail == f) {
    *tail = m[f].prev;
  } else {
    /* not the tail and has no next: already detached -- nothing to do */
  }
}

RA8_INTERNAL
RA8_INTERNAL static void
internal_push_head(ra8_keycache_t* kc, int32_t f, int32_t* head, int32_t* tail)
{
  ra8_keycache_cell_t* m = kc->cfg.meta;
  m[f].prev              = -1;
  m[f].next              = *head;
  if (*head != -1) {
    m[*head].prev = f;
  }
  *head = f;
  if (*tail == -1) {
    *tail = f;
  }
}

RA8_INTERNAL
RA8_INTERNAL static void internal_hash_insert(ra8_keycache_t* kc, int32_t f)
{
  const uint32_t b          = internal_hash(kc, internal_key_ptr(kc, (uint32_t)f));
  kc->cfg.meta[f].hash_next = kc->cfg.buckets[b];
  kc->cfg.buckets[b]        = f;
}

RA8_INTERNAL
RA8_INTERNAL static void internal_hash_remove(ra8_keycache_t* kc, int32_t f)
{
  const uint32_t b   = internal_hash(kc, internal_key_ptr(kc, (uint32_t)f));
  int32_t        cur = kc->cfg.buckets[b];
  if (cur == f) {
    kc->cfg.buckets[b] = kc->cfg.meta[f].hash_next;
  } else {
    for (uint32_t guard = 0U; guard < kc->cfg.cell_count; ++guard) {
      if (cur == -1) {
        break;
      }
      if (kc->cfg.meta[cur].hash_next == f) {
        kc->cfg.meta[cur].hash_next = kc->cfg.meta[f].hash_next;
        break;
      }
      cur = kc->cfg.meta[cur].hash_next;
    }
  }
  kc->cfg.meta[f].hash_next = -1;
}

RA8_INTERNAL
RA8_INTERNAL static int32_t internal_hash_lookup(const ra8_keycache_t* kc, const void* key)
{
  const uint32_t b   = internal_hash(kc, key);
  int32_t        cur = kc->cfg.buckets[b];
  for (uint32_t guard = 0U; guard < kc->cfg.cell_count; ++guard) {
    if (cur == -1) {
      break;
    }
    const ra8_keycache_cell_t* m = &kc->cfg.meta[cur];
    if (m->valid != 0U) {
      if (internal_key_eq(kc, internal_key_ptr(kc, (uint32_t)cur), key)) {
        return cur;
      }
    }
    cur = m->hash_next;
  }
  return -1;
}

RA8_INTERNAL
RA8_INTERNAL static int32_t internal_first_unpinned(const ra8_keycache_t* kc, int32_t tail)
{
  int32_t cur = tail;
  for (uint32_t guard = 0U; guard < kc->cfg.cell_count; ++guard) {
    if (cur == -1) {
      break;
    }
    if (kc->cfg.meta[cur].pin_count == 0U) {
      return cur;
    }
    cur = kc->cfg.meta[cur].prev;
  }
  return -1;
}

RA8_INTERNAL
RA8_INTERNAL static int32_t internal_pick_victim(const ra8_keycache_t* kc)
{
  const int32_t pb = internal_first_unpinned(kc, kc->pb_tail);
  if (pb != -1) {
    return pb;
  }
  return internal_first_unpinned(kc, kc->pt_tail);
}

RA8_INTERNAL
RA8_INTERNAL static void internal_slru_access(ra8_keycache_t* kc, int32_t f)
{
  if (kc->cfg.meta[f].seg == (uint8_t)k_keycache_seg_protected) {
    internal_unlink(kc, f, &kc->pt_head, &kc->pt_tail);
    internal_push_head(kc, f, &kc->pt_head, &kc->pt_tail);
    return;
  }
  internal_unlink(kc, f, &kc->pb_head, &kc->pb_tail);
  if (kc->protected_count >= kc->protected_cap) {
    const int32_t d = kc->pt_tail;
    if (d != -1) {
      internal_unlink(kc, d, &kc->pt_head, &kc->pt_tail);
      kc->cfg.meta[d].seg = (uint8_t)k_keycache_seg_probation;
      internal_push_head(kc, d, &kc->pb_head, &kc->pb_tail);
      kc->protected_count--;
    }
  }
  kc->cfg.meta[f].seg = (uint8_t)k_keycache_seg_protected;
  internal_push_head(kc, f, &kc->pt_head, &kc->pt_tail);
  kc->protected_count++;
}

RA8_INTERNAL
RA8_INTERNAL static void internal_access(ra8_keycache_t* kc, int32_t f)
{
  if (kc->cfg.evict == k_ra8_keycache_evict_slru) {
    internal_slru_access(kc, f);
  } else {
    internal_unlink(kc, f, &kc->pb_head, &kc->pb_tail);
    internal_push_head(kc, f, &kc->pb_head, &kc->pb_tail);
  }
}

RA8_INTERNAL
RA8_INTERNAL static ra8_err_t internal_validate_cfg_ptrs(const ra8_keycache_cfg_t* cfg)
{
  RA8_CHECK_NULL_PTR(cfg->cell_mem, s_tag, "cell_mem must not be nullptr");
  RA8_CHECK_NULL_PTR(cfg->key_mem, s_tag, "key_mem must not be nullptr");
  RA8_CHECK_NULL_PTR(cfg->meta, s_tag, "meta must not be nullptr");
  RA8_CHECK_NULL_PTR(cfg->buckets, s_tag, "buckets must not be nullptr");
  RA8_CHECK_NULL_PTR(cfg->render, s_tag, "render must not be nullptr");
  if (cfg->user_bytes != 0U) {
    RA8_CHECK_NULL_PTR(cfg->user_mem, s_tag, "user_mem required when user_bytes > 0");
  }
  return k_ra8_ok;
}

RA8_INTERNAL
RA8_INTERNAL static ra8_err_t internal_validate_cfg_sizes(const ra8_keycache_cfg_t* cfg)
{
  if (cfg->cell_count == 0U) {
    return k_ra8_err_invalid_size;
  }
  if (cfg->cell_bytes == 0U) {
    return k_ra8_err_invalid_size;
  }
  if (cfg->key_bytes == 0U) {
    return k_ra8_err_invalid_size;
  }
  if (cfg->bucket_count == 0U) {
    return k_ra8_err_invalid_size;
  }
  return k_ra8_ok;
}

RA8_INTERNAL
RA8_INTERNAL static ra8_err_t internal_validate_cfg_policy(const ra8_keycache_cfg_t* cfg)
{
  if (cfg->evict == k_ra8_keycache_evict_slru) {
    if ((uint32_t)cfg->protected_pct > (uint32_t)k_keycache_percent_full) {
      return k_ra8_err_invalid_arg;
    }
  }
  return k_ra8_ok;
}

RA8_INTERNAL
RA8_INTERNAL static uint32_t internal_protected_cap(const ra8_keycache_cfg_t* cfg)
{
  const uint32_t pct = (cfg->protected_pct == 0U) ? (uint32_t)k_keycache_protected_pct_def
                                                  : (uint32_t)cfg->protected_pct;
  return (cfg->cell_count * pct) / (uint32_t)k_keycache_percent_full;
}

RA8_INTERNAL
RA8_INTERNAL static void internal_seed_cells(ra8_keycache_t* kc, const ra8_keycache_cfg_t* cfg)
{
  (void)memset(kc, 0, sizeof(*kc));
  kc->cfg     = *cfg;
  kc->pb_head = -1;
  kc->pb_tail = -1;
  kc->pt_head = -1;
  kc->pt_tail = -1;
  for (uint32_t b = 0U; b < cfg->bucket_count; ++b) {
    cfg->buckets[b] = -1;
  }
  for (uint32_t i = 0U; i < cfg->cell_count; ++i) {
    kc->cfg.meta[i].valid     = 0U;
    kc->cfg.meta[i].pin_count = 0U;
    kc->cfg.meta[i].seg       = (uint8_t)k_keycache_seg_probation;
    kc->cfg.meta[i].hash_next = -1;
    internal_push_head(kc, (int32_t)i, &kc->pb_head, &kc->pb_tail);
  }
}
 
ra8_err_t ra8_keycache_init(ra8_keycache_t* kc, const ra8_keycache_cfg_t* cfg)
{
  RA8_CHECK_NULL_PTR(kc, s_tag, "kc must not be nullptr");
  RA8_CHECK_NULL_PTR(cfg, s_tag, "cfg must not be nullptr");
  const ra8_err_t perr = internal_validate_cfg_ptrs(cfg);
  if (perr != k_ra8_ok) {
    return perr;
  }
  const ra8_err_t serr = internal_validate_cfg_sizes(cfg);
  if (serr != k_ra8_ok) {
    return serr;
  }
  const ra8_err_t verr = internal_validate_cfg_policy(cfg);
  if (verr != k_ra8_ok) {
    return verr;
  }
  internal_seed_cells(kc, cfg);
  kc->protected_cap = (cfg->evict == k_ra8_keycache_evict_slru) ? internal_protected_cap(cfg) : 0U;
  return k_ra8_ok;
}

RA8_INTERNAL
RA8_INTERNAL static ra8_err_t
internal_miss(ra8_keycache_t* kc, const void* key, ra8_keycache_view_t* out_view)
{
  const int32_t v = internal_pick_victim(kc);
  if (v < 0) {
    return k_ra8_err_no_mem;
  }
  ra8_keycache_cell_t* m = &kc->cfg.meta[v];
  if (m->valid != 0U) {
    internal_hash_remove(kc, v);
    kc->evictions++;
  }
  const uint8_t seg = m->seg;
  internal_unlink(kc,
                  v,
                  (seg == (uint8_t)k_keycache_seg_protected) ? &kc->pt_head : &kc->pb_head,
                  (seg == (uint8_t)k_keycache_seg_protected) ? &kc->pt_tail : &kc->pb_tail);
  if (seg == (uint8_t)k_keycache_seg_protected) {
    kc->protected_count--;
  }
  uint8_t*        cell = internal_cell_ptr(kc, (uint32_t)v);
  void*           user = internal_user_ptr(kc, (uint32_t)v);
  const ra8_err_t rerr = kc->cfg.render(kc->cfg.render_ctx, key, cell, kc->cfg.cell_bytes, user);
  if (rerr != k_ra8_ok) {
    m->valid = 0U;
    m->seg   = (uint8_t)k_keycache_seg_probation;
    internal_push_head(kc, v, &kc->pb_head, &kc->pb_tail);
    return rerr;
  }
  (void)memcpy(internal_key_ptr(kc, (uint32_t)v), key, (size_t)kc->cfg.key_bytes);
  m->valid     = 1U;
  m->pin_count = 1U;
  m->seg       = (uint8_t)k_keycache_seg_probation;
  internal_hash_insert(kc, v);
  internal_push_head(kc, v, &kc->pb_head, &kc->pb_tail);
  *out_view = (ra8_keycache_view_t){.data = cell, .user = user};
  return k_ra8_ok;
}
 
ra8_err_t ra8_keycache_get(ra8_keycache_t* kc, const void* key, ra8_keycache_view_t* out_view)
{
  RA8_CHECK_NULL_PTR(kc, s_tag, "kc must not be nullptr");
  RA8_CHECK_NULL_PTR(key, s_tag, "key must not be nullptr");
  RA8_CHECK_NULL_PTR(out_view, s_tag, "out_view must not be nullptr");
  const int32_t f = internal_hash_lookup(kc, key);
  if (f >= 0) {
    kc->hits++;
    kc->cfg.meta[f].pin_count++;
    internal_access(kc, f);
    *out_view = (ra8_keycache_view_t){.data = internal_cell_ptr(kc, (uint32_t)f),
                                      .user = internal_user_ptr(kc, (uint32_t)f)};
    return k_ra8_ok;
  }
  kc->misses++;
  return internal_miss(kc, key, out_view);
}
 
ra8_err_t ra8_keycache_prefetch(ra8_keycache_t* kc, const void* key)
{
  RA8_CHECK_NULL_PTR(kc, s_tag, "kc must not be nullptr");
  RA8_CHECK_NULL_PTR(key, s_tag, "key must not be nullptr");
  ra8_keycache_view_t view = {};
  const ra8_err_t     gerr = ra8_keycache_get(kc, key, &view);
  if (gerr != k_ra8_ok) {
    return gerr;
  }
  /* Drop the pin now: the cell is resident but evictable, so a wrong read-ahead
   * guess ages out before hot data is displaced by a pinned request. */
  return ra8_keycache_put(kc, view.data);
}
 
ra8_err_t ra8_keycache_put(ra8_keycache_t* kc, const uint8_t* data)
{
  RA8_CHECK_NULL_PTR(kc, s_tag, "kc must not be nullptr");
  RA8_CHECK_NULL_PTR(data, s_tag, "data must not be nullptr");
  const uintptr_t base = (uintptr_t)kc->cfg.cell_mem;
  const uintptr_t addr = (uintptr_t)data;
  if (addr < base) {
    return k_ra8_err_invalid_arg;
  }
  const uintptr_t off  = addr - base;
  const uintptr_t span = (uintptr_t)kc->cfg.cell_count * (uintptr_t)kc->cfg.cell_bytes;
  if (off >= span) {
    return k_ra8_err_invalid_arg;
  }
  if ((off % (uintptr_t)kc->cfg.cell_bytes) != 0U) {
    return k_ra8_err_invalid_arg;
  }
  const uint32_t idx = (uint32_t)(off / (uintptr_t)kc->cfg.cell_bytes);
  if (kc->cfg.meta[idx].pin_count == 0U) {
    return k_ra8_err_invalid_arg;
  }
  kc->cfg.meta[idx].pin_count--;
  return k_ra8_ok;
}
 
ra8_err_t ra8_keycache_stats(const ra8_keycache_t* kc,
                             uint32_t*             out_hits,
                             uint32_t*             out_misses,
                             uint32_t*             out_evictions)
{
  RA8_CHECK_NULL_PTR(kc, s_tag, "kc must not be nullptr");
  if (kc->cfg.cell_mem == nullptr) {
    return k_ra8_err_invalid_state;
  }
  if (out_hits != nullptr) {
    *out_hits = kc->hits;
  }
  if (out_misses != nullptr) {
    *out_misses = kc->misses;
  }
  if (out_evictions != nullptr) {
    *out_evictions = kc->evictions;
  }
  return k_ra8_ok;
}