reader_vmem.c

Go to the documentation of this file.

 
#include <stddef.h>
#include <stdint.h>
#include <string.h>
 
#include "ra8_err.h"
#include "ra8_log.h"
#include "ra8_vmem.h"
#include "ra8_vsource.h"
#include "reader_vmem_internal.h"

typedef enum : uint32_t {
  k_rv_header_frames  = 4U,    
  k_rv_chapters       = 24U,   
  k_rv_chap_min_fr    = 8U,    
  k_rv_chap_span_fr   = 160U,  
  k_rv_backglance_pct = 12U,   
  k_rv_toc_rounds     = 600U,  
  k_rv_toc_read_fr    = 6U,    
  k_rv_sr_rounds      = 40U,   
  k_rv_sr_hot_pass    = 3U,    
  k_rv_sr_hot_fr      = 200U,  
  k_rv_sr_scan_fr     = 1200U, 
  k_rv_pct_base       = 100U,  
  k_rv_def_budget     = 256U,  
  k_rv_max_objs       = 2U,    
} rv_dimension_t;

typedef enum : uint32_t {
  k_rv_xs_shift_a     = 13U,         
  k_rv_xs_shift_b     = 7U,          
  k_rv_xs_shift_c     = 17U,         
  k_rv_fill_mul       = 2654435761U, 
  k_rv_fill_shift     = 24U,         
  k_rv_decimal_base   = 10U,         
  k_rv_rate_scale     = 10000U,      
  k_rv_rate_digits    = 2U,          
  k_rv_workspace_pads = 3U,          
} rv_constant_t;

typedef enum : uint64_t {
  k_rv_rng_seed = 0x9E3779B97F4A7C15ULL, 
} rv_seed_t;

typedef enum : uint64_t {
  k_rv_workspace_storage_bytes =
    ((uint64_t)READER_VMEM_MAX_BUDGET *
     ((uint64_t)k_rv_frame_bytes + sizeof(ra8_vmem_frame_t) + sizeof(ra8_vmem_key_t))) +
    ((uint64_t)k_rv_bucket_count * sizeof(int32_t)) +
    ((uint64_t)k_rv_workspace_pads * (_Alignof(max_align_t) - 1U)), 
} rv_storage_size_t;
 
static_assert(READER_VMEM_MAX_BUDGET > 0U);
static_assert(k_rv_workspace_storage_bytes <= SIZE_MAX);

typedef struct {
  alignas(max_align_t) uint8_t bytes[k_rv_workspace_storage_bytes];
} rv_workspace_storage_t;

static rv_workspace_storage_t s_reader_workspace;

typedef struct {
  uint32_t first; 
  uint32_t count; 
} rv_chapter_t;

typedef struct {
  uint64_t bytes; 
} rv_book_t;

typedef struct {
  rv_chapter_t chapters[k_rv_chapters]; 
  uint32_t     total_frames;            
  uint64_t     rng;                     
  ra8_vmem_t*  vm;                      
  rv_trace_t*  trace;                   
  uint32_t     object_id;               
  uint64_t     accesses;                
  bool         failed;                  
} rv_driver_t;
 
void ra8_log_emit_error(const char* tag, const char* message)
{
  priv_rv_diag("[ra8_log] ");
  priv_rv_diag(tag);
  priv_rv_diag(": ");
  priv_rv_diag(message);
  priv_rv_diag("\n");
}
 
void ra8_log_emit_error_val(const char* tag, const char* message, uint32_t value)
{
  priv_rv_diag("[ra8_log] ");
  priv_rv_diag(tag);
  priv_rv_diag(": ");
  priv_rv_diag(message);
  priv_rv_diag(" =");
  priv_rv_diag_u64(value);
  priv_rv_diag("\n");
}

RA8_INTERNAL static uint64_t internal_rng(uint64_t* state)
{
  uint64_t value = *state;
  value ^= value << (uint32_t)k_rv_xs_shift_a;
  value ^= value >> (uint32_t)k_rv_xs_shift_b;
  value ^= value << (uint32_t)k_rv_xs_shift_c;
  *state = value;
  return value;
}

RA8_INTERNAL static uint32_t internal_below(uint64_t* state, uint32_t span)
{
  return (span == 0U) ? 0U : (uint32_t)(internal_rng(state) % (uint64_t)span);
}

