root/1.8.3/trunk/src/chunk.c

/**
 * \file chunk.c
 *
 * \brief Chunk memory management system
 *
 * <h3>Synopsis:</h3>
 * The chunk memory management system has three goals: to reduce overall
 * memory consumption, to improve locality of reference, and to allow
 * less-used sections of memory to be paged out to disk.  These three
 * goals are accomplished by implementing an allocation management layer
 * on top of malloc(), with significantly reduced overhead and the ability
 * to rearrange allocations to actively control fragmentation and increase
 * locality.
 *
 *
 * <h3>Basic operation:</h3>
 * The managed memory pool is divided into regions of approximately 64KB.
 * These regions contain variable-size chunks representing allocated and
 * available (free) memory.  No individual allocation may be larger than
 * will fit in a single region, and no allocation may be smaller than one
 * byte.  Each chunk has between two and four bytes of overhead (indicating
 * the used/free status, the size of the chunk, and the number of
 * dereferences for the chunk), and each region has additional overhead
 * of about 42 bytes.
 *
 * Allocations are made with the chunk_create() call, which is given
 * the size of the data, the data value to be stored, and an initial
 * dereference count to be assigned to the chunk.  Once created, the
 * value of a chunk cannot be changed; the storage is immutable.
 * chunk_create() returns an integral reference value that can be
 * used to retrieve or free the allocation.
 *
 * Allocations are accessed with the chunk_fetch(), chunk_len(), and
 * chunk_derefs() calls.  Each of these if given a reference (as
 * returned by chunk_create()), and chunk_fetch() is additionally
 * given a buffer and length to fill with the allocated value.  Both
 * chunk_fetch() and chunk_len() increment a chunk's dereference
 * count (up to the maximum of 255), which is used in migration to
 * improve locality.
 *
 * Allocations are freed with the chunk_delete() call, which also
 * requires a reference as input.
 *
 * Finally, allocations are allowed to rearrange themselves with the
 * chunk_migration() call.  chunk_migration() takes an array of
 * pointers to chunk references as input, and examines each of the
 * indicated chunks to see which need to be moved to improve the
 * distribution of allocations.  If any allocations are moved, then
 * the references to the moved allocations are updated in place
 * (hence the array of pointers to references, instead of just an
 * array of references).  Migration may be done incrementally by
 * submitting only a portion of the allocations with each call to
 * chunk_migration(); however, _all_ allocations made with chunk_create()
 * must eventually be submitted for migration in order to maintain the
 * memory pool in a non-fragmented state.
 *
 *
 * <h3>Migration:</h3>
 * Under normal conditions, extended use of this chunk allocation system
 * would lead to a significantly fragmented datastore, unless there was
 * some means to defragment the storage arena.  In the long run, this could
 * be very bad, leading to quite a mess.  Calling chunk_migration() gives
 * the allocator permission to move allocations around both to defragment
 * the arena and to improve locality of reference (by making sure that
 * all the infrequently used chunks are segregated from the chunks in
 * active use).  Of course, moving all the allocated chunks at once would
 * be a slow and painful process.  Instead, migration may be done
 * incrementally, giving permission to move a small number of chunks
 * at any one time, and spreading out the cost of defragmenting the
 * data store.
 *
 * Just because you give permission to move a chunk doesn't mean that it
 * will be moved.  The chunk may be perfectly happy where it is, with
 * no need to move it elsewhere.  Chunks are only moved when their
 * personal happiness would be improved by a move.  In general, maximizing
 * the happiness of individual chunks will improve the happiness of the
 * whole.
 *
 * There are two things that factor into a chunk's happiness.
 * The things that make a chunk unhappy are:
 * <ul>
 * <li> Having a dereference count different from the region average.
 *      The greater the difference, the more unhappy the chunk is.
 * <li> Being in a sparsely populated region.  The fewer chunks in a
 *      region, the more unhappy the chunks in it.
 * </ul>
 * Neither of these factors are absolute; both of them have different
 * weights that add into a general unhappiness for the chunk.  The lower
 * the unhappiness, the better.
 *
 * Over time and usage, the dereference counts for chunks will increase
 * and eventually reach a maximum value of 255.  (The count is limited
 * by the fact that it's stored in a single byte for each chunk.)  If
 * this is left unchecked, eventually all chunks would have a dereference
 * count of 255, and the counts would be useless for improving locality.
 * To counteract this, when the average dereference count for a certain
 * number of regions exceeds 128, the 'migration period' is incremented
 * and all chunk dereference counts are halved.  The critical number of
 * regions is determined based on the cache size and the total number of
 * regions.  If you're not using forking dumps, then period change should
 * be controlled primarily by the frequency of database dumps (which end
 * up incrementing the dereference count on all chunks, and thus all
 * regions).  Given a dump frequency of once per hour (the default), there
 * should be a period change about every 2.6 days.
 *
 *
 * <h3>Statistics:</h3>
 * The chunk memory management system keeps several statistics about
 * the allocation pool, both to maintain good operation through active
 * encouragement of locality, and to satisfy the curiosity of people
 * using the system (and its designer ;-)).  These statistics are
 * reported (in PennMUSH) through the use of the @stats command,
 * with /chunks switch.
 *
 * @stats/chunks generates output similar to this:
 * \verbatim
 * Chunks:         99407 allocated (   8372875 bytes,     223808 ( 2%) overhead)
 *                   74413 short     (   1530973 bytes,     148826 ( 9%) overhead)
 *                   24994 medium    (   6841902 bytes,      74982 ( 1%) overhead)
 *                       0 long      (         0 bytes,          0 ( 0%) overhead)
 *                   128 free      (   1319349 bytes,      23058 ( 1%) fragmented)
 * Regions:          147 total,       16 cached
 * Paging:        158686 out,     158554 in
 * Storage:      9628500 total (86% saturation)
 *
 * Period:             1 (   5791834 accesses so far,       1085 chunks at max)
 * Migration:     245543 moves this period
 *                  145536 slide
 *                      45 away
 *                   30719 fill exact
 *                   69243 fill inexact
 * \endverbatim
 * First, the number of allocated chunks is given, along with their
 * total size and overhead.  Then, the allocated chunks are broken
 * up by size-range; short chunks (2 to 63 bytes) with two bytes of
 * overhead each, medium chunks (64 to 8191 bytes) with three bytes
 * of overhead each, and long chunks (8192 to ~64K bytes) with four
 * bytes of overhead each.  Rounding out the individual chunk statistics
 * is the number of free chunks, their total size, and the amount of
 * fragmented free space (free space not in the largest free chunk for
 * its region is considered fragmented).
 *
 * Next comes statistics on regions: the number of regions in use
 * and the number held in the memory cache.  All regions not in the
 * cache are paged out to disk.  Paging statistics follow, listing
 * the number of times a region has been moved out of or into
 * memory cache.  After that, the total amount of storage (in memory
 * or on disk) used is given, along with the saturation rate (where
 * saturation is indicated by what fraction of the used space is
 * actually allocated in chunks).
 *
 * Finally comes statistics on migration and the migration period.
 * The period number is listed, along with the total number of
 * dereferences in the period and how many chunks have the maximum
 * dereference count of 255.  Then the amount of migration movement
 * is listed, both in total and broken up by category.  Slides occur
 * when an allocation is shifted to the other side of a neighboring
 * free space.  Away moves are made when an allocation is extremely
 * unhappy where it is, and is pushed out to somewhere else.  Fills
 * are when an allocation is moved in order to fill in a free space;
 * the space can be either exactly filled by the move, or inexactly
 * filled (leaving some remaining free space).
 *
 *
 * <h3>Histograms:</h3>
 * The chunk memory management system can also display a few
 * histograms about itself.  These histograms are reported (in PennMUSH)
 * through the use of the @stats command, with the /regions, /freespace,
 * or /paging switches.
 *
 * All of @stats/regions, @stats/freespace, and @stas/paging produce
 * histograms vs. region average dereference count.  The histograms
 * use buckets four counts wide, so all regions from 0-3 will be in
 * the first bucket, 4-7 in the second, etc., up to 252-255 in the
 * last bucket.  If the heights of the buckets are significantly
 * different, then the highest spikes will be allowed to extend off
 * the top of the histogram (with their real values labeled in
 * parenthesis next to them).
 *
 * @stats/regions is a histogram of how many regions at each count
 * currently exist.  In a healthy game, there should be a large spike
 * at some dereference count between 64 and 128 (representing the
 * largely unused portion of the database), a lesser spike at 255
 * (representing the portion of the database that's used very frequently),
 * and a smattering of regions at other counts, with either new areas
 * of the database (below the large spike) or semi-frequently used
 * areas (above the large spike).  New migration periods occur when
 * the large spike would pass 128, at which point everything is halved
 * and the spike is pushed back down to 64.
 *
 * @stats/freespace is a histogram of how much free space exists in
 * regions at each dereference count.  This histogram is included
 * to aid in diagnosis of the cause for dropping saturation rates.
 *
 * @stats/paging is a histogram of the number of regions being paged
 * in or out at each dereference count.  As of this writing, a very
 * unhealthy behaviour is observed, wherein the histogram shows a
 * trapeziod between 64 and 128, drowning out most of the rest of the
 * chart.  This indicates that as time goes on, the attributes
 * associated with a single low-use object are getting scattered
 * randomly throughout all the low-use regions, and thus when dumps
 * occur (with their linear enumeration of all attributes on objects)
 * the low-use regions thrash in and out of cache.  This can be very
 * detrimental to dump performance.  Something will have to be done
 * to fix this tendency of migration.  Healthy behaviour will make
 * some other pattern in the paging histogram which has not yet been
 * determined.
 */

