From: Mark Wooding Date: Fri, 5 Jan 2018 04:31:08 +0000 (+0000) Subject: base/rsvr.[ch]: New hack for buffering input to block-oriented functions. X-Git-Tag: 2.5.0~14^2~40 X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/28363d2cd517811c538dcdfcd0a205dc3bd2bffe base/rsvr.[ch]: New hack for buffering input to block-oriented functions. --- diff --git a/base/Makefile.am b/base/Makefile.am index c9560ca2..8de4d69c 100644 --- a/base/Makefile.am +++ b/base/Makefile.am @@ -29,6 +29,8 @@ include $(top_srcdir)/vars.am noinst_LTLIBRARIES = libbase.la libbase_la_SOURCES = +TEST_LIBS = libbase.la + ###-------------------------------------------------------------------------- ### Component files. @@ -55,6 +57,12 @@ libbase_la_SOURCES += lmem.c ## Clearing secrets from memory. pkginclude_HEADERS += paranoia.h +## Reservoir handling. +pkginclude_HEADERS += rsvr.h +libbase_la_SOURCES += rsvr.c +TESTS += rsvr.t$(EXEEXT) +EXTRA_DIST += t/rsvr + ## Base definitions for assembler source. EXTRA_DIST += asm-common.h diff --git a/base/rsvr.c b/base/rsvr.c new file mode 100644 index 00000000..a468db76 --- /dev/null +++ b/base/rsvr.c @@ -0,0 +1,481 @@ +/* -*-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 +#include +#include + +#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 +#include +#include + +#include +#include +#include +#include +#include + +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((unsigned char)*p)) p++; + if (!*p) break; + if (*p == ',') p++; + while (isspace((unsigned char)*p)) p++; + errno = 0; n = strtoul(p, &q, 0); + if (errno || (*q && *q != ',' && !isspace((unsigned char)*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 -------------------------------------------------*/ diff --git a/base/rsvr.h b/base/rsvr.h new file mode 100644 index 00000000..9fb9c0a6 --- /dev/null +++ b/base/rsvr.h @@ -0,0 +1,195 @@ +/* -*-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. + */ + +#ifndef CATACOMB_RSVR_H +#define CATACOMB_RSVR_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct rsvr_policy { + unsigned f; /* Flags... */ +#define RSVRF_FULL 1u /* Hold back a full reservoir */ + unsigned blksz; /* Block size */ + unsigned rsvrsz; /* Reservoir size; multiple of + * @blksz@ */ +} rsvr_policy; + +typedef struct rsvr_plan { + unsigned head; /* First, accumulate @head@ bytes + * into the reservoir */ + unsigned from_rsvr; /* Next, process @from_rsvr@ bytes + * from the reservoir */ + size_t from_input; /* Then, process @from_input@ bytes + * directly from the input */ + unsigned tail; /* Finally, accumulate the remaining + * @tail@ bytes of input into the + * reservoir */ +} rsvr_plan; + +enum { RSVRSRC_RSVR, RSVRSRC_INPUT, RSVRSRC_DONE }; + +typedef struct rsvr_state { + rsvr_plan plan; + unsigned *used; + unsigned char *rsvr; + const unsigned char *in, *p; + size_t sz; + unsigned src; +} rsvr_state; + +/*----- Functions provided ------------------------------------------------*/ + +/* --- @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. + */ + +extern void rsvr_mkplan(rsvr_plan */*plan*/, const rsvr_policy */*pol*/, + size_t /*used*/, size_t /*insz*/); + +/* --- @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. + */ + +extern void rsvr_setup(rsvr_state */*st*/, const rsvr_policy */*pol*/, + void */*rsvr*/, unsigned */*used*/, + const void */*in*/, size_t /*insz*/); + +/* --- @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. + */ + +#define RSVR_NEXT(st, n) \ + ((n) > (st)->sz \ + ? 0 \ + : ((st)->sz -= (n), \ + (st)->p += (n), \ + (const void *)((st)->p - (n)))) +extern const void *rsvr_next(rsvr_state */*st*/, size_t /*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. + */ + +extern int rsvr_done(rsvr_state */*st*/); + +/* --- @RSVR_DO@ --- * + * + * Arguments: @st@ = pointer to state structure + * + * Use: Invoke as @RSVR_DO(st) stmt@: performs two passes of @stmt@ + * over the reservoir and input buffers respectively. + */ + +#define RSVR_DO(st) switch (0) while (!rsvr_done(st)) case 0: + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/base/t/rsvr b/base/t/rsvr new file mode 100644 index 00000000..188adb38 --- /dev/null +++ b/base/t/rsvr @@ -0,0 +1,26 @@ +### -*-conf-*- +### Tests for reservoir management. + +plan { + ## F BLKSZ RSVRSZ USED INSZ HEAD FROM-RSVR FROM-INPUT TAIL + 0 8 8 0 0 0 0 0 0; + 0 8 8 0 1 1 0 0 0; + 0 8 8 7 1 1 8 0 0; + 1 8 8 7 1 1 0 0 0; + 0 8 8 0 16 0 0 16 0; + 0 8 8 1 15 7 8 8 0; + 1 8 8 1 15 7 8 0 8; + 0 8 8 1 16 7 8 8 1; + 1 8 8 1 16 7 8 8 1; + + 0 8 8 0 1 1 0 0 0; + 0 8 8 1 4 4 0 0 0; + 0 8 8 5 7 3 8 0 4; + 0 8 8 4 31 4 8 24 3; + 0 8 8 3 5 5 8 0 0; +} + +copy { + ## F BLKSZ RSVRSZ CHUNKSZ,... BLKSZ,... + 0 8 8 1,4,7,31,5 16,8; +}