RA8_INTERNAL static ra8_err_t
internal_book_read(void* context, uint64_t offset, uint8_t* buffer, uint32_t length)
{
  const rv_book_t* book = (const rv_book_t*)context;
  if (book == nullptr || buffer == nullptr) {
    return k_ra8_err_null_ptr;
  }
  if (offset > book->bytes || (uint64_t)length > (book->bytes - offset)) {
    return k_ra8_err_out_of_range;
  }
  for (uint32_t i = 0U; i < length; ++i) {
    const uint64_t absolute = offset + i;
    buffer[i] = (uint8_t)((absolute * (uint64_t)k_rv_fill_mul) >> (uint32_t)k_rv_fill_shift);
  }
  return k_ra8_ok;
}

RA8_INTERNAL static void internal_layout_book(rv_driver_t* driver)
{
  uint32_t cursor = (uint32_t)k_rv_header_frames;
  for (uint32_t chapter = 0U; chapter < (uint32_t)k_rv_chapters; ++chapter) {
    const uint32_t count =
      (uint32_t)k_rv_chap_min_fr + internal_below(&driver->rng, (uint32_t)k_rv_chap_span_fr);
    driver->chapters[chapter] = (rv_chapter_t){.first = cursor, .count = count};
    cursor += count;
  }
  driver->total_frames = cursor;
}

RA8_INTERNAL static void internal_touch(rv_driver_t* driver, uint32_t frame)
{
  const uint64_t  offset = (uint64_t)frame * (uint64_t)k_rv_frame_bytes;
  void*           page   = nullptr;
  const ra8_err_t get    = ra8_vmem_get(driver->vm, driver->object_id, offset, &page);
  if (get == k_ra8_ok) {
    if (ra8_vmem_put(driver->vm, page) != k_ra8_ok) {
      driver->failed = true;
    }
  } else {
    priv_rv_diag("vm_get(frame ");
    priv_rv_diag_u64(frame);
    priv_rv_diag(") failed: ");
    priv_rv_diag_u64(get);
    priv_rv_diag("\n");
    driver->failed = true;
  }
  if (!priv_rv_trace_reference(driver->trace, driver->object_id, frame)) {
    driver->failed = true;
  }
  ++driver->accesses;
}

RA8_INTERNAL static void internal_touch_header(rv_driver_t* driver)
{
  for (uint32_t frame = 0U; frame < (uint32_t)k_rv_header_frames; ++frame) {
    internal_touch(driver, frame);
  }
}

RA8_INTERNAL static void internal_phase_linear(rv_driver_t* driver)
{
  for (uint32_t chapter = 0U; chapter < (uint32_t)k_rv_chapters; ++chapter) {
    const rv_chapter_t extent = driver->chapters[chapter];
    for (uint32_t index = 0U; index < extent.count; ++index) {
      const uint32_t frame = extent.first + index;
      internal_touch_header(driver);
      internal_touch(driver, frame);
      const bool glance =
        internal_below(&driver->rng, (uint32_t)k_rv_pct_base) < (uint32_t)k_rv_backglance_pct;
      if (glance && index > 0U) {
        internal_touch(driver, frame - 1U);
      }
    }
  }
}

RA8_INTERNAL static void internal_phase_toc(rv_driver_t* driver)
{
  for (uint32_t round = 0U; round < (uint32_t)k_rv_toc_rounds; ++round) {
    internal_touch_header(driver);
    const uint32_t     index  = internal_below(&driver->rng, (uint32_t)k_rv_chapters);
    const rv_chapter_t extent = driver->chapters[index];
    for (uint32_t page = 0U; page < (uint32_t)k_rv_toc_read_fr && page < extent.count; ++page) {
      internal_touch(driver, extent.first + page);
    }
  }
}

RA8_INTERNAL static void internal_phase_scan(rv_driver_t* driver)
{
  uint32_t scan_at = (uint32_t)k_rv_header_frames + (uint32_t)k_rv_sr_hot_fr;
  for (uint32_t round = 0U; round < (uint32_t)k_rv_sr_rounds; ++round) {
    for (uint32_t pass = 0U; pass < (uint32_t)k_rv_sr_hot_pass; ++pass) {
      for (uint32_t hot = 0U; hot < (uint32_t)k_rv_sr_hot_fr; ++hot) {
        internal_touch(driver, (uint32_t)k_rv_header_frames + hot);
      }
    }
    for (uint32_t scan = 0U; scan < (uint32_t)k_rv_sr_scan_fr; ++scan) {
      const uint32_t span  = driver->total_frames - (uint32_t)k_rv_header_frames;
      const uint32_t frame = (uint32_t)k_rv_header_frames + ((scan_at + scan) % span);
      internal_touch(driver, frame);
    }
    scan_at += (uint32_t)k_rv_sr_scan_fr;
  }
}