#include "copyrite.h"
#include "config.h"
#include "conf.h"

#include <limits.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>

#include <fcntl.h>
#include <assert.h>
#include <sys/types.h>
#ifdef WIN32
#include <wtypes.h>
#include <io.h>
#else
#include <unistd.h>
#endif
#include <errno.h>

#include "externs.h"
#include "chunk.h"
#include "command.h"
#include "dbdefs.h"
#include "intrface.h"
#include "log.h"
#include "mymalloc.h"
#include "confmagic.h"

#ifdef WIN32
#pragma warning( disable : 4761)        /* disable warning re conversion */
#endif

/* A whole bunch of debugging #defines. */
/** Basic debugging stuff - are assertions checked? */
#undef CHUNK_DEBUG
/** Paranoid people check for region validity after every operation
 * that modifies a region. */
#undef CHUNK_PARANOID
/** Log all moves and slides during migration. */
#undef DEBUG_CHUNK_MIGRATE
/** Log creation of regions. */
#undef DEBUG_CHUNK_REGION_CREATE
/** Log paging of regions. */
#undef DEBUG_CHUNK_PAGING
/** Log all mallocs. */
#undef DEBUG_CHUNK_MALLOC

/** For debugging, we keep a rolling log of debug messages.
 * These get dumped to disk if we're about to panic.
 */
