trace.c

Go to the documentation of this file.

#include "trace.h"
 
#include <errno.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
 
#include "ra8_attributes.h"
 
typedef enum : uint32_t {
  k_cb_obj_book       = 1U,       
  k_cb_obj_comic      = 2U,       
  k_cb_footprint      = 8192U,    
  k_cb_accesses       = 120000U,  
  k_cb_hot_pages      = 96U,      
  k_cb_reread_pct     = 82U,      
  k_cb_jump_pct       = 4U,       
  k_cb_tile_span      = 6144U,    
  k_cb_sr_hot         = 192U,     
  k_cb_sr_hot_pass    = 3U,       
  k_cb_sr_scan        = 1500U,    
  k_cb_pct_full       = 100U,     
  k_cb_mixed_phase    = 2048U,    
  k_cb_huge_footprint = 1835008U, 
  k_cb_huge_hot       = 256U,     
  k_cb_huge_hot_pass  = 3U,       
  k_cb_huge_scan      = 4000U,    
} cb_workload_dim_t;
 
typedef enum : uint8_t {
  k_rng_shift_a       = 13U, 
  k_rng_shift_b       = 7U,  
  k_rng_shift_c       = 17U, 
  k_cb_base_dec       = 10U, 
  k_cb_key_high_shift = 24U, 
} cb_trace_math_t;
 
typedef enum : uint64_t {
  k_rng_seed_random  = 0x9E3779B97F4A7C15ULL, 
  k_rng_seed_reread  = 0xD1B54A32D192ED03ULL, 
  k_rng_seed_toc     = 0x2545F4914F6CDD1DULL, 
  k_rng_seed_mixed_a = 0x9E3779B97F4A7C15ULL, 
  k_rng_seed_mixed_b = 0xABCDEF1234567890ULL, 
  k_cb_hash_offset   = 0xCBF29CE484222325ULL, 
  k_cb_hash_prime    = 0x100000001B3ULL,      
} cb_trace_seed_t;

RA8_INTERNAL
static uint64_t internal_rng(uint64_t* state)
{
  uint64_t value = *state;
  value ^= value << (uint8_t)k_rng_shift_a;
  value ^= value >> (uint8_t)k_rng_shift_b;
  value ^= value << (uint8_t)k_rng_shift_c;
  *state = value;
  return value;
}

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

RA8_INTERNAL
static uint64_t internal_trace_hash(uint64_t hash, cb_key_t key)
{
  const uint8_t bytes[sizeof(key)] = {
    (uint8_t)key.object_id,
    (uint8_t)(key.object_id >> 8U),
    (uint8_t)(key.object_id >> 16U),
    (uint8_t)(key.object_id >> (uint8_t)k_cb_key_high_shift),
    (uint8_t)key.page,
    (uint8_t)(key.page >> 8U),
    (uint8_t)(key.page >> 16U),
    (uint8_t)(key.page >> (uint8_t)k_cb_key_high_shift),
  };
  for (size_t i = 0U; i < sizeof(bytes); ++i) {
    hash ^= bytes[i];
    hash *= (uint64_t)k_cb_hash_prime;
  }
  return hash;
}
 
void cb_traces_synthetic(cb_trace_t out[k_cb_synthetic_trace_count])
{
  static const char* const names[k_cb_synthetic_trace_count] = {
    "seq-pageturn",
    "random",
    "reread-locality",
    "linear+jumps",
    "cbz-scroll",
    "hotset+scan",
    "hugebook-7GiB",
    "mixed-session",
  };
  static const uint32_t footprints[k_cb_synthetic_trace_count] = {
    k_cb_footprint,
    k_cb_footprint,
    k_cb_footprint,
    k_cb_footprint,
    k_cb_tile_span,
    k_cb_footprint,
    k_cb_huge_footprint,
    k_cb_footprint,
  };
  for (uint8_t i = 0U; i < (uint8_t)k_cb_synthetic_trace_count; ++i) {
    out[i] = (cb_trace_t){.name      = names[i],
                          .n         = (uint64_t)k_cb_accesses,
                          .footprint = footprints[i],
                          .kind      = (cb_trace_kind_t)i};
  }
}

RA8_INTERNAL
static cb_io_status_t internal_trace_read_byte(cb_trace_cursor_t* cursor, uint8_t* out, bool* eof)
{
  if (cursor->read_at == cursor->read_count) {
    if (cursor->source_offset >= cursor->trace->source.size) {
      *eof = true;
      return k_cb_io_ok;
    }
    size_t         count     = 0U;
    const uint64_t remaining = cursor->trace->source.size - cursor->source_offset;
    const size_t   request =
      (remaining < sizeof(cursor->read_buffer)) ? (size_t)remaining : sizeof(cursor->read_buffer);
    const cb_io_status_t status = cursor->trace->source.read(cursor->trace->source.ctx,
                                                             cursor->source_offset,
                                                             cursor->read_buffer,
                                                             request,
                                                             &count);
    if ((status != k_cb_io_ok) || (count == 0U) || (count > request)) {
      return (status == k_cb_io_ok) ? k_cb_io_fault : status;
    }
    cursor->source_offset += count;
    cursor->read_at    = 0U;
    cursor->read_count = count;
  }
  *out = cursor->read_buffer[cursor->read_at];
  cursor->read_at++;
  *eof = false;
  return k_cb_io_ok;
}