RA8_INTERNAL static bool internal_parse_budget(const char* text, uint32_t* budget)
{
  if (text == nullptr || text[0] == '\0') {
    return false;
  }
  uint64_t value = 0U;
  for (size_t i = 0U; text[i] != '\0'; ++i) {
    if (text[i] < '0' || text[i] > '9') {
      return false;
    }
    const uint32_t digit = (uint32_t)(text[i] - '0');
    if (value > ((UINT32_MAX - digit) / (uint32_t)k_rv_decimal_base)) {
      return false;
    }
    value = (value * (uint32_t)k_rv_decimal_base) + digit;
  }
  if (value == 0U) {
    return false;
  }
  *budget = (uint32_t)value;
  return true;
}

RA8_INTERNAL static bool internal_vmem_setup(ra8_vmem_t*           vm,
                                             const rv_workspace_t* workspace,
                                             uint32_t              budget,
                                             ra8_vsource_t*        sources)
{
  const ra8_vmem_cfg_t config = {.frame_mem    = workspace->frame_mem,
                                 .frame_bytes  = (uint32_t)k_rv_frame_bytes,
                                 .frame_count  = budget,
                                 .meta         = workspace->meta,
                                 .keys         = workspace->keys,
                                 .buckets      = workspace->buckets,
                                 .bucket_count = (uint32_t)k_rv_bucket_count,
                                 .loader       = ra8_vsource_loader,
                                 .loader_ctx   = sources};
  return ra8_vmem_init(vm, &config) == k_ra8_ok;
}

RA8_INTERNAL static void internal_report_rate(uint32_t hits, uint64_t accesses)
{
  uint64_t scaled = 0U;
  if (accesses != 0U) {
    scaled = (((uint64_t)hits * (uint64_t)k_rv_rate_scale) + (accesses / 2U)) / accesses;
  }
  priv_rv_diag_u64(scaled / (uint64_t)k_rv_pct_base);
  priv_rv_diag(".");
  const uint64_t fraction = scaled % (uint64_t)k_rv_pct_base;
  if (fraction < (uint64_t)k_rv_decimal_base) {
    priv_rv_diag("0");
  }
  priv_rv_diag_u64(fraction);
}

RA8_INTERNAL static void internal_report(const rv_driver_t* driver,
                                         const rv_book_t*   book,
                                         uint32_t           budget,
                                         const char*        trace_path,
                                         uint32_t           hits,
                                         uint32_t           misses,
                                         uint32_t           evictions)
{
  priv_rv_diag("reader_vmem: book=");
  priv_rv_diag_u64(driver->total_frames);
  priv_rv_diag(" frames (");
  priv_rv_diag_u64(book->bytes);
  priv_rv_diag(" bytes), budget=");
  priv_rv_diag_u64(budget);
  priv_rv_diag(" frames\n  accesses=");
  priv_rv_diag_u64(driver->accesses);
  priv_rv_diag("  trace=");
  priv_rv_diag(trace_path);
  priv_rv_diag("\n  ra8_vmem SLRU: hits=");
  priv_rv_diag_u64(hits);
  priv_rv_diag(" misses=");
  priv_rv_diag_u64(misses);
  priv_rv_diag(" evictions=");
  priv_rv_diag_u64(evictions);
  priv_rv_diag("  hit_rate=");
  internal_report_rate(hits, driver->accesses);
  priv_rv_diag("%\n");
}

RA8_INTERNAL static void internal_report_workspace(uint32_t budget, const rv_workspace_need_t* need)
{
  priv_rv_diag("reader_vmem: budget ");
  priv_rv_diag_u64(budget);
  priv_rv_diag(" requires ");
  priv_rv_diag_u64(need->total_bytes);
  priv_rv_diag(" workspace bytes; compiled max budget ");
  priv_rv_diag_u64(READER_VMEM_MAX_BUDGET);
  priv_rv_diag(" provides ");
  priv_rv_diag_u64(sizeof(s_reader_workspace.bytes));
  priv_rv_diag(" bytes\n");
}