#define ROLLING_LOG_SIZE 200
#define ROLLING_LOG_ENTRY_LEN 1024

/* debug... */
#ifdef CHUNK_DEBUG
#define ASSERT(x) assert(x)
#else                           /* CHUNK_DEBUG */
static int ignore;      /**< Used to shut up compiler warnings when not asserting */
#define ASSERT(x) ignore++
#endif                          /* CHUNK_DEBUG */

/*
 * Sizes, limits, etc.
 */
/** Region size, including header.
 * This is a little less than 64K to allow for malloc overhead without
 * spilling into next page */
#define REGION_SIZE 65500

/** Region capacity.
 * This is the size minus the fixed region overhead.
 */
#define REGION_CAPACITY (REGION_SIZE - FIRST_CHUNK_OFFSET_IN_REGION)

/** Maximum chunk length.
 * This is fairly arbitrary, but must be less than
 * REGION_CAPACITY (it must fit in a region).
 */
#define MAX_CHUNK_LEN (16384-1)

/** Number of oddballs tracked in regions.
 * This is used to figure out when we should pull regions in because
 * we have an opportunity to migrate chunks that don't match.
 * Relatively arbitrary; too low means you don't move things out
 * enough, but boosting it too high wastes memory.
 */
#define NUM_ODDBALLS 10

