progs/perftest.c: Use from Glibc syscall numbers.

[catacomb] / base / rsvr.c

/* -*-c-*-
 *
 * Reservoir and buffer handling
 *
 * (c) 2017 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software: you can redistribute it and/or modify it
 * under the terms of the GNU Library General Public License as published
 * by the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb.  If not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 * USA.
 */

/*----- Header files ------------------------------------------------------*/

#include <assert.h>
#include <stdlib.h>
#include <string.h>

#include "rsvr.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @rsvr_mkplan@ --- *
 *
 * Arguments:   @rsvr_plan *plan@ = pointer to plan to fill in
 *              @const rsvr_policy *pol@ = reservoir policy to follow
 *              @size_t used@ = amount of data in the reservoir
 *              @size_t insz@ = amount of fresh input data arriving
 *
 * Returns:     ---
 *
 * Use:         Prepares a plan for feeding input data into a block-oriented
 *              operation.
 *
 *              The caller's code for following the plan proceeds in four
 *              parts.
 *
 *                1. Insert the first @plan->head@ input items into the
 *                   reservoir; there will be sufficient space, and
 *                   @plan->head@ will be at most @pol->blksz@.
 *
 *                2. Process the first @plan->from_rsvr@ items from the
 *                   reservoir, shifting the remaining items forward;
 *                   @plan->from_rsvr@ will be a multiple of @pol->blksz@.
 *
 *                3. Process the next @plan->from_input@ items directly from
 *                   the input; @plan->from_input@ will be a multiple of
 *                   @pol->blksz@.
 *
 *                4. Insert the remaining @plan->tail@ input items into the
 *                   reservoir for next time.
 */

void rsvr_mkplan(rsvr_plan *plan, const rsvr_policy *pol,
                 size_t used, size_t insz)
{
  unsigned extra = !!(pol->f&RSVRF_FULL);
  unsigned n, final;

  if (insz < pol->rsvrsz - used + extra) {
    /* Easy case: there's enough space in the reservoir for the whole input,
     * so just accumulate it and we're done.
     */

    plan->head = insz;
    plan->from_rsvr = plan->from_input = plan->tail = 0;
  } else {
    /* The hard case.  We're going to have to actually process something. */

    /* Firstly, we top the reservoir up to the next block boundary. */
    n = (pol->rsvrsz - used)%pol->blksz;
    plan->head = n; used += n; insz -= n;

    /* Next, figure out the final amount we'll leave in the reservoir.  This
     * will be congruent to USED, modulo the block size, and within the last
     * BLKSZ-wide interval permitted.  We must have enough material to get
     * here, or we'd be in the other branch above.
     */
    final = pol->rsvrsz - pol->blksz + extra +
      (insz + pol->blksz - extra)%pol->blksz;

    /* If we don't have enough input to drain the reservoir completely, and
     * then top it up to the necessary level, then take as much as we can
     * from the reservoir; otherwise, drain completely and then use up the
     * remaining input directly.
     */
    if (insz < final) {
      /* We don't have enough input to drain the reservoir completely and
       * then top it up to the necessary final level.  Take what we can.
       */

      plan->from_rsvr = used + insz - final;
      plan->from_input = 0;
      plan->tail = insz;
    } else {
      /* We have lots of input.  Drain the reservoir fully, process the bulk
       * of the input buffer, and load the rest into the reservoir at the
       * end.
       */

      plan->from_rsvr = used;
      plan->from_input = insz - final;
      plan->tail = final;
    }
  }
}