RA8_INTERNAL
static bool internal_parse_trace_line(const char* line, uint32_t* object_id, uint32_t* page)
{
  char* end                  = nullptr;
  errno                      = 0;
  const unsigned long object = strtoul(line, &end, (int)k_cb_base_dec);
  if ((end == line) || (errno != 0)) {
    return false;
  }
#if ULONG_MAX > UINT32_MAX
  if (object > (unsigned long)UINT32_MAX) {
    return false;
  }
#endif
  const char* second             = end;
  errno                          = 0;
  const unsigned long page_value = strtoul(second, &end, (int)k_cb_base_dec);
  if ((end == second) || (errno != 0)) {
    return false;
  }
#if ULONG_MAX > UINT32_MAX
  if (page_value > (unsigned long)UINT32_MAX) {
    return false;
  }
#endif
  *object_id = (uint32_t)object;
  *page      = (uint32_t)page_value;
  return true;
}

RA8_INTERNAL
static cb_io_status_t
internal_trace_captured_next(cb_trace_cursor_t* cursor, cb_key_t* key, bool* done)
{
  size_t length = 0U;
  bool   eof    = false;
  while ((length + 1U) < sizeof(cursor->line)) {
    uint8_t              value  = 0U;
    const cb_io_status_t status = internal_trace_read_byte(cursor, &value, &eof);
    if (status != k_cb_io_ok) {
      return status;
    }
    if (eof) {
      break;
    }
    cursor->line[length] = (char)value;
    length++;
    if (value == (uint8_t)'\n') {
      break;
    }
  }
  if ((length == 0U) && eof) {
    *done = true;
    return k_cb_io_ok;
  }
  cursor->line[length] = '\0';
  if (!internal_parse_trace_line(cursor->line, &key->object_id, &key->page)) {
    *done = true;
    return k_cb_io_ok;
  }
  *done = false;
  return k_cb_io_ok;
}

RA8_INTERNAL
static cb_key_t internal_trace_scan_key(uint64_t index, bool huge)
{
  const uint32_t hot       = huge ? (uint32_t)k_cb_huge_hot : (uint32_t)k_cb_sr_hot;
  const uint32_t passes    = huge ? (uint32_t)k_cb_huge_hot_pass : (uint32_t)k_cb_sr_hot_pass;
  const uint32_t scan      = huge ? (uint32_t)k_cb_huge_scan : (uint32_t)k_cb_sr_scan;
  const uint32_t footprint = huge ? (uint32_t)k_cb_huge_footprint : (uint32_t)k_cb_footprint;
  const uint64_t hot_span  = (uint64_t)hot * (uint64_t)passes;
  const uint64_t cycle     = hot_span + (uint64_t)scan;
  const uint64_t round     = index / cycle;
  const uint64_t pos       = index % cycle;
  const uint32_t page = (pos < hot_span)
                          ? (uint32_t)(pos % hot)
                          : hot + (uint32_t)(((uint64_t)hot + (round * scan) + (pos - hot_span)) %
                                             (uint64_t)(footprint - hot));
  return (cb_key_t){.object_id = k_cb_obj_book, .page = page};
}

RA8_INTERNAL
static cb_key_t internal_trace_synthetic_next(cb_trace_cursor_t* cursor)
{
  const uint64_t index = cursor->index;
  switch (cursor->trace->kind) {
    case k_cb_trace_seq:
      return (cb_key_t){.object_id = k_cb_obj_book,
                        .page      = (uint32_t)(index % (uint64_t)k_cb_footprint)};
    case k_cb_trace_random:
      return (cb_key_t){.object_id = k_cb_obj_book,
                        .page      = internal_rand_below(&cursor->rng, k_cb_footprint)};
    case k_cb_trace_reread: {
      uint32_t page = 0U;
      if (internal_rand_below(&cursor->rng, k_cb_pct_full) < k_cb_reread_pct) {
        page = cursor->hot + internal_rand_below(&cursor->rng, k_cb_hot_pages);
      } else {
        page        = internal_rand_below(&cursor->rng, k_cb_footprint);
        cursor->hot = (page < k_cb_hot_pages) ? 0U : (page - k_cb_hot_pages);
      }
      return (cb_key_t){.object_id = k_cb_obj_book, .page = page % k_cb_footprint};
    }
    case k_cb_trace_jumps:
      cursor->page = (internal_rand_below(&cursor->rng, k_cb_pct_full) < k_cb_jump_pct)
                       ? internal_rand_below(&cursor->rng, k_cb_footprint)
                       : (cursor->page + 1U) % k_cb_footprint;
      return (cb_key_t){.object_id = k_cb_obj_book, .page = cursor->page};
    case k_cb_trace_scroll:
      return (cb_key_t){.object_id = k_cb_obj_comic,
                        .page      = (uint32_t)(index % (uint64_t)k_cb_tile_span)};
    case k_cb_trace_scan:
      return internal_trace_scan_key(index, false);
    case k_cb_trace_huge:
      return internal_trace_scan_key(index, true);
    case k_cb_trace_mixed: {
      const uint32_t phase = (uint32_t)((index / k_cb_mixed_phase) % 4U);
      if (phase == 0U) {
        cursor->page = (cursor->page + 1U) % k_cb_footprint;
      } else if (phase == 1U) {
        cursor->page = cursor->hot + internal_rand_below(&cursor->rng, k_cb_hot_pages);
      } else if (phase == 2U) {
        cursor->page = internal_rand_below(&cursor->rng, k_cb_footprint);
        cursor->hot  = (cursor->page < k_cb_hot_pages) ? 0U : cursor->page - k_cb_hot_pages;
      } else {
        return (cb_key_t){.object_id = k_cb_obj_comic, .page = cursor->page % k_cb_tile_span};
      }
      return (cb_key_t){.object_id = k_cb_obj_book, .page = cursor->page % k_cb_footprint};
    }
    case k_cb_trace_captured:
      break;
  }
  return (cb_key_t){};
}
 