/** Minimum disagreement to be an oddball.
 * This is used to figure out when we should pull regions in because
 * we have an opportunity to migrate chunks that don't match.
 * Relatively arbitrary; too low means you don't move things out
 * enough, but boosting it too high wastes migration time.
 */
#define ODDBALL_THRESHOLD 8

/*
 * FIXME: pulling config variables out of my left ear. Fix later.
 */
/** How much space is initially allocated for the in-memory region array? */
#define FIXME_INIT_REGION_LEN 20
/** How much does the region array grow by each time it has to grow? */
#define FIXME_REGION_ARRAY_INCREMENT 10

/** Limit for when being a nearly-empty region counts against being
 * a good region.  This is exponential: an empty region gets a penalty
 * of 1 << LONLINESS_LIMIT.  A near-empty region gets a penalty of
 * 1 << (LONLINESS_LIMIT - used_count).
 *
 * Rationale: we don't want to reuse empty regions (or make new regions)
 * for trivialities.
 */
#define LONLINESS_LIMIT 5

/** Free space limit for when we consider making new regions.
 * The total free space must be less than this percent of capacity.
 *
 * Rationale: we don't want to waste memory with lots of extra regions.
 */
#define FREE_PERCENT_LIMIT 2

/** Bias for allocating chunks in a region that's already in memory.
 * Actually, this is a bias against allocating in swapped-out regions,
 * but that's a nit...
 *
 * Rationale: reduce the amount of paging during migration.
 */
#define IN_MEMORY_BIAS 4

/*
 *  Structures and Accessor Macros
 */
/*
 * What a chunk_reference_t looks like from the inside
 */
/** Get the region from a chunk_reference_t. */
#define ChunkReferenceToRegion(ref) ((ref) >> 16)
/** Get the offset from a chunk_reference_t. */
#define ChunkReferenceToOffset(ref) ((ref) & 0xFFFF)
/** Make a chunk_reference_t from a region and offset. */
#define ChunkReference(region, offset) \
  ((chunk_reference_t)(((region) << 16) | (offset)))

/** Sentinel value used to mark unused cache regions. */
#define INVALID_REGION_ID 0xffff

/**
 * \verbatim
 * The chunk headers look like this:
 *
 * Short:
 * byte 0     byte 1
 *  76543210   76543210
 * +--------+ +--------+
 * |ft len  | | deref  |
 * +--------+ +--------+
 *  ||\__6_/   \___8__/
 *  ||   |         `----- deref count (decays)
 *  ||   `--------------- length of data
 *  |`------------------- tag bit (0 for short)
 *  `-------------------- free flag (0 for allocated, 1 for free)
 *
 * Medium:
 * byte 0     byte 1     byte 2
 *  76543210   76543210   76543210
 * +--------+ +--------+ +--------+
 * |ftg lenM| | deref  | |  lenL  |
 * +--------+ +--------+ +--------+
 *  |||\_5_/   \___8__/   \___8__/
 *  |||  |         |          `----- length, least significant
 *  |||  |         `---------------- deref count (decays)
 *  |||  `-------------------------- length, most significant
 *  ||`----------------------------- tag bit (0 for medium)
 *  |`------------------------------ tag bit (1 for medium/long)
 *  `------------------------------- free flag
 *
 * Long:
 * byte 0     byte 1     byte 2     byte 3
 *  76543210   76543210   76543210   76543210
 * +--------+ +--------+ +--------+ +--------+
 * |ftg     | | deref  | |  lenM  | |  lenL  |
 * +--------+ +--------+ +--------+ +--------+
 *  |||        \___8__/   \_______16________/
 *  |||            |               `----------- length of data
 *  |||            `--------------------------- deref count (decays)
 *  ||`---------------------------------------- tag bit (1 for long)
 *  |`----------------------------------------- tag bit (1 for medium/long)
 *  `------------------------------------------ free flag
 *
 *
 * Note in particular that the dereference count is always in the second
 * byte of a chunk, to simplify the access logic.
 * \endverbatim
 */

