fuzz_memorypool.c

Go to the documentation of this file.

/*
  This file is part of libmicrohttpd
  Copyright (C) 2026 Christian Grothoff
 
  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
 
  This library 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
  Lesser General Public License for more details.
 
  You should have received a copy of the GNU Lesser General Public
  License along with this library.
  If not, see <http://www.gnu.org/licenses/>.
*/
 
#define FUZZ_HARNESS_NAME "fuzz_memorypool"
#include "fuzz_common.h"
 
/* internal.h pulls in MHD_config.h and <microhttpd.h> in the right
   order; including <microhttpd.h> first would redefine _MHD_EXTERN. */
#include "internal.h"
#include "memorypool.h"
 
 
#define FZ_ALIGN_SIZE (2 * sizeof (void *))
 
#ifdef MHD_ASAN_POISON_ACTIVE
#define FZ_RED_ZONE_SIZE FZ_ALIGN_SIZE
#else  /* ! MHD_ASAN_POISON_ACTIVE */
#define FZ_RED_ZONE_SIZE ((size_t) 0)
#endif /* ! MHD_ASAN_POISON_ACTIVE */
 
#define FZ_MAX_BLOCKS 24
 
#define FZ_MAX_OPS 64
 
#define FZ_PAT_MAX 96
 
static const size_t fz_pool_sizes[] = {
  1, 15, 16, 17, 32, 48, 64, 96, 128, 129, 192, 256, 320, 384, 512,
  768, 1024, 1400, 1500, 2048, 4096, 8192, 16384, 32768, 65536, 131072
};
 
#define FZ_NUM_POOL_SIZES \
  (sizeof (fz_pool_sizes) / sizeof (fz_pool_sizes[0]))
 
 
enum fz_op
{
  FZ_OP_ALLOC = 0,       
  FZ_OP_ALLOC_ALL,       
  FZ_OP_TRY_ALLOC,       
  FZ_OP_SQUEEZE,         
  FZ_OP_REALLOC,         
  FZ_OP_REALLOC_NEW,     
  FZ_OP_DEALLOC,         
  FZ_OP_RESET,           
  FZ_OP_GET_FREE,        
  FZ_OP_RESIZABLE,       
  FZ_OP_VERIFY,          
  FZ_OP_RECREATE,        
  FZ_OP_COUNT
};
 
 
struct fz_block
{
  uint8_t *ptr;
 
  size_t size;
 
  uint8_t tag;
 
  bool from_end;
};
 
 
struct fz_pool
{
  struct MemoryPool *pool;
 
  uint8_t *base;
 
  size_t cap;
 
  struct fz_block blk[FZ_MAX_BLOCKS];
 
  unsigned int nblk;
 
  uint8_t next_tag;
 
  bool paranoid;
};
 
 
static int full_dealloc_enabled;
 
static int wrap_realloc_enabled;
 
static int known_bugs_read;
 