/* --- @rsvr_setup@ --- *
 *
 * Arguments:   @rsvr_state *st@ = pointer to state structure to fill in
 *              @const rsvr_policy *pol@ = reservoir policy to follow
 *              @void *rsvr@ = pointer to the actual reservoir
 *              @unsigned *used@ = pointer to the reservoir level
 *              @const void *in@ = pointer to the input data
 *              @size_t insz@ = size of the input
 *
 * Returns:     ---
 *
 * Use:         Prepares for a simple operation.  This performs the initial
 *              copy of input data into the reservoir, and prepares for the
 *              next step.
 *
 *              After this, the calling code should usually proceed as
 *              follows.
 *
 *                1. Call @RSVR_NEXT@ in a sequence of loops, with
 *                   successively smaller values of @n@, to process waiting
 *                   data from the reservoir.  Usually, each @n@ will be some
 *                   multiple of the block size @pol->blksz@, and the final
 *                   loop will have @n = pol->blksz@.
 *
 *                2. Call @rsvr_done@ to indicate that this has been done.
 *
 *                3. Call @RSVR_NEXT@ in a sequence of loops, as in step 1,
 *                   to process the remaining data from the input buffer.
 *
 *                4. Call @rsvr_done@ to indicate that the job is complete.
 */

void rsvr_setup(rsvr_state *st, const rsvr_policy *pol,
                void *rsvr, unsigned *used, const void *in, size_t insz)
{
  rsvr_mkplan(&st->plan, pol, *used, insz);
  st->rsvr = rsvr; st->in = in; st->used = used;

  if (st->plan.head) {
    memcpy(rsvr + *st->used, st->in, st->plan.head);
    *st->used += st->plan.head; st->in += st->plan.head;
  }
  st->src = RSVRSRC_RSVR; st->p = st->rsvr; st->sz = st->plan.from_rsvr;
}

/* --- @RSVR_NEXT@, @rsvr_next@ --- *
 *
 * Arguments:   @rsvr_state *st@ = pointer to the state structure
 *              @size_t n@ = amount of input data required, in bytes; should
 *                      usually be a multiple of @pol->blksz@
 *
 * Returns:     A pointer to the next @n@ bytes of input, or null if there is
 *              insufficient data remaining.
 */

const void *rsvr_next(rsvr_state *st, size_t n) { return RSVR_NEXT(st, n); }

/* --- @rsvr_done@ --- *
 *
 * Arguments:   @rsvr_state *st@ = pointer to the state structure
 *
 * Returns:     Zero after the first pass, nonzero after the second.
 *
 * Use:         Reports that the first or second stage (see @rsvr_setup@
 *              above) of an operation has been completed.
 *
 *              If the first stage is complete, then this shifts stuff about
 *              in the reservoir and prepares for the second stage; if the
 *              second stage is complete, then it copies the remaining input
 *              into the reservoir and marks the state as complete.
 */

int rsvr_done(rsvr_state *st)
{
  assert(!st->sz);
  switch (st->src) {
    case RSVRSRC_RSVR:
      if (st->plan.from_rsvr) {
        if (st->plan.from_rsvr < *st->used) {
          memmove(st->rsvr, st->rsvr + st->plan.from_rsvr,
                  *st->used - st->plan.from_rsvr);
        }
        *st->used -= st->plan.from_rsvr;
      }
      st->src = RSVRSRC_INPUT;
      st->p = st->in; st->sz = st->plan.from_input;
      return (0);
    case RSVRSRC_INPUT:
      if (st->plan.tail) {
        memcpy(st->rsvr + *st->used, st->p, st->plan.tail);
        *st->used += st->plan.tail;
      }
      st->src = RSVRSRC_DONE;
      st->p = 0; st->sz = 0;
      return (1);
    default:
      abort();
  }
}

/*----- Testing -----------------------------------------------------------*/

#ifdef TEST_RIG

#include <ctype.h>
#include <errno.h>
#include <stdio.h>

#include <mLib/alloc.h>
#include <mLib/bits.h>
#include <mLib/darray.h>
#include <mLib/macros.h>
#include <mLib/report.h>
#include <mLib/testrig.h>

struct rng {
  uint32 x;
};

static void init_rng(struct rng *r)
  { r->x = 0; }

static void step_rng(struct rng *r)
  { r->x = U32(0x0d83c207*r->x + 0x380fcfea); }

DA_DECL(uint_v, unsigned);

struct testinfo {
  rsvr_policy pol;
  uint_v chunksz;
  uint_v blksz;
  unsigned used;
  size_t off;
  int ok;
};

static void show_uint_v(const char *what, const uint_v *v)
{
  size_t i;

  printf("\t%s:", what);
  for (i = 0; i < DA_LEN(v); i++) printf("%s%u", i ? ", " : " ", DA(v)[i]);
  printf("\n");
}