/*
 * Fields in chunk headers
 */
#define CHUNK_FREE_MASK   0x80
#define CHUNK_FREE        0x80
#define CHUNK_USED        0x00

#define CHUNK_TAG1_MASK   0x40
#define CHUNK_TAG1_SHORT  0x00
#define CHUNK_TAG1_MEDIUM 0x40
#define CHUNK_TAG1_LONG   0x40
#define CHUNK_TAG1_OFFSET 0

#define CHUNK_TAG2_MASK   0x20
#define CHUNK_TAG2_MEDIUM 0x00
#define CHUNK_TAG2_LONG   0x20
#define CHUNK_TAG2_OFFSET 0

#define CHUNK_SHORT_LEN_MASK 0x3F
#define CHUNK_SHORT_LEN_OFFSET 0

#define CHUNK_MEDIUM_LEN_MSB_MASK 0x1F
#define CHUNK_MEDIUM_LEN_LSB_MASK 0xFF
#define CHUNK_MEDIUM_LEN_MSB_OFFSET 0
#define CHUNK_MEDIUM_LEN_LSB_OFFSET 2

#define CHUNK_LONG_LEN_MSB_MASK 0xFF
#define CHUNK_LONG_LEN_LSB_MASK 0xFF
#define CHUNK_LONG_LEN_MSB_OFFSET 2
#define CHUNK_LONG_LEN_LSB_OFFSET 3

#define CHUNK_DEREF_OFFSET 1

#define CHUNK_DEREF_MAX 0xFF

#define CHUNK_AGED_MASK   0x10
#define CHUNK_AGED_OFFSET 0

#define CHUNK_SHORT_DATA_OFFSET 2
#define CHUNK_MEDIUM_DATA_OFFSET 3
#define CHUNK_LONG_DATA_OFFSET 4

#define MIN_CHUNK_LEN 1
#define MIN_REMNANT_LEN (CHUNK_SHORT_DATA_OFFSET + MIN_CHUNK_LEN)

#define MAX_SHORT_CHUNK_LEN CHUNK_SHORT_LEN_MASK
#define MAX_MEDIUM_CHUNK_LEN \
        ((CHUNK_MEDIUM_LEN_MSB_MASK << 8) | CHUNK_MEDIUM_LEN_LSB_MASK)
#define MAX_LONG_CHUNK_LEN \
        (REGION_CAPACITY - CHUNK_LONG_DATA_OFFSET)

#define LenToFullLen(len) \
  ((len) + \
   (((len) > MAX_SHORT_CHUNK_LEN) \
    ? ((len) > MAX_MEDIUM_CHUNK_LEN) \
      ? CHUNK_LONG_DATA_OFFSET \
      : CHUNK_MEDIUM_DATA_OFFSET \
    : CHUNK_SHORT_DATA_OFFSET))

#define ChunkPointer(region, offset) \
  (((unsigned char *)(regions[(region)].in_memory)) + (offset))
#define ChunkReferenceToPointer(ref) \
  ChunkPointer(ChunkReferenceToRegion((ref)), ChunkReferenceToOffset((ref)))