static unsigned long stat_ops;
static unsigned long stat_alloc_ok;
static unsigned long stat_alloc_fail;
static unsigned long stat_realloc_moved;
static unsigned long stat_resets;
 
 
static void
print_stats (void)
{
  if (! fuzz_verbose)
    return;
  fprintf (stderr,
           "%s: ops=%lu allocations=%lu (failed %lu) "
           "moved reallocations=%lu resets=%lu\n",
           FUZZ_HARNESS_NAME,
           stat_ops, stat_alloc_ok, stat_alloc_fail,
           stat_realloc_moved, stat_resets);
}
 
 
static void
fz_report (const char *op,
           const char *what)
{
  char msg[256];
 
  (void) snprintf (msg, sizeof (msg), "%s: %s", op, what);
  fuzz_report_finding (msg);
}
 
 
static size_t
fz_round (size_t n)
{
  return (n + (FZ_ALIGN_SIZE - 1)) / FZ_ALIGN_SIZE * FZ_ALIGN_SIZE;
}
 
 
static uint8_t
fz_pat (uint8_t tag,
        size_t idx)
{
  return (uint8_t) ((((unsigned int) tag) * 131u)
                    + ((unsigned int) (idx * 17u))
                    + 0x5Au);
}
 
 
static void
fz_fill (uint8_t *ptr,
         uint8_t tag,
         size_t from,
         size_t to)
{
  size_t i;
 
  if (to > FZ_PAT_MAX)
    to = FZ_PAT_MAX;
  for (i = from; i < to; i++)
    ptr[i] = fz_pat (tag, i);
}
 
 
static void
fz_verify (const uint8_t *ptr,
           size_t size,
           uint8_t tag,
           const char *op,
           const char *what)
{
  size_t n = (size < FZ_PAT_MAX) ? size : (size_t) FZ_PAT_MAX;
  uint8_t *expect;
  size_t i;
 
  if (0 == n)
    return;
  expect = (uint8_t *) malloc (n);
  if (NULL == expect)
    abort ();
  for (i = 0; i < n; i++)
    expect[i] = fz_pat (tag, i);
  if (0 != memcmp (expect, ptr, n))
    fz_report (op, what);
  free (expect);
}
 
 
static void
fz_verify_all (struct fz_pool *st,
               const char *op)
{
  unsigned int i;
 
  for (i = 0; i < st->nblk; i++)
    fz_verify (st->blk[i].ptr,
               st->blk[i].size,
               st->blk[i].tag,
               op,
               "the contents of a live allocation changed");
}
 
 
static void
fz_check_ptr (struct fz_pool *st,
              void *p,
              size_t size,
              const char *op)
{
  const uint8_t *up = (const uint8_t *) p;
  size_t off;
  unsigned int i;
 
  if ( (up < st->base) ||
       (up > st->base + st->cap) )
  {
    fz_report (op, "returned a pointer outside of the pool");
    return;
  }
  off = (size_t) (up - st->base);
  if ( (size > st->cap) ||
       (off + size > st->cap) )
    fz_report (op, "returned a block that extends past the end of the pool");
  if (0 != (off % FZ_ALIGN_SIZE))
    fz_report (op, "returned a misaligned pointer");
  if (0 == size)
    return;
  for (i = 0; i < st->nblk; i++)
  {
    const uint8_t *q = st->blk[i].ptr;
 
    if (0 == st->blk[i].size)
      continue;
    if ( (up < q + st->blk[i].size) &&
         (q < up + size) )
    {
      fz_report (op, "returned a block overlapping another live allocation");
      return;
    }
  }
}
 
 
static void
fz_check_invariants (struct fz_pool *st,
                     const char *op)
{
  size_t total = 0;
  size_t freem;
  unsigned int i;
 
  freem = MHD_pool_get_free (st->pool);
  if (freem > st->cap)
    fz_report (op, "MHD_pool_get_free() exceeds the size of the pool");
  for (i = 0; i < st->nblk; i++)
    total += st->blk[i].size;
  if (total > st->cap)
    fz_report (op, "the live allocations alone exceed the size of the pool");
  else if (total + freem > st->cap)
    fz_report (op,
               "the live allocations plus the free space exceed the size "
               "of the pool");
  if (st->paranoid)
    fz_verify_all (st, op);
}
 
 
static struct fz_block *
fz_add (struct fz_pool *st,
        void *ptr,
        size_t size,
        bool from_end)
{
  struct fz_block *b = &st->blk[st->nblk++];
 
  b->ptr = (uint8_t *) ptr;
  b->size = size;
  b->tag = st->next_tag++;
  b->from_end = from_end;
  fz_fill (b->ptr, b->tag, 0, size);
  return b;
}
 
 
static void
fz_del (struct fz_pool *st,
        struct fz_block *b)
{
  *b = st->blk[--st->nblk];
}
 
 
static struct fz_block *
fz_pick (struct fz_pool *st,
         uint8_t sel,
         bool front_only)
{
  unsigned int i;
  unsigned int n = 0;
  unsigned int idx;
 
  for (i = 0; i < st->nblk; i++)
  {
    if ( (! front_only) ||
         (! st->blk[i].from_end) )
      n++;
  }
  if (0 == n)
    return NULL;
  idx = ((unsigned int) sel) % n;
  for (i = 0; i < st->nblk; i++)
  {
    if ( (front_only) &&
         (st->blk[i].from_end) )
      continue;
    if (0 == idx)
      return &st->blk[i];
    idx--;
  }
  return NULL; /* unreachable */
}
 
 
static size_t
fz_size (uint8_t sel,
         size_t cap,
         size_t freem)
{
  size_t d;
 
  switch (sel & 0x03)
  {
  case 0:
    return (size_t) (sel >> 2);              /* 0 .. 63 */
  case 1:
    return (((size_t) ((sel >> 2) + 1)) * cap) / 64u;
  case 2:
    d = (size_t) ((sel >> 2) & 0x07u);
    if (0 != (sel & 0x20))
      return freem + d;
    return (freem > d) ? (freem - d) : 0;
  default:
    return SIZE_MAX - (size_t) (sel >> 2);
  }
}
 
 
static void
fz_pool_close (struct fz_pool *st)
{
  MHD_pool_destroy (st->pool);
  st->pool = NULL;
  st->nblk = 0;
}
 
 
static bool
fz_pool_open (struct fz_pool *st,
              uint8_t sel)
{
  size_t max = fz_pool_sizes[((size_t) sel) % FZ_NUM_POOL_SIZES];
  void *base;
 
  st->nblk = 0;
  st->pool = MHD_pool_create (max);
  if (NULL == st->pool)
    return false;
  st->cap = MHD_pool_get_free (st->pool) + FZ_RED_ZONE_SIZE;
  if (st->cap != fz_round (max))
    fz_report ("MHD_pool_create",
               "a fresh pool does not offer the requested size rounded "
               "up to the alignment");
  /* MHD_pool_reset() with nothing to keep returns the start of the
     pool; connection.c:3021 relies on exactly this call.  It is the
     only way to learn the base address through the public interface. */
  base = MHD_pool_reset (st->pool, NULL, 0, 0);
  if (NULL == base)
  {
    fz_report ("MHD_pool_reset", "returned NULL for an empty pool");
    fz_pool_close (st);
    return false;
  }
  st->base = (uint8_t *) base;
  return true;
}
 
 
/* ------------------------------------------------------------------ */
/* The individual operations                                           */
/* ------------------------------------------------------------------ */
 