RA8_INTERNAL static bool internal_prepare(uint32_t             budget,
                                          const rv_book_t*     book,
                                          rv_workspace_t*      workspace,
                                          ra8_vsource_t*       sources,
                                          ra8_vsource_obj_t    objects[k_rv_max_objs],
                                          uint32_t*            object_id,
                                          rv_workspace_need_t* need)
{
  if (!priv_rv_workspace_require(budget, need)) {
    priv_rv_diag("reader_vmem: invalid workspace requirement\n");
    return false;
  }
  if (budget > (uint32_t)READER_VMEM_MAX_BUDGET ||
      need->total_bytes > sizeof(s_reader_workspace.bytes)) {
    internal_report_workspace(budget, need);
    return false;
  }
  if (!priv_rv_workspace_bind(s_reader_workspace.bytes,
                              sizeof(s_reader_workspace.bytes),
                              need,
                              workspace) ||
      ra8_vsource_init(sources, objects, (uint32_t)k_rv_max_objs) != k_ra8_ok ||
      ra8_vsource_add_paged(sources, internal_book_read, (void*)book, 0U, book->bytes, object_id) !=
        k_ra8_ok) {
    priv_rv_diag("reader_vmem: cache workspace/source setup failed\n");
    return false;
  }
  return true;
}

RA8_INTERNAL static bool internal_execute(const char* trace_path, uint32_t budget)
{
  rv_driver_t driver = {.rng = (uint64_t)k_rv_rng_seed};
  internal_layout_book(&driver);
  const rv_book_t book = {
    .bytes = (uint64_t)driver.total_frames * (uint64_t)k_rv_frame_bytes,
  };
  rv_workspace_t      workspace              = {};
  rv_workspace_need_t need                   = {};
  ra8_vsource_obj_t   objects[k_rv_max_objs] = {};
  ra8_vsource_t       sources                = {};
  if (!internal_prepare(budget, &book, &workspace, &sources, objects, &driver.object_id, &need)) {
    return false;
  }
  ra8_vmem_t vm = {};
  if (!internal_vmem_setup(&vm, &workspace, budget, &sources)) {
    priv_rv_diag("reader_vmem: vmem setup failed\n");
    return false;
  }
  rv_trace_t trace = {};
  if (!priv_rv_trace_begin(trace_path, &trace)) {
    priv_rv_diag("reader_vmem: cannot open trace file ");
    priv_rv_diag(trace_path);
    priv_rv_diag("\n");
    return false;
  }
  driver.vm    = &vm;
  driver.trace = &trace;
  internal_phase_linear(&driver);
  internal_phase_toc(&driver);
  internal_phase_scan(&driver);
  uint32_t   hits      = 0U;
  uint32_t   misses    = 0U;
  uint32_t   evictions = 0U;
  const bool stats_ok  = ra8_vmem_stats(&vm, &hits, &misses, &evictions) == k_ra8_ok;
  const bool run_ok    = !driver.failed && stats_ok;
  if (!run_ok || !priv_rv_trace_commit(&trace)) {
    priv_rv_trace_abort(&trace);
    priv_rv_diag("reader_vmem: trace generation failed\n");
    return false;
  }
  internal_report(&driver, &book, budget, trace_path, hits, misses, evictions);
  return true;
}

RA8_INTERNAL static void internal_usage(void)
{
  priv_rv_diag("usage: reader_vmem [TRACE [FRAME_BUDGET]]\n");
  priv_rv_diag("compiled maximum frame budget: ");
  priv_rv_diag_u64(READER_VMEM_MAX_BUDGET);
  priv_rv_diag("\n");
}
 
int main(int argc, char** argv)
{
  if (argc > 3 || (argc > 1 && strcmp(argv[1], "--help") == 0)) {
    internal_usage();
    return (argc > 3) ? 2 : 0;
  }
  const char* trace_path = (argc > 1) ? argv[1] : "reader_vmem.trace";
  uint32_t    budget     = (uint32_t)k_rv_def_budget;
  if (argc > 2 && !internal_parse_budget(argv[2], &budget)) {
    internal_usage();
    return 2;
  }
  return internal_execute(trace_path, budget) ? 0 : 1;
}