/*
 * Macros for probing and manipulating chunk headers
 */
#define CPLenShort(cptr) \
  ((cptr)[CHUNK_SHORT_LEN_OFFSET] & CHUNK_SHORT_LEN_MASK)
#define CPLenMedium(cptr) \
  ((((cptr)[CHUNK_MEDIUM_LEN_MSB_OFFSET] & CHUNK_MEDIUM_LEN_MSB_MASK) << 8) + \
   ((cptr)[CHUNK_MEDIUM_LEN_LSB_OFFSET] & CHUNK_MEDIUM_LEN_LSB_MASK))
#define CPLenLong(cptr) \
  ((((cptr)[CHUNK_LONG_LEN_MSB_OFFSET] & CHUNK_LONG_LEN_MSB_MASK) << 8) + \
   ((cptr)[CHUNK_LONG_LEN_LSB_OFFSET] & CHUNK_LONG_LEN_LSB_MASK))
#define CPLen(cptr) \
  ((*(cptr) & CHUNK_TAG1_MASK) \
   ? (*(cptr) & CHUNK_TAG2_MASK) \
     ? CPLenLong((cptr)) \
     : CPLenMedium((cptr)) \
   : CPLenShort((cptr)))
#define ChunkLen(region, offset) \
  CPLen(ChunkPointer((region), (offset)))
#define CPFullLen(cptr) \
  ((*(cptr) & CHUNK_TAG1_MASK) \
   ? (*(cptr) & CHUNK_TAG2_MASK) \
     ? (CPLenLong((cptr)) + CHUNK_LONG_DATA_OFFSET) \
     : (CPLenMedium((cptr)) + CHUNK_MEDIUM_DATA_OFFSET) \
   : (CPLenShort((cptr)) + CHUNK_SHORT_DATA_OFFSET))
#define ChunkFullLen(region, offset) \
  CPFullLen(ChunkPointer((region), (offset)))

#define ChunkIsFree(region, offset) \
  ((*ChunkPointer((region), (offset)) & CHUNK_FREE_MASK) == CHUNK_FREE)
#define ChunkIsShort(region, offset) \
  ((*ChunkPointer((region), (offset)) & CHUNK_TAG1_MASK) == CHUNK_TAG1_SHORT)
#define ChunkIsMedium(region, offset) \
  ((*ChunkPointer((region), (offset)) & (CHUNK_TAG1_MASK | CHUNK_TAG2_MASK)) \
   == (CHUNK_TAG1_MEDIUM | CHUNK_TAG2_MEDIUM))
#define ChunkIsLong(region, offset) \
  ((*ChunkPointer((region), (offset)) & (CHUNK_TAG1_MASK | CHUNK_TAG2_MASK)) \
   == (CHUNK_TAG1_LONG | CHUNK_TAG2_LONG))

#define ChunkDerefs(region, offset) \
  (ChunkPointer((region), (offset))[CHUNK_DEREF_OFFSET])

#define CPDataPtr(cptr) \
  ((*(cptr) & CHUNK_TAG1_MASK) \
   ? (*(cptr) & CHUNK_TAG2_MASK) \
     ? (cptr) + CHUNK_LONG_DATA_OFFSET \
     : (cptr) + CHUNK_MEDIUM_DATA_OFFSET \
   : (cptr) + CHUNK_SHORT_DATA_OFFSET)
#define ChunkDataPtr(region, offset) \
  (CPDataPtr(ChunkPointer(region, offset)))

#define ChunkNextFree(region, offset) \
  ((ChunkDataPtr(region, offset)[0] << 8) + ChunkDerefs(region, offset))

/* 0 for no, 1 for yes with room, 2 for exact */
#define FitsInSpace(size, capacity) \
  (((size) == (capacity)) ? 2 : ((size) <= (capacity) - MIN_REMNANT_LEN))

/** Region info that gets paged out with its region.
 * This is at the start of the region;
 * the rest of the 64K bytes of the region contain chunks.
 */