static void
fz_op_alloc (struct fz_pool *st,
             const uint8_t *op,
             bool prefer_end)
{
  static const char *const nm[2] = { "MHD_pool_allocate",
                                     "MHD_pool_allocate (from_end)" };
  const bool from_end = (0 != (op[1] & 0x01)) || prefer_end;
  const char *name = nm[from_end ? 1 : 0];
  size_t freem;
  size_t after;
  size_t size;
  void *p;
 
  if (st->nblk >= FZ_MAX_BLOCKS)
    return;
  freem = MHD_pool_get_free (st->pool);
  size = fz_size (op[2], st->cap, freem);
  p = MHD_pool_allocate (st->pool, size, from_end);
  after = MHD_pool_get_free (st->pool);
  if (NULL == p)
  {
    stat_alloc_fail++;
    if (after != freem)
      fz_report (name, "a failed allocation changed the amount of free space");
    if ( (0 != fz_round (size)) &&
         (fz_round (size) <= freem) )
      fz_report (name,
                 "allocation failed although MHD_pool_get_free() reported "
                 "room for it");
    return;
  }
  stat_alloc_ok++;
  if (after > freem)
    fz_report (name, "MHD_pool_get_free() increased across an allocation");
  else if (freem - after < size)
    fz_report (name,
               "MHD_pool_get_free() dropped by less than the allocated size");
  fz_check_ptr (st, p, size, name);
  (void) fz_add (st, p, size, from_end);
}
 
 
static void
fz_op_alloc_all (struct fz_pool *st,
                 const uint8_t *op)
{
  static const char name[] = "MHD_pool_allocate (all free)";
  const bool from_end = (0 != (op[1] & 0x01));
  size_t freem;
  void *p;
 
  if (st->nblk >= FZ_MAX_BLOCKS)
    return;
  freem = MHD_pool_get_free (st->pool);
  if (0 == freem)
    return;
  p = MHD_pool_allocate (st->pool, freem, from_end);
  if (NULL == p)
  {
    stat_alloc_fail++;
    fz_report (name,
               "allocating exactly MHD_pool_get_free() bytes failed");
    return;
  }
  stat_alloc_ok++;
  fz_check_ptr (st, p, freem, name);
  if (0 != MHD_pool_get_free (st->pool))
    fz_report (name,
               "the pool still reports free space after all of it was "
               "allocated");
  (void) fz_add (st, p, freem, from_end);
}
 
 
static void
fz_op_try_alloc (struct fz_pool *st,
                 const uint8_t *op)
{
  static const char name[] = "MHD_pool_try_alloc";
  size_t freem;
  size_t after;
  size_t size;
  size_t need;
  void *p;
 
  if (st->nblk >= FZ_MAX_BLOCKS)
    return;
  freem = MHD_pool_get_free (st->pool);
  size = fz_size (op[2], st->cap, freem);
  need = 0x5A5A5A5Au; /* poor man's "was it written at all" */
  p = MHD_pool_try_alloc (st->pool, size, &need);
  after = MHD_pool_get_free (st->pool);
  if (NULL == p)
  {
    stat_alloc_fail++;
    if (after != freem)
      fz_report (name, "a failed allocation changed the amount of free space");
    if (0 == need)
      fz_report (name,
                 "the allocation failed but no additional memory is "
                 "reported to be required");
    else if ( (SIZE_MAX != need) &&
              (need > st->cap) )
      fz_report (name,
                 "more memory is reported to be required than the pool "
                 "has in total");
    if ( (0 != fz_round (size)) &&
         (fz_round (size) <= freem) )
      fz_report (name,
                 "allocation failed although MHD_pool_get_free() reported "
                 "room for it");
    return;
  }
  stat_alloc_ok++;
  if (0 != need)
    fz_report (name,
               "the allocation succeeded but required_bytes was not "
               "cleared");
  if (after > freem)
    fz_report (name, "MHD_pool_get_free() increased across an allocation");
  else if (freem - after < size)
    fz_report (name,
               "MHD_pool_get_free() dropped by less than the allocated size");
  fz_check_ptr (st, p, size, name);
  /* try_alloc always allocates "from the end" */
  (void) fz_add (st, p, size, true);
}
 
 
static void
fz_op_squeeze (struct fz_pool *st,
               const uint8_t *op)
{
  static const char name[] = "MHD_pool_try_alloc (squeeze)";
  size_t size;
  size_t need = 0;
  size_t need2 = 0;
  void *p;
  unsigned int i;
  struct fz_block *victim = NULL;
 
  if (st->nblk >= FZ_MAX_BLOCKS)
    return;
  size = fz_size (op[2], st->cap, MHD_pool_get_free (st->pool));
  p = MHD_pool_try_alloc (st->pool, size, &need);
  if (NULL != p)
  {
    fz_check_ptr (st, p, size, name);
    (void) fz_add (st, p, size, true);
    return;
  }
  if ( (0 == need) ||
       (SIZE_MAX == need) )
    return;
  for (i = 0; i < st->nblk; i++)
  {
    if (st->blk[i].from_end)
      continue;
    if (st->blk[i].size < need)
      continue;
    if (! MHD_pool_is_resizable_inplace (st->pool,
                                         st->blk[i].ptr,
                                         st->blk[i].size))
      continue;
    victim = &st->blk[i];
    break;
  }
  if (NULL == victim)
    return;
  {
    const size_t new_size = victim->size - need;
    void *shrunk = MHD_pool_reallocate (st->pool,
                                        victim->ptr,
                                        victim->size,
                                        new_size);
 
    if (NULL == shrunk)
    {
      fz_report (name,
                 "shrinking a block that is resizable in-place failed");
      return;
    }
    if (shrunk != victim->ptr)
      fz_report (name,
                 "shrinking a block that is resizable in-place moved it");
    victim->ptr = (uint8_t *) shrunk;
    victim->size = new_size;
    fz_verify (victim->ptr, victim->size, victim->tag, name,
               "shrinking a block damaged its contents");
  }
  p = MHD_pool_try_alloc (st->pool, size, &need2);
  if (NULL == p)
  {
    fz_report (name,
               "the allocation still fails after freeing the number of "
               "bytes that required_bytes asked for");
    return;
  }
  fz_check_ptr (st, p, size, name);
  (void) fz_add (st, p, size, true);
}
 
 
static void
fz_op_realloc (struct fz_pool *st,
               const uint8_t *op)
{
  static const char name[] = "MHD_pool_reallocate";
  struct fz_block *b = fz_pick (st, op[1], true);
  struct fz_block saved;
  size_t freem;
  size_t after;
  size_t new_size;
  bool inplace;
  void *p;
 
  if (NULL == b)
    return;
  freem = MHD_pool_get_free (st->pool);
  new_size = fz_size (op[2], st->cap, freem);
  if ( (0 == b->size) &&
       (new_size > SIZE_MAX - FZ_ALIGN_SIZE) &&
       (! wrap_realloc_enabled) )
    return; /* open finding F2, see above */
  inplace = MHD_pool_is_resizable_inplace (st->pool, b->ptr, b->size);
  saved = *b;
  p = MHD_pool_reallocate (st->pool, b->ptr, b->size, new_size);
  after = MHD_pool_get_free (st->pool);
  if (NULL == p)
  {
    /* "old continues to be valid for old_size" */
    if (after != freem)
      fz_report (name,
                 "a failed reallocation changed the amount of free space");
    fz_verify (saved.ptr, saved.size, saved.tag, name,
               "a failed reallocation damaged the old block");
    if ( (inplace) &&
         (new_size <= saved.size + freem) )
      fz_report (name,
                 "reallocation failed although the block is resizable "
                 "in-place and the pool has the required free space");
    return;
  }
  if ( (inplace) &&
       (p != saved.ptr) )
    fz_report (name,
               "a block that MHD_pool_is_resizable_inplace() accepted was "
               "moved");
  if ( (new_size >= saved.size) &&
       (after > freem) )
    fz_report (name,
               "MHD_pool_get_free() increased across a growing "
               "reallocation");
  /* the old location is gone as far as the model is concerned */
  fz_del (st, b);
  if (p != saved.ptr)
    stat_realloc_moved++;
  fz_check_ptr (st, p, new_size, name);
  fz_verify ((const uint8_t *) p,
             (new_size < saved.size) ? new_size : saved.size,
             saved.tag,
             name,
             "reallocation did not preserve the contents of the block");
  b = &st->blk[st->nblk++];
  b->ptr = (uint8_t *) p;
  b->size = new_size;
  b->tag = saved.tag;
  b->from_end = false;
  if (new_size > saved.size)
    fz_fill (b->ptr, b->tag, saved.size, new_size);
}
 
 
static void
fz_op_realloc_new (struct fz_pool *st,
                   const uint8_t *op)
{
  static const char name[] = "MHD_pool_reallocate (fresh)";
  size_t freem;
  size_t size;
  void *p;
 
  if (st->nblk >= FZ_MAX_BLOCKS)
    return;
  freem = MHD_pool_get_free (st->pool);
  size = fz_size (op[2], st->cap, freem);
  p = MHD_pool_reallocate (st->pool, NULL, 0, size);
  if (NULL == p)
  {
    stat_alloc_fail++;
    if ( (0 != fz_round (size)) &&
         (fz_round (size) <= freem) )
      fz_report (name,
                 "allocation failed although MHD_pool_get_free() reported "
                 "room for it");
    return;
  }
  stat_alloc_ok++;
  if (MHD_pool_get_free (st->pool) > freem)
    fz_report (name, "MHD_pool_get_free() increased across an allocation");
  fz_check_ptr (st, p, size, name);
  (void) fz_add (st, p, size, false);
}
 
 
static void
fz_op_dealloc (struct fz_pool *st,
               const uint8_t *op)
{
  static const char name[] = "MHD_pool_deallocate";
  struct fz_block *b = fz_pick (st, op[1], false);
  size_t freem;
  size_t after;
 
  freem = MHD_pool_get_free (st->pool);
  if ( (NULL != b) &&
       (b->from_end) &&
       (0 != b->size) &&
       (0 == freem) &&
       (! full_dealloc_enabled) )
  {
    /* See the comment on full_dealloc_enabled: this is an open finding,
       not a precondition of MHD_pool_deallocate().  The lowest-addressed
       live "from the end" block of non-zero size starts exactly at
       pool->end, which for a full pool is also pool->pos -- the
       ambiguous case.  Any block above it is unaffected, so only that
       one block is spared.  Zero-sized blocks do not count: they consume
       nothing, so they can sit below pool->end once a later
       deallocation has moved pool->end back up past them. */
    unsigned int i;
 
    for (i = 0; i < st->nblk; i++)
    {
      if ( (st->blk[i].from_end) &&
           (0 != st->blk[i].size) &&
           (st->blk[i].ptr < b->ptr) )
        break;
    }
    if (i == st->nblk)
      return;
  }
  if (NULL == b)
  {
    MHD_pool_deallocate (st->pool, NULL, 0);
  }
  else
  {
    fz_verify (b->ptr, b->size, b->tag, name,
               "the contents of the block changed before it was freed");
    MHD_pool_deallocate (st->pool, b->ptr, b->size);
    fz_del (st, b);
  }
  after = MHD_pool_get_free (st->pool);
  if (after < freem)
    fz_report (name, "deallocation reduced the amount of free space");
}
 
 
static void
fz_op_reset (struct fz_pool *st,
             const uint8_t *op)
{
  static const char name[] = "MHD_pool_reset";
  struct fz_block *b = fz_pick (st, (uint8_t) (op[1] & 0x0F), false);
  size_t new_size;
  size_t copy;
  uint8_t tag = 0;
  void *p;
 
  new_size = fz_size (op[2], st->cap, MHD_pool_get_free (st->pool));
  if (new_size > st->cap)
    new_size = st->cap;
  copy = 0;
  if (NULL != b)
  {
    copy = (b->size * ((size_t) (op[1] >> 4))) / 15u;
    if (copy > b->size)
      copy = b->size;
    if (copy > new_size)
      copy = new_size;
    tag = b->tag;
    fz_verify (b->ptr, b->size, b->tag, name,
               "the contents of the kept block changed before the reset");
  }
  p = MHD_pool_reset (st->pool,
                      (NULL != b) ? b->ptr : NULL,
                      copy,
                      new_size);
  stat_resets++;
  /* every allocation is gone now */
  st->nblk = 0;
  if (NULL == p)
  {
    fz_report (name, "returned NULL");
    return;
  }
  fz_check_ptr (st, p, new_size, name);
  fz_verify ((const uint8_t *) p, copy, tag, name,
             "the kept bytes did not survive the reset");
  b = fz_add (st, p, new_size, false);
  /* fz_add() has just re-tagged and re-filled the whole block */
}
 
 
static void
fz_op_resizable (struct fz_pool *st,
                 const uint8_t *op)
{
  static const char name[] = "MHD_pool_is_resizable_inplace";
  struct fz_block *b = fz_pick (st, op[1], false);
  bool r;
 
  if ( (NULL == b) ||
       (0 != (op[1] & 0x80)) )
  {
    if (MHD_pool_is_resizable_inplace (st->pool, NULL, 0))
      fz_report (name, "an unallocated block is reported as resizable");
    return;
  }
  r = MHD_pool_is_resizable_inplace (st->pool, b->ptr, b->size);
  if ( (r) &&
       (b->from_end) &&
       (0 != b->size) )
    fz_report (name,
               "a block allocated from the end is reported as resizable "
               "in-place");
  if (! r)
    return;
  /* A block that is resizable in-place must survive a resize to its own
     size without moving; connection.c asserts this after every such
     reallocation. */
  {
    void *p = MHD_pool_reallocate (st->pool, b->ptr, b->size, b->size);
 
    if (NULL == p)
      fz_report (name,
                 "reallocating a resizable block to its own size failed");
    else if (p != b->ptr)
      fz_report (name,
                 "reallocating a resizable block to its own size moved it");
  }
}
 
 
static void
fz_do_op (struct fz_pool *st,
          const uint8_t *op,
          bool prefer_end)
{
  const char *name = "operation";
 
  stat_ops++;
  switch ((enum fz_op) (op[0] % (uint8_t) FZ_OP_COUNT))
  {
  case FZ_OP_ALLOC:
    fz_op_alloc (st, op, prefer_end);
    break;
  case FZ_OP_ALLOC_ALL:
    fz_op_alloc_all (st, op);
    break;
  case FZ_OP_TRY_ALLOC:
    fz_op_try_alloc (st, op);
    break;
  case FZ_OP_SQUEEZE:
    fz_op_squeeze (st, op);
    break;
  case FZ_OP_REALLOC:
    fz_op_realloc (st, op);
    break;
  case FZ_OP_REALLOC_NEW:
    fz_op_realloc_new (st, op);
    break;
  case FZ_OP_DEALLOC:
    fz_op_dealloc (st, op);
    break;
  case FZ_OP_RESET:
    fz_op_reset (st, op);
    break;
  case FZ_OP_GET_FREE:
    name = "MHD_pool_get_free";
    break;
  case FZ_OP_RESIZABLE:
    fz_op_resizable (st, op);
    break;
  case FZ_OP_VERIFY:
    name = "verify";
    fz_verify_all (st, name);
    break;
  case FZ_OP_RECREATE:
    fz_pool_close (st);
    if (! fz_pool_open (st, op[1]))
      return;
    break;
  case FZ_OP_COUNT:
  default:
    break;
  }
  fz_check_invariants (st, name);
}
 
 
int
LLVMFuzzerTestOneInput (const uint8_t *data,
                        size_t size)
{
  static bool inited = false;
  struct fz_pool st;
  size_t nops;
  size_t i;
 
  if (size < 5)
    return 0;
  if (! inited)
  {
    inited = true;
    /* Sets the page size used by MHD_pool_create(); MHD does this once
       from MHD_start_daemon(). */
    MHD_init_mem_pools_ ();
    (void) atexit (&print_stats);
  }
  if (! known_bugs_read)
  {
    const char *e;
 
    known_bugs_read = 1;
    e = getenv ("MHD_FUZZ_POOL_FULL_DEALLOC");
    if (NULL != e)
      full_dealloc_enabled = (0 != atoi (e));
    e = getenv ("MHD_FUZZ_POOL_WRAP_REALLOC");
    if (NULL != e)
      wrap_realloc_enabled = (0 != atoi (e));
  }
  memset (&st, 0, sizeof (st));
  st.paranoid = (0 != (data[1] & 0x01));
  if (! fz_pool_open (&st, data[0]))
    return 0;
  nops = (size - 2) / 3;
  if (nops > FZ_MAX_OPS)
    nops = FZ_MAX_OPS;
  for (i = 0; i < nops; i++)
  {
    if (NULL == st.pool)
      break;
    fz_do_op (&st, data + 2 + 3 * i, (0 != (data[1] & 0x02)));
  }
  fz_verify_all (&st, "final");
  fz_pool_close (&st);  /* MHD_pool_destroy() tolerates a NULL pool */
  return 0;
}
 
 
/* ------------------------------------------------------------------ */
/* Generator                                                           */
/* ------------------------------------------------------------------ */
 