cb_io_status_t cb_trace_cursor_open(const cb_trace_t* trace, cb_trace_cursor_t* cursor)
{
  if ((trace == nullptr) || (cursor == nullptr)) {
    return k_cb_io_fault;
  }
  *cursor = (cb_trace_cursor_t){.trace = trace, .fingerprint = (uint64_t)k_cb_hash_offset};
  if (trace->kind == k_cb_trace_random) {
    cursor->rng = (uint64_t)k_rng_seed_random;
  } else if (trace->kind == k_cb_trace_reread) {
    cursor->rng = (uint64_t)k_rng_seed_reread;
  } else if (trace->kind == k_cb_trace_jumps) {
    cursor->rng = (uint64_t)k_rng_seed_toc;
  } else if (trace->kind == k_cb_trace_mixed) {
    cursor->rng = (uint64_t)k_rng_seed_mixed_a ^ (uint64_t)k_rng_seed_mixed_b;
  } else if ((trace->kind == k_cb_trace_captured) && (trace->source.read == nullptr)) {
    return k_cb_io_fault;
  }
  return k_cb_io_ok;
}
 
cb_io_status_t cb_trace_cursor_next(cb_trace_cursor_t* cursor, cb_key_t* key, bool* done)
{
  if ((cursor == nullptr) || (cursor->trace == nullptr) || (key == nullptr) || (done == nullptr)) {
    return k_cb_io_fault;
  }
  cb_io_status_t status = k_cb_io_ok;
  if (cursor->trace->kind == k_cb_trace_captured) {
    status = internal_trace_captured_next(cursor, key, done);
  } else {
    *done = cursor->index >= cursor->trace->n;
    if (!*done) {
      *key = internal_trace_synthetic_next(cursor);
    }
  }
  if ((status == k_cb_io_ok) && !*done) {
    cursor->fingerprint = internal_trace_hash(cursor->fingerprint, *key);
    cursor->index++;
  }
  return status;
}
 
cb_io_status_t cb_trace_cursor_finish(const cb_trace_cursor_t* cursor)
{
  if ((cursor == nullptr) || (cursor->trace == nullptr)) {
    return k_cb_io_fault;
  }
  if ((cursor->index != cursor->trace->n) ||
      ((cursor->trace->kind == k_cb_trace_captured) &&
       (cursor->fingerprint != cursor->trace->fingerprint))) {
    return k_cb_io_mutated;
  }
  return k_cb_io_ok;
}
 
cb_io_status_t
cb_trace_bind(const cb_source_t* source, const char* name, size_t name_length, cb_trace_t* out)
{
  if ((source == nullptr) || (source->read == nullptr) || (name == nullptr) || (out == nullptr) ||
      (name_length == 0U) || (name_length >= (size_t)k_cb_trace_name_capacity)) {
    return k_cb_io_capacity;
  }
  *out = (cb_trace_t){.kind = k_cb_trace_captured, .source = *source};
  memcpy(out->name_storage, name, name_length);
  out->name_storage[name_length] = '\0';
  out->name                      = out->name_storage;
  cb_trace_cursor_t cursor       = {};
  cb_io_status_t    status       = cb_trace_cursor_open(out, &cursor);
  bool              done         = false;
  while ((status == k_cb_io_ok) && !done) {
    cb_key_t key = {};
    status       = cb_trace_cursor_next(&cursor, &key, &done);
  }
  if ((status != k_cb_io_ok) || (cursor.index == 0U)) {
    *out = (cb_trace_t){};
    return (status == k_cb_io_ok) ? k_cb_io_fault : status;
  }
  out->n           = cursor.index;
  out->fingerprint = cursor.fingerprint;
  return k_cb_io_ok;
}