static void report_policy(const struct rsvr_policy *pol)
{
  printf("\tpolicy: flags = 0x%08x%s; blksz = %u; rsvrsz = %u\n",
         pol->f, pol->f&RSVRF_FULL ? " full" : pol->f ? "" : " nil",
         pol->blksz, pol->rsvrsz);
}

static void report_testinfo(const struct testinfo *info)
{
  report_policy(&info->pol);
  show_uint_v("chunksz", &info->chunksz);
  show_uint_v("blksz", &info->blksz);
  printf("\treservoir level = %u\n", info->used);
  printf("\toffset = %lu\n", (unsigned long)info->off);
}

static void check(struct rng *r, struct testinfo *info,
                  const void *p, size_t sz)
{
  const octet *q = p;
  unsigned x;

  while (sz) {
    x = U8(r->x);
    if (info->ok && *q != x) {
      printf("\n*** FAIL data mismatch (0x%02x /= 0x%02x)\n", *q, x);
      report_testinfo(info);
      info->ok = 0;
    }
    q++; sz--; info->off++;
    step_rng(r);
  }
}

static void parse_intlist(uint_v *v, const char *p)
{
  char *q;
  unsigned long n;
  int e = errno;

  for (;;) {
    while (ISSPACE(*p)) p++;
    if (!*p) break;
    if (*p == ',') p++;
    while (ISSPACE(*p)) p++;
    errno = 0; n = strtoul(p, &q, 0);
    if (errno || (*q && *q != ',' && !ISSPACE(*q)))
      die(1, "invalid int list");
    p = q; DA_PUSH(v, n);
  }
  errno = e;
}

int vrfy_plan(dstr *dv)
{
  rsvr_policy pol;
  rsvr_plan want, calc;
  unsigned used;
  size_t insz;
  int ok = 1;

  pol.f = *(unsigned long *)dv[0].buf;
  pol.blksz = *(unsigned long *)dv[1].buf;
  pol.rsvrsz = *(unsigned long *)dv[2].buf;
  used = *(unsigned long *)dv[3].buf;
  insz = *(unsigned long *)dv[4].buf;
  want.head = *(unsigned long *)dv[5].buf;
  want.from_rsvr = *(unsigned long *)dv[6].buf;
  want.from_input = *(unsigned long *)dv[7].buf;
  want.tail = *(unsigned long *)dv[8].buf;

  rsvr_mkplan(&calc, &pol, used, insz);

  if (want.head != calc.head ||
      want.from_rsvr != calc.from_rsvr ||
      want.from_input != calc.from_input ||
      want.tail != calc.tail) {
    printf("\n*** FAIL plan doesn't match\n");
    report_policy(&pol);
    printf("\treservoir level = %u\n", used);
    printf("\tinput size = %lu\n", (unsigned long)insz);
#define SHOW(what, slot) do {                                           \
  printf("\t" what " (calc) %lu %s %lu (want)\n",                       \
         (unsigned long)calc.slot,                                      \
         calc.slot == want.slot ? "=" : "/=",                           \
         (unsigned long)want.slot);                                     \
} while(0)
    SHOW("head", head);
    SHOW("from reservoir", from_rsvr);
    SHOW("from input", from_input);
    SHOW("tail", tail);
#undef SHOW
    ok = 0;
  }

  return (ok);
}