static const uint8_t gen_ops[] = {
  FZ_OP_ALLOC, FZ_OP_ALLOC, FZ_OP_ALLOC, FZ_OP_ALLOC,
  FZ_OP_ALLOC_ALL,
  FZ_OP_TRY_ALLOC, FZ_OP_TRY_ALLOC,
  FZ_OP_SQUEEZE, FZ_OP_SQUEEZE,
  FZ_OP_REALLOC, FZ_OP_REALLOC, FZ_OP_REALLOC, FZ_OP_REALLOC,
  FZ_OP_REALLOC_NEW,
  FZ_OP_DEALLOC, FZ_OP_DEALLOC, FZ_OP_DEALLOC,
  FZ_OP_RESET,
  FZ_OP_GET_FREE,
  FZ_OP_RESIZABLE, FZ_OP_RESIZABLE,
  FZ_OP_VERIFY,
  FZ_OP_RECREATE
};
 
 
static uint8_t
gen_size_sel (struct fuzz_rng *rng)
{
  const uint32_t k = fuzz_below (rng, 100);
  uint32_t d;
  uint32_t sign;
 
  if (k < 35)                                  /* tiny */
    return (uint8_t) ((fuzz_below (rng, 64) << 2) | 0u);
  if (k < 60)                                  /* fraction of the pool */
    return (uint8_t) ((fuzz_below (rng, 64) << 2) | 1u);
  if (k < 95)
  {                                            /* around the free space */
    /* Two statements, not one expression: the order in which the
       operands of '|' are evaluated is unspecified, and both calls
       advance the PRNG, so a single expression would make the generated
       stream compiler-dependent. */
    d = fuzz_below (rng, 8);
    sign = fuzz_below (rng, 2);
    return (uint8_t) ((d << 2) | (sign << 5) | 2u);
  }
  return (uint8_t) ((fuzz_below (rng, 64) << 2) | 3u);   /* value wrap */
}
 
 
static size_t
fuzz_generate (struct fuzz_rng *rng,
               uint8_t *buf,
               size_t cap)
{
  size_t len = 0;
  unsigned int nops;
  unsigned int i;
  unsigned int psel;
  uint8_t flags = 0;
 
  if (cap < 8)
    return 0;
  /* Small pools are where the interesting paths are, so bias towards
     them, but keep the whole table reachable. */
  if (fuzz_chance (rng, 3))
    psel = fuzz_below (rng, (uint32_t) FZ_NUM_POOL_SIZES);
  else
    psel = fuzz_below (rng, 16);
  buf[len++] = (uint8_t) psel;
  /* One PRNG call per statement, see gen_size_sel(). */
  if (fuzz_chance (rng, 4))
    flags |= 0x01;
  if (fuzz_chance (rng, 8))
    flags |= 0x02;
  buf[len++] = flags;
  nops = 1 + fuzz_below (rng, FZ_MAX_OPS);
  for (i = 0; i < nops; i++)
  {
    if (len + 3 > cap)
      break;
    buf[len++] = gen_ops[fuzz_below (rng, (uint32_t) (sizeof (gen_ops)))];
    buf[len++] = fuzz_byte (rng);
    buf[len++] = gen_size_sel (rng);
  }
  return len;
}
 
 
/* ------------------------------------------------------------------ */
/* Seed corpus                                                         */
/* ------------------------------------------------------------------ */
 