typedef struct region_header {
  uint16_t region_id;           /**< will be INVALID_REGION_ID if not in use */
  uint16_t first_free;          /**< offset of 1st free chunk */
  struct region_header *prev;   /**< linked list prev for LRU cache */
  struct region_header *next;   /**< linked list next for LRU cache */
} RegionHeader;

#define FIRST_CHUNK_OFFSET_IN_REGION sizeof(RegionHeader)

/** In-memory (never paged) region info.  */
typedef struct region {
  uint16_t used_count;          /**< number of used chunks */
  uint16_t free_count;          /**< number of free chunks */
  uint16_t free_bytes;          /**< number of free bytes (with headers) */
  uint16_t largest_free_chunk;  /**< largest single free chunk */
  uint32_t total_derefs;        /**< total of all used chunk derefs */
  uint32_t period_last_touched; /**< "this" period, for deref counts;
                                           we don't page in regions to update
                                           counts on period change! */
  RegionHeader *in_memory;      /**< cache entry; NULL if paged out */
  uint16_t oddballs[NUM_ODDBALLS];      /**< chunk offsets with odd derefs */
} Region;

#define RegionDerefs(region) \
  (regions[(region)].used_count \
   ? (regions[(region)].total_derefs >> \
      (curr_period - regions[(region)].period_last_touched)) / \
     regions[(region)].used_count \
   : 0)
#define RegionDerefsWithChunk(region, derefs) \
   (((regions[(region)].total_derefs >> \
     (curr_period - regions[(region)].period_last_touched)) + derefs) / \
    (regions[(region)].used_count + 1))

/*
 *  Globals
 */

/** Swap File */
#ifdef WIN32
typedef HANDLE fd_type;
static HANDLE swap_fd;
static HANDLE swap_fd_child = INVALID_HANDLE_VALUE;
#else
typedef int fd_type;
static int swap_fd;
static int swap_fd_child = -1;
#endif
static char child_filename[300];

/** Deref scale control.
 * When the deref counts get too big, the current period is incremented
 * and all derefs are divided by 2. */
static uint32_t curr_period;

/*
 * Info about all regions
 */
static uint32_t region_count;   /**< regions in use */
static uint32_t region_array_len;       /**< length of regions array */
static Region *regions;         /**< regions array, realloced as (rarely) needed */

/*
 * regions presently in memory
 */
static uint32_t cached_region_count;    /**< number of regions in cache */
static RegionHeader *cache_head;        /**< most recently used region */
static RegionHeader *cache_tail;        /**< least recently used region */

/*
 * statistics
 */
static int stat_used_short_count;       /**< How many short chunks? */
static int stat_used_short_bytes;       /**< How much space in short chunks? */
static int stat_used_medium_count;      /**< How many medium chunks? */
static int stat_used_medium_bytes;      /**< How much space in medium chunks? */
static int stat_used_long_count;        /**< How many long chunks? */
static int stat_used_long_bytes;        /**< How much space in long chunks? */
static int stat_deref_count;            /**< Dereferences this period */
static int stat_deref_maxxed;           /**< Number of chunks with max derefs */
/** histogram for average derefs of regions being paged in/out */
static int stat_paging_histogram[CHUNK_DEREF_MAX + 1];
static int stat_page_out;               /**< Number of page-outs */
static int stat_page_in;                /**< Number of page-ins */
static int stat_migrate_slide;          /**< Number of slide migrations */
static int stat_migrate_move;           /**< Number of move migrations */
static int stat_migrate_away;           /**< Number of chunk evictions */
static int stat_create;                 /**< Number of chunk creations */
static int stat_delete;                 /**< Number of chunk deletions */



/*
 * migration globals that are used for holding relevant data...
 */
static int m_count;             /**< The used length for the arrays. */
static chunk_reference_t **m_references; /**< The passed-in references array. */