static int vrfy_copy(dstr *dv)
{
  struct testinfo info;
  rsvr_state st;
  struct rng ra, rb;
  octet *buf = 0, *rsvr;
  const void *p;
  size_t i, j, bsz = 0;
  unsigned n, used0, lb, ub, fin;

  init_rng(&ra); init_rng(&rb);
  info.pol.f = *(unsigned long *)dv[0].buf;
  info.pol.blksz = *(unsigned long *)dv[1].buf;
  info.pol.rsvrsz = *(unsigned long *)dv[2].buf;
  info.ok = 1; info.used = 0; info.off = 0;
  rsvr = xmalloc(info.pol.rsvrsz);
  DA_CREATE(&info.chunksz); parse_intlist(&info.chunksz, dv[3].buf);
  DA_CREATE(&info.blksz); parse_intlist(&info.blksz, dv[4].buf);
  for (i = 0; i < DA_LEN(&info.chunksz); i++)
    if (bsz < DA(&info.chunksz)[i]) bsz = DA(&info.chunksz)[i];
  buf = xmalloc(bsz);
  for (i = 0; i < DA_LEN(&info.chunksz); i++) {
    n = DA(&info.chunksz)[i];
    for (j = 0; j < n; j++) { buf[j] = U8(ra.x); step_rng(&ra); }
    used0 = info.used;
    rsvr_setup(&st, &info.pol, rsvr, &info.used, buf, n);
    if (n != st.plan.head + st.plan.from_input + st.plan.tail) {
      printf("\n*** FAIL input size crosscheck "
             "(%u /= %u + %lu + %u = %lu)\n",
             n,
             st.plan.head, (unsigned long)st.plan.from_input, st.plan.tail,
             (unsigned long)(st.plan.head +
                             st.plan.from_input +
                             st.plan.tail));
      report_testinfo(&info);
      info.ok = 0;
    }
    if (st.plan.from_rsvr%info.pol.blksz) {
      printf("\n*** FAIL reservoir chunk %u misaligned\n",
             st.plan.from_rsvr);
      report_testinfo(&info);
      info.ok = 0;
    }
    if (st.plan.from_input%info.pol.blksz) {
      printf("\n*** FAIL direct chunk %lu misaligned\n",
             (unsigned long)st.plan.from_input);
      report_testinfo(&info);
      info.ok = 0;
    }
    if (st.plan.head > info.pol.rsvrsz - used0) {
      printf("\n*** FAIL top-up out of range (%u + %u = %u > %u)\n",
             used0, st.plan.head, used0 + st.plan.head, info.pol.rsvrsz);
      report_testinfo(&info);
      info.ok = 0;
    }
    if (st.plan.from_rsvr > used0 + st.plan.head) {
      printf("\n*** FAIL shift out of range (%u > %u + %u = %u)\n",
             st.plan.from_rsvr,
             used0, st.plan.head, used0 + st.plan.head);
      report_testinfo(&info);
      info.ok = 0;
    }
    if (st.plan.head != n) {
      ub = info.pol.rsvrsz + !!(info.pol.f&RSVRF_FULL);
      lb = ub - info.pol.blksz;
      fin = used0 + st.plan.head - st.plan.from_rsvr + st.plan.tail;
      if (lb > fin) {
        printf("\n*** FAIL final level out of bounds "
               "(%u > %u = %u + %u - %u + %u)\n",
               lb, fin,
               used0, st.plan.head, st.plan.from_rsvr, st.plan.tail);
        report_testinfo(&info);
        info.ok = 0;
      }
      if (fin >= ub) {
        printf("\n*** FAIL final level out of bounds "
               "(%u + %u - %u + %u = %u >= %u)\n",
               used0, st.plan.head, st.plan.from_rsvr, st.plan.tail,
               fin, ub);
        report_testinfo(&info);
        info.ok = 0;
      }
    }

    if (!info.ok) break;
    RSVR_DO(&st) {
      for (j = 0; j < DA_LEN(&info.blksz); j++) {
        n = DA(&info.blksz)[j];
        while ((p = RSVR_NEXT(&st, n)) != 0) check(&rb, &info, p, n);
      }
    }
  }

  DA_DESTROY(&info.chunksz);
  DA_DESTROY(&info.blksz);
  xfree(rsvr); xfree(buf);
  return (info.ok);
}

static const struct test_chunk tests[] = {
  { "plan", vrfy_plan,
    { &type_ulong, &type_ulong, &type_ulong, &type_ulong, &type_ulong,
      &type_ulong, &type_ulong, &type_ulong, &type_ulong } },
  { "copy", vrfy_copy,
    { &type_ulong, &type_ulong, &type_ulong, &type_string, &type_string } },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  test_run(argc, argv, tests, SRCDIR "/t/rsvr");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/