/* Size selectors, see fz_size() */
#define SZ_TINY(n)    ((uint8_t) ((((unsigned int) (n)) << 2) | 0u))
#define SZ_FRAC(k)    ((uint8_t) ((((unsigned int) (k)) << 2) | 1u))
#define SZ_FREE       ((uint8_t) 2u)
#define SZ_FREE_M(d)  ((uint8_t) ((((unsigned int) (d)) << 2) | 2u))
#define SZ_FREE_P(d)  ((uint8_t) ((((unsigned int) (d)) << 2) | 0x20u | 2u))
#define SZ_HUGE       ((uint8_t) 3u)
 
/* Pool size selectors, indices into fz_pool_sizes[] */
#define PS_1     0
#define PS_16    2
#define PS_32    4
#define PS_64    6
#define PS_128   8
#define PS_256   11
#define PS_512   14
#define PS_1024  16
#define PS_1500  18
#define PS_32768 23
 
#define OPR(o,b,s) ((uint8_t) (o)), ((uint8_t) (b)), (s)
 
static const uint8_t seed_grow_shrink[] = {
  PS_512, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (32)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (63)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (8)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_FRAC (32)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (1)),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_two_blocks_realloc[] = {
  PS_256, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (17)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (23)),
  /* the first block is no longer the last one: it has to move */
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (60)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_REALLOC, 0x01, SZ_TINY (40)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_from_end[] = {
  PS_128, 0x01,
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (16)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (1)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (16)),
  OPR (FZ_OP_RESIZABLE, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (16))
};
 