#ifdef CHUNK_PARANOID
/** Log of recent actions for debug purposes */
static char rolling_log[ROLLING_LOG_SIZE][ROLLING_LOG_ENTRY_LEN];
static int rolling_pos;
static int noisy_log = 0;
#endif

/*
 * Forward decls
 */
static void find_oddballs(uint16_t region);

/*
 * Debug routines
 */
/** Add a message to the rolling log. */
static void
debug_log(char const *format, ...)
{
#ifdef CHUNK_PARANOID
  va_list args;

  va_start(args, format);
  vsprintf(rolling_log[rolling_pos], format, args);
  va_end(args);

  rolling_log[rolling_pos][ROLLING_LOG_ENTRY_LEN - 1] = '\0';
  if (noisy_log) {
    fprintf(tracelog_fp, "%s\n", rolling_log[rolling_pos]);
    fflush(tracelog_fp);
  }
  rolling_pos = (rolling_pos + 1) % ROLLING_LOG_SIZE;
#else
  if (format)
    return;                     /* shut up the compiler warning */
#endif
}

#ifdef CHUNK_PARANOID
/** Dump the rolling log. */
static void
dump_debug_log(FILE * fp)
{
  int j;
  fputs("Recent chunk activity:\n", fp);
  j = rolling_pos;
  do {
    if (rolling_log[j][0]) {
      fputs(rolling_log[j], fp);
      fputc('\n', fp);
      rolling_log[j][0] = '\0';
    }
    j = (j + 1) % ROLLING_LOG_SIZE;
  } while (j != rolling_pos);
  fputs("End of recent chunk activity.\n", fp);
  fflush(fp);
}

/** Test if a chunk is migratable. */
static int
migratable(uint16_t region, uint16_t offset)
{
  chunk_reference_t ref = ChunkReference(region, offset);
  int j;

  for (j = 0; j < m_count; j++)
    if (m_references[j][0] == ref)
      return 1;
  return 0;
}

/** Give a detailed map of a region.
 * Lists pertinent region information, and all the chunks in the region.
 * Does not print the contents of the chunks (which would probably be
 * unreadable, anyway).
 * \param region the region to display.
 * \param fp the FILE* to output to.
 */
static void
debug_dump_region(uint16_t region, FILE * fp)
{
  Region *rp = regions + region;
  RegionHeader *rhp;
  uint16_t offset, count;

  ASSERT(region < region_count);
  rhp = rp->in_memory;

  fprintf(fp, "region: id:%04x period:%-8x deref:%-8x (%-2x per chunk)\n",
          region, rp->period_last_touched, rp->total_derefs,
          RegionDerefs(region));
  fprintf(fp, "        #used:%-4x #free:%-4x fbytes:%-4x hole:%-4x ",
          rp->used_count, rp->free_count, rp->free_bytes,
          rp->largest_free_chunk);
  if (rhp)
    fprintf(fp, "first:%-4x h_id:%-4x\n", rhp->first_free, rhp->region_id);
  else
    fprintf(fp, "PAGED\n");
  fflush(fp);

  if (rhp) {
    for (offset = FIRST_CHUNK_OFFSET_IN_REGION;
         offset < REGION_SIZE; offset += ChunkFullLen(region, offset)) {
      fprintf(fp, "chunk:%c%4s %-6s off:%04x full:%04x ",
              migratable(region, offset) ? '*' : ' ',
              ChunkIsFree(region, offset) ? "FREE" : "",
              ChunkIsShort(region, offset) ? "SHORT" :
              (ChunkIsMedium(region, offset) ? "MEDIUM" : "LONG"),
              offset, ChunkFullLen(region, offset));
      if (ChunkIsFree(region, offset)) {
        fprintf(fp, "next:%04x\n", ChunkNextFree(region, offset));
      } else {
        fprintf(fp, "doff:%04x len:%04x ",
                ChunkDataPtr(region, offset) - (unsigned char *) rhp,
                ChunkLen(region, offset));