static const uint8_t seed_fill_exactly[] = {
  PS_128, 0x01,
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (16)),
  OPR (FZ_OP_ALLOC_ALL, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_GET_FREE, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (1)),
  OPR (FZ_OP_TRY_ALLOC, 0x00, SZ_TINY (1))
};
 
static const uint8_t seed_squeeze[] = {
  PS_512, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (40)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (7)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_FRAC (8))
};
 
static const uint8_t seed_squeeze_small[] = {
  PS_128, 0x01,
  OPR (FZ_OP_REALLOC_NEW, 0x00, SZ_FREE_M (2)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (17)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (17)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (17))
};
 
static const uint8_t seed_reset_keep[] = {
  PS_1500, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (60)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (12)),
  OPR (FZ_OP_RESET, 0xF0, SZ_FRAC (31)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_RESET, 0xF0, SZ_TINY (4)),
  OPR (FZ_OP_RESET, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_reset_full[] = {
  PS_256, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_FRAC (63)),
  OPR (FZ_OP_RESET, 0xF0, SZ_FRAC (63)),
  OPR (FZ_OP_RESET, 0xF0, SZ_FREE_P (1)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_boundary[] = {
  PS_64, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_FREE_M (1)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_ALLOC, 0x01, SZ_FREE_P (1)),
  OPR (FZ_OP_TRY_ALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_FREE)
};
 
static const uint8_t seed_wrap[] = {
  PS_256, 0x00,
  OPR (FZ_OP_ALLOC, 0x00, SZ_HUGE),
  OPR (FZ_OP_ALLOC, 0x01, SZ_HUGE),
  OPR (FZ_OP_TRY_ALLOC, 0x00, SZ_HUGE),
  OPR (FZ_OP_REALLOC_NEW, 0x00, SZ_HUGE),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (16)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_HUGE),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_tiny_pool[] = {
  PS_1, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (1)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (1)),
  OPR (FZ_OP_GET_FREE, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_RESET, 0xF0, SZ_TINY (1)),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_zero_sizes[] = {
  PS_32, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (0)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (4)),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_RESET, 0x00, SZ_TINY (0))
};
 
static const uint8_t seed_many_small[] = {
  PS_1500, 0x01,
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (5)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (5)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (5)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (5)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (5)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (5)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (33)),
  OPR (FZ_OP_REALLOC, 0x01, SZ_TINY (33)),
  OPR (FZ_OP_DEALLOC, 0x02, SZ_TINY (0)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_TINY (5))
};
 
static const uint8_t seed_recreate[] = {
  PS_32768, 0x00,
  OPR (FZ_OP_ALLOC, 0x00, SZ_FRAC (60)),
  OPR (FZ_OP_RECREATE, PS_16, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_RECREATE, PS_512, SZ_TINY (0)),
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (24)),
  OPR (FZ_OP_RESET, 0xF0, SZ_FRAC (2))
};
 
/* The read-buffer life cycle of a connection: allocate the read buffer,
   grow it to everything that is free, put the parsed headers "at the
   end", shrink the read buffer to what was actually received, then
   reset the pool keeping the received bytes -- connection.c does
   exactly this for every keep-alive request. */
static const uint8_t seed_connection_cycle[] = {
  PS_1500, 0x01,
  OPR (FZ_OP_REALLOC_NEW, 0x00, SZ_FRAC (31)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_TRY_ALLOC, 0x00, SZ_TINY (12)),
  OPR (FZ_OP_TRY_ALLOC, 0x00, SZ_TINY (20)),
  OPR (FZ_OP_SQUEEZE, 0x00, SZ_TINY (40)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_TINY (60)),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_RESET, 0xF0, SZ_FRAC (31)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_FREE),
  OPR (FZ_OP_VERIFY, 0x00, SZ_TINY (0))
};
 
 
/* The reproducer of the open finding described at full_dealloc_enabled:
   a 128 byte pool, one 16 byte block "from the end", the whole rest of
   the pool allocated from the front, then that first block released.
   Inert unless MHD_FUZZ_POOL_FULL_DEALLOC=1 is set. */
static const uint8_t seed_dealloc_end_full[] = {
  PS_128, 0x01,
  OPR (FZ_OP_ALLOC, 0x01, SZ_TINY (16)),
  OPR (FZ_OP_ALLOC_ALL, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_DEALLOC, 0x00, SZ_TINY (0))
};
 
 
/* The reproducer of the open finding F2: MHD_pool_reset() with nothing
   to keep leaves a zero-length block at the front boundary, and
   reallocating that to SIZE_MAX wraps.  Inert unless
   MHD_FUZZ_POOL_WRAP_REALLOC=1 is set. */
static const uint8_t seed_realloc_wrap[] = {
  PS_1024, 0x01,
  OPR (FZ_OP_RESET, 0x00, SZ_TINY (0)),
  OPR (FZ_OP_REALLOC, 0x00, SZ_HUGE)
};
 
 
struct mp_seed
{
  const uint8_t *bytes;
  size_t len;
};
 
#define MSEED(a) { (a), sizeof (a) }
 
static const struct mp_seed mp_seeds[] = {
  MSEED (seed_grow_shrink),
  MSEED (seed_two_blocks_realloc),
  MSEED (seed_from_end),
  MSEED (seed_fill_exactly),
  MSEED (seed_squeeze),
  MSEED (seed_squeeze_small),
  MSEED (seed_reset_keep),
  MSEED (seed_reset_full),
  MSEED (seed_boundary),
  MSEED (seed_wrap),
  MSEED (seed_tiny_pool),
  MSEED (seed_zero_sizes),
  MSEED (seed_many_small),
  MSEED (seed_recreate),
  MSEED (seed_connection_cycle),
  MSEED (seed_dealloc_end_full),
  MSEED (seed_realloc_wrap)
};
 
 
static size_t
fuzz_seed_count (void)
{
  return sizeof (mp_seeds) / sizeof (mp_seeds[0]);
}
 
 
static const uint8_t *
fuzz_seed_get (size_t idx,
               size_t *len)
{
  *len = mp_seeds[idx].len;
  return mp_seeds[idx].bytes;
}