pfe-mem.c   [plain text]

/* Persistent Front End (PFE) low-level and common routines.
   Copyright (C) 2001
   Free Software Foundation, Inc.
   Contributed by Apple Computer Inc.

This file is part of GNU CC.

GNU CC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU CC 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU CC; see the file COPYING.  If not, write to
the Free Software Foundation, 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.  */

/* 
=====================================================================
============= I M P L E M E N T A T I O N    N O T E S ==============
=====================================================================
IMPLEMENTATION GOALS:
* Provide a generic memory manager implementation, suitable for the
  FSF.
* Under conditionals, provide a version that is tuned for Macintosh 
  OS X.
* Retain structures across a dump and load.
* Avoid dirtying and/or bringing in pages unnecessarily.

IMPLEMENTATION STRATEGIES:
* Keep track of ranges (start and end) for reporting to the PFE, and
  have new allocations extend existing ranges if possible.
  
IMPLEMENTATION ISSUES/QUESTIONS:
* Do we want to support zones?  Perhaps we would want a zone for 
  those things that need to be written out by the PFE and a zone 
  for everything else.  It might be useful to have a zone for the 
  memory manager itself.
* Do we want to have an interface that allows users of the memory
  manager to specify something about the kinds of memory they are
  likely to use (zones, types, sizes, expected number of allocations,
  etc.)?
* What should the default alignment of fragments be?  If memory 
  fragments begin after the "hidden" long that preceeds them 
  (recording the actual size of the fragment), what do we do if
  something requires greater alignment?
* How do we keep track of the biggest available fragment in a block,
  particularly after we use it (or part of it)?  We could scan the
  list up to that point as we look for a block from which to do an
  allocation.  Otherwise, we might have to keep a list in order of
  size.
* Do we want the block list to be a table or a linked list?  A table
  would have some advantages, but, since it has to grow, it would
  require that persistent references to items in the table be via
  indices.
* The block rover strategy may save on space, but it may be
  inefficient in causing many more blocks and fragments to be
  searched when trying to do an allocation, especially when we don't
  find a suitable fragment and are forced to allocate a new block.
* We may want to deal someday with fragmentable blocks of arbitrary 
  size.

TO DO:
* Check for best (or better) fit for fragment, rather than just first.
* Rovers in fragment lists.
* Ensure that no unusable (too small) fragments are created.
* Write freeze/thaw routines for pfe-mem structures, which would
  allow pfe-mem structures to be used across a dump and load.  We
  should do this if we determine that it is worthwhile to use these 
  structures on after a load.  This would allow frees in the load 
  area to work, but this would only have a benefit if we then used 
  this space for allocations.
* Consider splitting large blocks in the free whole block list.
* Gather statistics.  
  - Move malloc/free/etc stats gathering to pfe-mem from pfe.
  - Calculate the real size of freed objects.
* Allow for a bigger initial frag block allocation with smaller
  incremental allocations after that.  The initial block should be
  big enough to handle Carbon.h.

DONE:
* Rover in block list.
* Validate free_bytes in blocks upon termination.
* Adjust criterion for when to alloc a fragment to take into
  account the new max allocatable fragment size after the changes
  to alloc a frag block's block info entry at the beginning of the
  block.
* Shorten final ranges based on what is in the free list.

TUNING:
* Try using different sizes of fragmentable blocks.
=====================================================================
*/

/* Control whether priting memory statistics is enabled.  The actual
   diagnostic messages are controlled by a command line option
   controlling similar PFE diagnostics.  */
#define PFEM_MEMORY_STATS 1

/* Control whether informational diagnostics are on.  */
#define PFEM_DIAGNOSTICS 0

/* Control whether debugging diagnostics are on.  */
#define PFEM_DEBUG 0

/* Control whether or not we will try to minimize memory ranges
   when pfem_id_ranges is called.  At this point, the minimization
   code cuts out memory ranges that are still identified as being
   present in other pfe-mem structures.  This can be fixed.  */
#define MINIMIZE_RANGES 0

/* Flag indicating whether this is an implementation specific for
   Macintosh OS X.  Should be autoconfiscated someday.  */
#ifdef CONFIG_DARWIN_H
#define APPLE_OS_X_IMPLEMENTATION 1
#else
#define APPLE_OS_X_IMPLEMENTATION 0
#endif

#include "config.h"
#include "system.h"

#include <stddef.h>
#include <stdlib.h>

#if APPLE_OS_X_IMPLEMENTATION
#include <mach/mach.h>
#include <mach/mach_error.h>
#endif

#include "pfe-mem.h"

/* The PFE memory manager structures are as follows:
(1) "range": a range of contiguous memory controlled by the memory
    manager.
(2) "block": a block of memory allocated by a single call to the
    system memory manager.  Blocks are either "whole" or
    "fragmentable", meaning that the block is either allocated as
    a single (whole) unit, or it is carved up into smaller fragments.
(3) "block info": an entry (itself a fragment) corresponding to a
    block, indicating its location, size and whether it is whole or
    fragmentable.  If the block is fragmentable, there is a pointer
    to its list of fragments that are available for allocation.
(4) "fragment": a fragment of memory allocated by the PFE memory
    manager, originally coming from a block.
(5) "range table": a table of the range of addresses covered by the
    blocks that were allocated.  When contiguous blocks are allocated
    they are treated as a single range.  The information in the range
    table is used by the higher level PFE system to know what regions
    of memory needed to be saved in a dump file.
*/

/* Size of a "fragmentable" PFE memory block.  */
#define PFEM_FRAG_BLOCK_SIZE (64 * 1024)

/* Minimum size of a whole (non-fragmentable) PFE memory block.  */
#define PFEM_MIN_WHOLE_BLOCK_SIZE (64 * 1024)

/* Structure for entry in table of memory ranges.  */
struct pfem_range {
  unsigned long start_addr;
  unsigned long end_addr;	/* Actually points to byte past the end.  */
  // ??? Keep track of anything else?
};
typedef struct pfem_range pfem_range;

/* Structure for memory fragments.  When a fragment is allocated,
   a pointer is returned to the memory following the long at the
   beginning of this structure so that the structure can remember
   its original size.  When a fragment is in the list of free
   fragments, its next field points to the next free fragment.  */
struct pfem_fragment {
  size_t size;
  struct pfem_fragment *next;	/* Usable space begins with this field.  */
};
typedef struct pfem_fragment pfem_fragment;

#define PFEM_FRAGMENT_OVERHEAD (sizeof (size_t))

/* Structure for entry in table of memory blocks.  Note that the
   free_bytes and largest_free_fragment_size fields represent the
   actual size (not the usable size after fragment overhead).  
   
   A memory block is either a fragmentable memory block or a whole
   (non-fragmentable) memory block.  Fragmentable blocks are broken
   up into smaller allocations.  Whole blocks are single large
   allocations that are allocated individually and not broken up.
   A whole memory block is identified by a free_fragments pointer
   that has been set to -1.  
   
   The "next" field points to the next block in the primary block
   list (pfem_block_list).  The "next_avail" field points to the
   next block in a particular avail list, e.g., the list of free
   whole blocks.  */
struct pfem_block_info {
  void *addr;
  size_t size;
  size_t free_bytes;
  size_t largest_free_fragment_size;
  pfem_fragment *free_fragments;
  struct pfem_block_info *next;
  struct pfem_block_info *next_avail;
};
typedef struct pfem_block_info pfem_block_info;

/* The maximum size size of a frament is determine by how fragmentable
   blocks are set up.  They are set up to have a fragment containing 
   their block entry information and a fragment containing the usable
   remainder of the block.  Thus the size of the largest usable
   fragment is defined by the following.  */
#define PFEM_MAX_FRAGMENT_SIZE (PFEM_FRAG_BLOCK_SIZE \
				- (PFEM_FRAGMENT_OVERHEAD \
				   + sizeof (pfem_block_info)))

/* The following pointer value is used in pfem_block_info entries 
   as a flag in the free_fragments field to indicate that the
   block is a "whole" (non-fragmentable) block.  */
#define PFEM_INVALID_PTR ((void *) -1)
#define PFEM_IS_WHOLE_BLOCK(x) ((x)->free_fragments == PFEM_INVALID_PTR)

/* List of memory manager blocks.  We keep a pointer to the last
   block since that is the most likely spot a new block will be
   inserted in the list.  */
static pfem_block_info *pfem_block_list = NULL;
static pfem_block_info *pfem_block_list_last = NULL;

/* List of memory manager "whole" (non-fragmentable) blocks that
   are available for allocation, i.e., they were allocated and were
   freed.  */
static pfem_block_info *pfem_whole_block_avail_list = NULL;

/* List of memory manager fragmentable blocks.  All fragmentable
   blocks are on the avail list.  */
static pfem_block_info *pfem_frag_block_avail_list = NULL;

/* Size that a fragment is allowed to vary from the original allocation
   size request to be allocated without splitting the fragment into
   two.  */
// ??? Need to think further about what this should be.
#define MAX_FRAGMENT_SIZE_VARIANCE_BEFORE_SPLIT 12

/* Definitions for the original size of the range table and the
   increment by which to grow it (as needed).  */
// ??? Adjust these values to something reasonable.

#define PFEM_INITIAL_RANGE_TABLE_SIZE 64
#define PFEM_RANGE_TABLE_INCR 64

/* The size a fragment at the end of a fragmentable block must be in 
   order for it to be removed from the address range table before
   address ranges are reported to the PFE.  */
#define PFEM_MIN_RECOVERABLE_FRAGMENT_SIZE 1024

/* Table with entries for each memory range to be "dump"ed.  */
static pfem_range *pfem_range_table = NULL;

/* Current size of the dump range table.  */
static int pfem_range_table_size = 0;

/* Number of items currently in the dump range table.  */
static int pfem_range_table_nitems = 0;

/* Flag whether initialization of the PFE memory manager is complete.  
   This is used by a few routines that deal with memory manager
   structures that must be handled somewhat differently before
   initialization is complete because they cannot yet rely on some
   of the memory manager mechanisms.  */
static int pfem_initialization_complete = 0;

/* Variables to collect statistics on PFE memory utilization.   */
#if PFEM_MEMORY_STATS
extern int pfe_display_memory_stats;
static size_t pfem_malloc_total_size = 0;
static int pfem_mallocs = 0;
static int pfem_callocs = 0;
static int pfem_reallocs = 0;
static int pfem_frees = 0;
#endif

/* Prototypes for static functions.  */

static void pfem_add_block_to_range_table PARAMS ((void *, size_t));
static void pfem_add_block_to_block_list PARAMS ((pfem_block_info *));
static void * pfem_alloc_block PARAMS ((size_t));
static void * pfem_alloc_fragment PARAMS ((size_t));
static void * pfem_alloc_whole_block PARAMS ((size_t));
static pfem_block_info * pfem_find_containing_block PARAMS ((void *));
static pfem_block_info * pfem_set_up_frag_block PARAMS ((void *, size_t));
#if PFEM_MEMORY_STATS
static void pfem_memory_statistics PARAMS ((void));
#endif

/*-------------------------------------------------------------------*/

/* Initialize the PFE's low-level memory manager.  */

void 
pfem_init (void)
{
  void *initial_block;
  pfem_block_info *block_info;
  
  /* Allocate some memory in which to allocate the memory manager's
     own data structures.  */
  initial_block = pfem_alloc_block (PFEM_FRAG_BLOCK_SIZE);
  
  /* Set up the initial fragment from which to do allocations.  After
     this set-up, pfem_malloc should be usable.  */
  block_info = pfem_set_up_frag_block (initial_block, PFEM_FRAG_BLOCK_SIZE);
  pfem_add_block_to_block_list (block_info);
  pfem_frag_block_avail_list = block_info;

  /* Initialize the memory range table.  */
  pfem_range_table_size = PFEM_INITIAL_RANGE_TABLE_SIZE;
  pfem_range_table = (pfem_range *) 
      		     xmalloc (sizeof (pfem_range) 
                              * pfem_range_table_size);
  
  /* Enter the initial block of memory in the range table.  */
  pfem_add_block_to_range_table (initial_block, PFEM_FRAG_BLOCK_SIZE);
  
  /* Signal that initialization is complete.  */
  pfem_initialization_complete = 1;
}

#if PFEM_MEMORY_STATS
/* Emit diagnostic information upon termination.  */

void 
pfem_memory_statistics (void)
{
  int range_idx;
  int block_idx;
  size_t free_fragments_in_block;
  size_t total_free_framents;
  size_t total_free_bytes;
  pfem_block_info *block;
  pfem_fragment *fragment;
  pfem_fragment *last_fragment;
  size_t free_frament_bytes;
  size_t recoverable_fragment_bytes;
  
  printf ("\npfem_term:\n");
    
  printf ("range table:\n");
  for (range_idx = 0; range_idx < pfem_range_table_nitems; range_idx++)
    printf ("  range [%d]: 0x%x - 0x%x; size = %d (0x%x)\n", 
	    range_idx + 1,
	    pfem_range_table[range_idx].start_addr,
	    pfem_range_table[range_idx].end_addr,
	    pfem_range_table[range_idx].end_addr 
	    - pfem_range_table[range_idx].start_addr,
	    pfem_range_table[range_idx].end_addr 
	    - pfem_range_table[range_idx].start_addr);
  
  printf ("\npfem_whole_block_avail_list:\n");
  block_idx = 0;
  for (block = pfem_whole_block_avail_list; block != NULL; block = block->next_avail)
    {
      block_idx++;
      printf ("  free whole block [%d]: addr = 0x%x; size = %d (0x%x)\n",
      	      block_idx, block->addr, block->size, block->size);
    }

  printf ("\npfem_frag_block_avail_list:\n");
  block_idx = 0;
  total_free_bytes = 0;
  total_free_framents = 0;
  recoverable_fragment_bytes = 0;
  for (block = pfem_frag_block_avail_list; block != NULL; block = block->next_avail)
    {
      block_idx++;
      total_free_bytes += block->free_bytes;
      /* Validate the free_bytes info against the size of fragments 
         on the avail list.  */
      free_frament_bytes = 0;
      free_fragments_in_block = 0;
      last_fragment = NULL;
      for (fragment = block->free_fragments; fragment != NULL; fragment = fragment->next)
        {
          free_frament_bytes += fragment->size;
          free_fragments_in_block++;
          last_fragment = fragment;
        }
      if ((last_fragment != NULL) 
      	  && (((unsigned long) last_fragment + last_fragment->size)
      	      == ((unsigned long) block->addr + block->size))
      	  && (last_fragment->size > 1023))
      	recoverable_fragment_bytes += last_fragment->size;
      total_free_framents += free_fragments_in_block;
      printf ("  fragment block [%d]: addr = 0x%x; size = %d; "
      	      "free_bytes = %d; free_fragments_in_block = %d\n", 
      	      block_idx, block->addr, block->size, block->free_bytes,
      	      free_fragments_in_block);
      if (free_frament_bytes != block->free_bytes)
	printf ("    free_bytes != free_frament_bytes (%d)\n", free_frament_bytes);
    }
    printf ("  total_free_bytes = %d\n", total_free_bytes);
    printf ("  total_free_framents = %d\n", total_free_framents);
    printf ("  recoverable_fragment_bytes = %d\n", recoverable_fragment_bytes);
}
#endif

/* Shut down the PFE's low-level memory manager.  */

void 
pfem_term (void)
{
#if PFEM_MEMORY_STATS
  if (pfe_display_memory_stats)
    pfem_memory_statistics ();
#endif
}

/* Put a new block info entry into the global block list.  The list
   is kept in order of ascending addresses.  */
   
void
pfem_add_block_to_block_list (new_block_info)
     pfem_block_info *new_block_info;
{
  pfem_block_info *block;
  pfem_block_info *last_block;
  
  /* First check whether the new block goes at the end of the list,
     which is the mostly likely case.  */
  
  if (pfem_block_list_last == NULL)
    {
      /* The list is empty.  */
      pfem_block_list = new_block_info;
      pfem_block_list_last = new_block_info;
      return;
    }
  if ((unsigned long) new_block_info->addr > (unsigned long) pfem_block_list_last->addr)
    {
      pfem_block_list_last->next = new_block_info;
      pfem_block_list_last = new_block_info;
      return;
    }
  
  /* Check whether the block goes at the front of the list.  */
  
  if (pfem_block_list == NULL)
    {
      /* There should always be a (first) block if things have been
         initialized properly.  */
      printf ("pfem_add_block_to_block_list: pfem_block_list == NULL.\n");
      exit (1);
    }
  if ((unsigned long) new_block_info->addr < (unsigned long)pfem_block_list->addr)
    {
      new_block_info->next = pfem_block_list;
      pfem_block_list = new_block_info;
      return;
    } 
  
  /* The block goes somewhere in the middle of the block list.  */
#if PFEM_DEBUG
  printf ("pfem_add_block_to_block_list: new block goes into middle of block list.\n");
#endif
  last_block = pfem_block_list;
  for (block = pfem_block_list->next; block != NULL; block = block->next)
    {
      if ((unsigned long) new_block_info->addr < (unsigned long)block->addr)
        {
          last_block->next = new_block_info;
          new_block_info->next = block;
          return;
        }
      last_block = block;
    }
#if PFEM_DEBUG
  printf ("pfem_add_block_to_block_list: we should not get here.\n");
#endif
}

/* Given an addr, return a pointer to the block info entry for the
   block containing the address.  */

pfem_block_info *
pfem_find_containing_block (addr)
     void *addr;
{
  pfem_block_info *block;
  pfem_block_info *last_block = NULL;

  for (block = pfem_block_list; block != NULL; block = block->next)
    {
      if ((unsigned long) addr < (unsigned long)block->addr)
        break;
      last_block = block;
    }
  if (last_block == NULL)
    return NULL;
  if ((unsigned long) addr < ((unsigned long) last_block->addr
			      + last_block->size))
    return last_block;
  return NULL;
  
}

/* Add information on a memory block to the range table.  The table 
   of ranges is ordered.  */

void
pfem_add_block_to_range_table (block_addr, size)
     void *block_addr;
     size_t size;
{
  int range_idx;
  unsigned long start_addr = (unsigned long)block_addr;
  unsigned long end_addr = start_addr + size;

  /* Check whether we need to grow the size of the range table.  */
  if (pfem_range_table_nitems >= pfem_range_table_size)
    {
      pfem_range_table_size += PFEM_RANGE_TABLE_INCR;
      pfem_range_table = (pfem_range *) 
                         xrealloc (pfem_range_table, 
                                   sizeof (pfem_range) 
                                   * pfem_range_table_size);
    }

  /* Entries in the range table need to be sorted by address.  Perform
     an insertion sort.  Find where the entry goes, shift the rest of 
     the table up, and fill in the range entry.  We coalesce
     contiguous entries, i.e., adjacent ranges are combined into a
     single, larger range.  */
  for (range_idx = 0; range_idx < pfem_range_table_nitems; range_idx++)
    if (start_addr < pfem_range_table[range_idx].start_addr)
      if (end_addr == pfem_range_table[range_idx].start_addr)
        {
          /* The block is just in front of this range, so extend the
             range.  */
          pfem_range_table[range_idx].start_addr = start_addr;
          return;
        }
      else
	{
	  /* The block needs to go before the current entry in the
	     range table, so we move the following entries up to
	     make room for the new entry.  Then we drop out of the
	     loop to where the new entry is added.  */
	  memmove (&pfem_range_table[range_idx + 1], 
		   &pfem_range_table[range_idx], 
		   sizeof (pfem_range) 
		   * (pfem_range_table_nitems - range_idx));
	  break;
	}
    else if (start_addr == pfem_range_table[range_idx].end_addr)
      {
        /* The block follows immediately after this range, so extend
           the range.  */
        pfem_range_table[range_idx].end_addr = end_addr;
        return;
      }
  pfem_range_table[range_idx].start_addr = start_addr;
  pfem_range_table[range_idx].end_addr = end_addr;
  pfem_range_table_nitems++;
}

#if MINIMIZE_RANGES
/* Remove a memory block from the range table.  This is called to
   remove unused (freed) blocks when pfem_id_ranges is called to 
   provide information about what memory ranges are being used.  */

void
pfem_remove_block_from_range_table (block_addr, size)
     void *block_addr;
     size_t size;
{
  int range_idx;
  unsigned long start_addr = (unsigned long)block_addr;
  unsigned long end_addr = start_addr + size;

  /* Entries in the range table are sorted by address.  Find where the 
     range is in the table.  The range we are removing is from a block
     that was used to create the range table, so it should be
     contained in one of the ranges in the table.  */
  for (range_idx = 0; range_idx < pfem_range_table_nitems; range_idx++)
    if (pfem_range_table[range_idx].end_addr >= start_addr)
      {
        /* The range to remove is contained in the current range in
           the range table.  */
        if (start_addr == pfem_range_table[range_idx].start_addr)
          {
            /* The range we are removing begins at the beginning
               of one of the ranges in the table.  */
            if (end_addr == pfem_range_table[range_idx].end_addr)
              {
                /* We are removing a whole range.  Remove the entry
                   and move the rest of the table down.  */
		pfem_range_table_nitems--;
		memmove (&pfem_range_table[range_idx], 
			 &pfem_range_table[range_idx + 1], 
			 sizeof (pfem_range) 
			 * (pfem_range_table_nitems - range_idx));
              }
            else
              {
                /* We are removing part of a range, starting at the
                   beginning of the range, so we move up the start.  */
                pfem_range_table[range_idx].start_addr = end_addr;
              }
          }
        else
          {
            /* The start of the range to remove is in the middle of
               this range.  */
            if (end_addr == pfem_range_table[range_idx].end_addr)
              {
                /* We are removing a bit of the end of this range.
                   Cut its end back.  */
                pfem_range_table[range_idx].end_addr = start_addr;
              }
            else
              {
                /* Neither the start of the end match the endpoints
                   of this range, so we are removing a bit out of
                   the middle of the range.  This means we have to
                   split the range.  */
                unsigned long new_start_addr = end_addr;
                unsigned long new_end_addr = pfem_range_table[range_idx].end_addr;
                
                pfem_range_table[range_idx].end_addr = start_addr;
		
		/* Check whether we need to grow the size of the range table.  */
		if (pfem_range_table_nitems >= pfem_range_table_size)
		  {
		    pfem_range_table_size += 2;
		    pfem_range_table = (pfem_range *) 
					   pfem_realloc (pfem_range_table, 
						     sizeof (pfem_range) 
						     * pfem_range_table_size);
		  }
		
		/* Move the remainder of the dump table up to make
		   room for the new entry.  */
		memmove (&pfem_range_table[range_idx + 2], 
			 &pfem_range_table[range_idx + 1], 
			 sizeof (pfem_range) 
			 * (pfem_range_table_nitems - range_idx));
		pfem_range_table_nitems++;
		range_idx++;
                pfem_range_table[range_idx].start_addr = new_start_addr;
                pfem_range_table[range_idx].end_addr = new_end_addr;
              }
          }
        return;
      }
}
#endif

/* PFE low-level memory manager's block allocator.  This function
   checks internally for allocation failures, so that users need not
   check.  */

void *
pfem_alloc_block (size)
     size_t size;
{
  char *data;
#if APPLE_OS_X_IMPLEMENTATION
  kern_return_t err;
  err = vm_allocate ((vm_map_t) mach_task_self (), (vm_address_t) &data,
  		     size, TRUE);
  if (err != KERN_SUCCESS)
    data = NULL;
#else
  data = xmalloc (size);
#endif
  if (data == NULL)
    {
      printf ("pfem_alloc_block: system allocator failure.\n");
      exit (1);
    }
  if (pfem_initialization_complete)
    pfem_add_block_to_range_table (data, size);
#if PFEM_DIAGNOSTICS
  {
    int alignment;
    unsigned long data2 = (unsigned long) data;
    
    for (alignment = 0; (data2 & 1) == 0; alignment++)
      data2 >>= 1;
    printf ("pfem_alloc_block: allocated block at 0x%x of size %d"
    	    " (2**%d alignment)\n",
  	    data, size, alignment);
  }
#endif
  return data;
}

/* Set up the first fragment in a fragmentable block.  The first
   fragment is the pfem_block_info entry for the block itself.  */

pfem_block_info *
pfem_set_up_frag_block (block_addr, size)
     void *block_addr;
     size_t size;
{
  pfem_fragment *fragment;
  pfem_block_info *block_info;
  
  /* First we carve out a first fragment that will contain the block
     info entry for the fragmentable block that we are allocating.  */
  
  fragment = (pfem_fragment *) block_addr;
  fragment->size = sizeof (pfem_block_info);
  block_info = (pfem_block_info *) &fragment->next;
  
  /* Now create the fragment making up the usable/free portion of
     the block.  */
  fragment = (pfem_fragment *) ((unsigned long) block_addr 
  				+ sizeof (pfem_block_info)
  				+ PFEM_FRAGMENT_OVERHEAD);
  fragment->size = size - (sizeof (pfem_block_info) 
  			   + PFEM_FRAGMENT_OVERHEAD);
  fragment->next = NULL;
  
  /* Initialize the block info entry.  */
  block_info->addr = block_addr;
  block_info->size = size;
  block_info->next = NULL;
  block_info->next_avail = NULL;
  block_info->free_fragments = fragment;
  block_info->free_bytes = fragment->size;
  block_info->largest_free_fragment_size = fragment->size;
  
  return block_info;
}

/* Allocate a large whole (non-fragmentable) memory block.  Such
   blocks have a size of at least PFEM_MIN_WHOLE_BLOCK_SIZE.  */

void * 
pfem_alloc_whole_block (size)
     size_t size;
{
  pfem_block_info *block_info;
  pfem_block_info *last_block_info;
  pfem_block_info *best_block_info = NULL;
  size_t bytes_needed;
  void *block_addr;
  
#if PFEM_DEBUG
  printf ("pfem_alloc_whole_block: request size = %d\n", size);
#endif
  
  /* Adjust the size (if necessary) so as not to create blocks with
     weird sizes.  Right now this rounds to multiples of 1K.  */
  bytes_needed = (size + 1023) & 0xFFFFFC00;

#if PFEM_DEBUG
  printf ("  pfem_alloc_whole_block: bytes_needed = %d\n", bytes_needed);
#endif
  
  /* See if there is a whole block that has been freed that can be 
     used.  Look for an exact size match, but remember the best 
     match as we check the free list.  */
  block_info = pfem_whole_block_avail_list;
  last_block_info = NULL;
  while (block_info != NULL)
    {
      if (block_info->size == bytes_needed)
	{
	  /* We found a block that is just the right size.
	     Remove it from the whole block avail list.  */
	  if (last_block_info == NULL)
	    pfem_whole_block_avail_list = block_info->next_avail;
	  else
	    last_block_info->next_avail = block_info->next_avail;
	  block_info->free_bytes = 0;
#if PFEM_DEBUG
	  printf ("  pfem_alloc_whole_block: allocated free block at 0x%x\n", 
		  block_info->addr);
#endif
	  return block_info->addr;
	}
      else if ((block_info->size > bytes_needed))
	{
	  /* ??? If we find a block that is big enough to split and
	     satisfy the request with the remainder still being
	     large enough to be a whole block, consider splitting the
	     block and keeping the remainder in play.  */
	  if ((best_block_info == NULL)
	      || (block_info->size < best_block_info->size))
	    best_block_info = block_info;
	}
      last_block_info = block_info;
      block_info = block_info->next_avail;
    }
  if (best_block_info != NULL)
    {
      /* Consider whether to use the best fit of larger available
	 blocks.  */
      /* ??? Consider what would be an acceptable variance.  */
      /* ??? We may want to break a block up into two whole blocks,
	 or even convert a portion into a fragmentable block.  */
#if PFEM_DEBUG
      printf ("  pfem_alloc_whole_block: bytes_needed = %d;"
	      " best fit found = %d\n", 
	      bytes_needed, best_block_info->size);
#endif
    }
  
  /* Allocate a new whole block and the corresponding block info
     entry.  Fill in the block info entry and add it to the block
     list.  */
  block_addr = pfem_alloc_block (bytes_needed);
  block_info = (pfem_block_info *) pfem_malloc (sizeof (pfem_block_info));
  if (block_info == NULL)
    {
      printf ("pfem_alloc_whole_block: block_info == NULL.\n");
      exit (1);
    }
  block_info->addr = block_addr;
  block_info->size = bytes_needed;
  block_info->free_bytes = 0;
  block_info->largest_free_fragment_size = 0;
  block_info->free_fragments = PFEM_INVALID_PTR;
  block_info->next = NULL;
  block_info->next_avail = NULL;
  pfem_add_block_to_block_list (block_info);
  return block_addr;
}

/* Allocate a fragment of memory, where a fragment is a piece of a 
   larger memory block allocated by the underlying system allocator
   and managed by the pfe-mem system.  Such fragments have a size of 
   smaller than PFEM_MAX_FRAGMENT_SIZE.  */

void * 
pfem_alloc_fragment (size)
     size_t size;
{
#define USE_BLOCK_ROVER 1
#if USE_BLOCK_ROVER
  static pfem_block_info *block_rover = NULL;
#endif
  pfem_block_info *block_info;
  size_t bytes_needed;
  void *block_addr;
  struct best_match_t {
    pfem_block_info *block;
    pfem_fragment *fragment;
    pfem_fragment *last_fragment;
    size_t difference;
    int tries;
  } best_match = { NULL, NULL, NULL, PFEM_FRAG_BLOCK_SIZE, 0 };
  
#if PFEM_DEBUG
  static int call_nbr = 0;
  printf ("pfem_alloc_fragment[%d]: request size = %d\n", ++call_nbr, size);
  if (call_nbr == 0)
    printf ("break here\n");
#endif

  /* Determine the size needed actually needed given the overhead for
     fragments.  */
  bytes_needed = size + PFEM_FRAGMENT_OVERHEAD;
#if PFEM_DEBUG
  printf ("  pfem_alloc_fragment: bytes_needed (with overhead) = %d\n", 
  	  bytes_needed);
#endif
  // ??? Take minimum alignment into account.  Compute this more elegantly.
  bytes_needed = (bytes_needed + 3) & 0xFFFFFFFC;
  
#if PFEM_DEBUG
  printf ("  pfem_alloc_fragment: bytes_needed (after alignment) = %d\n", 
  	  bytes_needed);
#endif

  /* Find a block with enough space available to do the allocation.  */
#if USE_BLOCK_ROVER
  /* Move the rover to the next block after the block from which we
     last allocated.  Initialize the rover if necessary.  If the 
     rover is at the end of the list, move it to the beginning.  */
  if ((block_rover == NULL) || (block_rover->next_avail == NULL))
    block_rover = pfem_frag_block_avail_list;
  else
    block_rover = block_rover->next_avail;
  block_info = block_rover;
#else
  block_info = pfem_frag_block_avail_list;
#endif
  while (1)
    {
      if (block_info == NULL)
	{
	  /* We are at the end of the block list.  Allocate another
	     fragmentable block.  */
	  pfem_block_info *new_block_info;
	  
	  /* Here we have a potentially tricky situation since we
	     need to allocate a new fragmentable block because we 
	     can't satisfy a fragment allocation request, and, in
	     order to allocate the new block we also have to allocate
	     a new fragment for the new block's block info entry.
	     This issue led to the decision to allocate the fragment
	     for the block info entry as the first fragment in the
	     new fragmentable block.  */
	  block_addr = pfem_alloc_block (PFEM_FRAG_BLOCK_SIZE);
	  new_block_info = pfem_set_up_frag_block (block_addr, 
	  					   PFEM_FRAG_BLOCK_SIZE);
	  pfem_add_block_to_block_list (new_block_info);
	  
	  /* Put the block in the fragmented block avail list.  */
	  new_block_info->next_avail = pfem_frag_block_avail_list;
	  pfem_frag_block_avail_list = new_block_info;

	  /* Set up to use the new block now.  */
	  block_info = new_block_info;

#if USE_BLOCK_ROVER
	  /* Set the block rover to the new block so that the next
	     allocation search will begin after the new block.  */
          block_rover = block_info;
#endif
#if PFEM_DEBUG
	  printf ("  pfem_alloc_fragment: allocating a new block at 0x%x\n",
		  block_addr);
#endif
	}
#if PFEM_DEBUG
      printf ("  pfem_alloc_fragment: checking block_info at 0x%x\n", 
      	      block_info);
      if (block_info != NULL)
	{
      	  printf ("    pfem_alloc_fragment: block size = %d\n", 
      	  	  block_info->size);
      	  printf ("    pfem_alloc_fragment: block free_bytes = %d\n", 
      	  	  block_info->free_bytes);
      	  printf ("    pfem_alloc_fragment: block largest_free_fragment_size = %d\n", 
      	  	  block_info->largest_free_fragment_size);
      	  printf ("    pfem_alloc_fragment: block free_fragments = 0x%x\n", 
      	  	  block_info->free_fragments);
      	  printf ("    pfem_alloc_fragment: block next = 0x%x\n", 
      	  	  block_info->next);
      	  printf ("    pfem_alloc_fragment: block next_avail = 0x%x\n", 
      	  	  block_info->next_avail);
	}
#endif
#if 0
      // FIXME: keep largest_free_fragment_size up-to-date
      if (bytes_needed <= block_info->largest_free_fragment_size)
        {
	  /* This block has a fragment that is big enough.  Walk the
	     fragment list and find one to use.  */
#else
      if (bytes_needed <= block_info->free_bytes)
        {
	  /* This block may have a fragment that is big enough.  Walk 
	     the fragment list and find one to use.  */
#endif
	  pfem_fragment *fragment = block_info->free_fragments;
	  pfem_fragment *last_fragment = NULL;
	  while (fragment != NULL)
	    {
#if PFEM_DEBUG
	      printf ("  pfem_alloc_fragment: checking fragment of size %d [0x%x] at 0x%x\n",
		      fragment->size, fragment->size, fragment);
	      if (fragment->size > PFEM_FRAG_BLOCK_SIZE)
	        printf ("  ***pfem_alloc_fragment: invalid fragment size.\n");
#endif
	      if (fragment->size >= bytes_needed)
	        {
	          /* See how much extra space there is in the 
	             fragment and decide whether to split it or 
	             not.  */
	          size_t difference = fragment->size - bytes_needed;
	          
#if PFEM_DEBUG
	          printf ("  pfem_alloc_fragment: difference = %d\n", difference);
#endif
	          if (difference > MAX_FRAGMENT_SIZE_VARIANCE_BEFORE_SPLIT)
	            {
	              /* The fragment is big enough that it needs to 
	                 be split.  We split the fragment so that the
	                 allocation will be made from the start of
	                 the fragment and the remainder will be put
	                 on the free fragment list.  */
	              pfem_fragment *new_fragment = (pfem_fragment *) 
	      		((unsigned long)fragment + bytes_needed);
#if PFEM_DEBUG
  		      printf ("  pfem_alloc_fragment: splitting fragment of size %d at 0x%x\n",
  	  		      fragment->size, fragment);
#endif
	      	      new_fragment->size = difference;
	      	      new_fragment->next = fragment->next;
#if PFEM_DEBUG
  		      printf ("  pfem_alloc_fragment: creating new fragment of size %d at 0x%x\n",
  	  		      new_fragment->size, new_fragment);
#endif
	      	      fragment->size = bytes_needed;
	      	      fragment->next = new_fragment;
	            }
	          /* Take the fragment out of the free fragment list.  */
		  if (last_fragment == NULL)
		    block_info->free_fragments = fragment->next;
		  else
		    last_fragment->next = fragment->next;
	          block_info->free_bytes -= fragment->size;
#if PFEM_DEBUG
		  printf ("  pfem_alloc_fragment: allocated fragment at 0x%x of size %d\n",
			  &fragment->next, fragment->size - PFEM_FRAGMENT_OVERHEAD);
#endif
		  return &fragment->next;
	        }
	      last_fragment = fragment;
	      fragment = fragment->next;
	    }
#if 0
	  /* We should not get here.  If we do, we did not find a
	     fragment that was big enough, even though the 
	     largest_free_fragment_size field in the block info
	     indicated we should.  */
	  printf ("  ***pfem_alloc_fragment: did not find fragment.  "
	  	  "largest_free_fragment_size incorrect\n");
#else
	  /* ??? The largest_free_fragment_size field is not yet being 
	     properly maintained.  For now we continue on and try the
	     next block.  */
#endif
        }
      block_info = block_info->next_avail;
#if USE_BLOCK_ROVER
      /* If we reach the end of the list when starting from a rover
         block we start over from the beginning.  If we reach the
         rover again, we have gone all the way around the list, so
         we signal that we've reached the end by setting block_info 
         to NULL.  */
      if (block_info == NULL)
        block_info = pfem_frag_block_avail_list;
      if (block_info == block_rover)
        block_info = NULL;
#endif
    }
}
  
/* PFE low-level memory manager's malloc.  Depending on the size of
   the request we either allocate a whole (non-fragmentable) block,
   or a fragment of a bigger block.  */

void * 
pfem_malloc (size)
     size_t size;
{
#if PFEM_DEBUG
  printf ("pfem_malloc: request size = %d\n", size);
#endif
  if (size > PFEM_MAX_FRAGMENT_SIZE)
    return pfem_alloc_whole_block (size);
  else
    return pfem_alloc_fragment (size);
}

/* PFE low-level memory manager's free.  */

void 
pfem_free (ptr)
     void *ptr;
{
  pfem_block_info *block_info;
  pfem_block_info *last_block_info;
  pfem_fragment *fragment_to_free;
  pfem_fragment *fragment;
  pfem_fragment *last_fragment;

  if (!ptr) return;
  
#if PFEM_DEBUG
  printf ("pfem_free: object at 0x%x\n", ptr);
#endif
  /* Find the block containing the object to be freed.  */
  last_block_info = NULL;
  for (block_info = pfem_block_list; 
       block_info != NULL; 
       block_info = block_info->next)
    {
      if ((unsigned long) ptr == (unsigned long) block_info->addr)
        {
          /* The pointer points to the beginning of a block.  This
             should be a pointer to a whole block which can now be
             marked as free.  Anything else is an error because we
             should not have get a pointer to the beginning of a
             fragmentable block because the pointer we give out
             for the first fragment will be 4 bytes into the block,
             due to the leading (hidden) size field.  */
          if (PFEM_IS_WHOLE_BLOCK (block_info))
            {
              if (block_info->free_bytes == block_info->size)
                {
		  printf ("pfem_free: freeing an already free whole block (0x%x).\n",
			  ptr);
		  return;
                }
              /* ??? Consider coalescing blocks on the whole block
                 avail list.  */
              block_info->free_bytes = block_info->size;
              block_info->next_avail = pfem_whole_block_avail_list;
              pfem_whole_block_avail_list = block_info;
#if PFEM_DEBUG
  	      printf ("  pfem_free: freed whole block at 0x%x\n", ptr);
#endif
              return;
            }
          else
            {
	      printf ("pfem_free: trying to free a fragment block (0x%x).\n",
	      	      ptr);
	      exit (1);
            }
        }
      else if ((unsigned long) ptr < (unsigned long) block_info->addr)
        {
          /* The pointer should be somewhere in the preceeding block,
             which should be a fragmentable block, given the pointer
             points to something inside it.  */
          break;
        }
      last_block_info = block_info;
    }
  
  /* If we get here, the object to be freed should be a fragment in 
     the last block.  */
  if (((unsigned long) ptr < (unsigned long) last_block_info->addr)
      || ((unsigned long)ptr >= ((unsigned long) last_block_info->addr
  			 	 + last_block_info->size)))
    {
      printf ("pfem_free: trying to free memory (0x%x) not allocated by "
      	      "the memory manager.\n", ptr);
      exit (1);
    }
  
  /* The block should be a fragmentable block.  */
  if (PFEM_IS_WHOLE_BLOCK (last_block_info))
    {
      printf ("pfem_free: trying to free a fragment (0x%x) in a "
      	      "non-fragmentable block (0x%x).\n", ptr, last_block_info->addr);
      exit (1);
    }
  
  fragment_to_free = (pfem_fragment *) ((unsigned long) ptr - PFEM_FRAGMENT_OVERHEAD);
#if PFEM_DEBUG
  printf ("  pfem_free: freeing fragment at 0x%x of size %d\n", 
  	  fragment_to_free, fragment_to_free->size);
  if (fragment_to_free->size > PFEM_FRAG_BLOCK_SIZE)
    printf ("  ***pfem_free: size > PFEM_FRAG_BLOCK_SIZE\n"); 
#endif
  
  /* If the block has no free fragments, put this one on the list.  */
  if (last_block_info->free_fragments == NULL)
    {
      last_block_info->free_fragments = fragment_to_free;
      fragment_to_free->next = NULL;
      last_block_info->free_bytes = fragment_to_free->size;
      last_block_info->largest_free_fragment_size = fragment_to_free->size;
      return;
    }
  
  /* Find where this fragment goes in the block's fragment list.  */
  last_fragment = NULL;
  for (fragment = last_block_info->free_fragments;
       fragment != NULL;
       fragment = fragment->next)
    {
      if ((unsigned long) fragment_to_free < (unsigned long) fragment)
        break;
      if ((unsigned long) fragment_to_free == (unsigned long) fragment)
        {
	  printf ("pfem_free: attempt to free an already free fragment "
	   	  "(0x%x).\n", fragment_to_free);
          exit (1);
        }
      last_fragment = fragment;
    }
  
  /* Put the fragment into the fragment list.  See whether it can be
     coalesced with the preceeding and/or following block.  If any
     coalescing takes place, we take care to set fragment_to_free
     to the coalesced block to simplify the bookkeeping for the
     block's largest_free_fragment_size.  */
  last_block_info->free_bytes += fragment_to_free->size;
  if (last_fragment == NULL)
    {
      /* The fragment goes before the first fragment in the free list.  */
      last_block_info->free_fragments = fragment_to_free;
    }
  else
    {
      /* There is a preceeding fragment.  See if we can coalesce with
         that.  */
      if (((unsigned long) last_fragment + last_fragment->size)
      	  == (unsigned long) fragment_to_free)
      	{
      	  last_fragment->size += fragment_to_free->size;
      	  fragment_to_free = last_fragment;
#if PFEM_DEBUG
  	  if (last_fragment->size > last_block_info->size)
  	    printf ("***pfem_free: coalesced fragment at 0x%x has size (%d) "
  	    	    "bigger than containing block at 0x%x.\n", 
  	    	    last_fragment, last_fragment->size, last_block_info);
#endif
      	}
       else
        last_fragment->next = fragment_to_free;
    }
  if (fragment == NULL)
    {
      /* The fragment is at the end of the free list.  */
      fragment_to_free->next = NULL;
    }
  else
    {
      /* There is a following fragment.  See if we can coalesce with
         that.  */
      if (((unsigned long) fragment_to_free + fragment_to_free->size)
	   == (unsigned long) fragment)
	{
	  /* Coalesce with the following fragment.  */
	  fragment_to_free->size += fragment->size;
	  fragment_to_free->next = fragment->next;
#if PFEM_DEBUG
  	  if (fragment_to_free->size > last_block_info->size)
  	    printf ("***pfem_free: coalesced fragment at 0x%x has size (%d) "
  	    	    "bigger than containing block at 0x%x.\n", 
  	    	    fragment_to_free, fragment_to_free->size, last_block_info);
#endif
	}
      else
	{
	  fragment_to_free->next = fragment;
	}
    }
  if (fragment_to_free->size > last_block_info->largest_free_fragment_size)
    last_block_info->largest_free_fragment_size = fragment_to_free->size;
}

/* PFE low-level memory manager's calloc: allocates and zeros memory 
   for n objects.  */

void * 
pfem_calloc (nobj, size)
     size_t nobj;
     size_t size;
{
  void *p;
  
  p = pfem_malloc (nobj * size);
  if (p != NULL)
    memset (p, 0, nobj * size);
  return p;
}

/* PFE low-level memory manager's realloc: reallocates memory given
   a pointer to a previous memory allocation.  */

void * 
pfem_realloc (p, size)
     void *p;
     size_t size;
{
  void *p2;
  pfem_block_info *block;
  size_t old_size;
  
  /* Alloc the new memory.  If we fail return NULL and leave the
     original pointer intact.  */
  p2 = pfem_malloc (size);
  if (p2 == NULL)
    return NULL;

  /* Copy the data from the old object to the new object, copying an
     amount determined by the smallest sized object.  In order to 
     determine the old size, we first need to know whether we have a
     whole block or a fragment.  We need to walk the block list to 
     determine what we have.  Free the old pointer.  Note that the
     original pointer is allowed to be NULL, in which case the 
     function behaves like malloc.  */
  if (p != NULL)
    {
      block = pfem_find_containing_block (p);
      if (block == NULL)
	{
	  printf ("pfem_realloc: attempt to realloc from a pointer not alloced.\n");
	  exit (1);
	}
      if (PFEM_IS_WHOLE_BLOCK (block))
	if (p == block->addr)
	  old_size = block->size;
	else
	  {
	    printf ("pfem_realloc: attempt to realloc from inside an alloced object.\n");
	    exit (1);
	  }
      else
	{
	  pfem_fragment *f = (pfem_fragment *) ((unsigned long) p - PFEM_FRAGMENT_OVERHEAD);
	  old_size = f->size;
	}
      memcpy (p2, p, (size < old_size) ? size : old_size);
      pfem_free (p);
    }
  return p2;
}

/* Identify ranges of memory used by the low-level memory manager.
   The parameter is a pointer to a call-back function that is passed
   the end-points of the memory range.  This should only be called
   once at the end of the use of the PFE memory management system
   since this function will modify (minimize) the address range table
   to reflect the memory usage at the point the routine is called.  
   
   NOTE: The current minimization of the block table adjusts the
   block table so that it reflects the memory in use, but not the
   memory that has been allocated.  Thus it is out of sync with the
   other memory structures.  As long as this happens, it will not
   be possible to dump these memory structures and use them after a
   load, unless the structures are brought into sync again.  */

void 
pfem_id_ranges (id_range_fp)
     void (*id_range_fp)(unsigned long, unsigned long);
{
  int range_idx;
#if MINIMIZE_RANGES
  pfem_block_info *block;
  pfem_fragment *fragment;
  pfem_fragment *last_fragment;
  
  /* Minimize the address range table.  */
  for (block = pfem_whole_block_avail_list; block != NULL; block = block->next_avail)
    pfem_remove_block_from_range_table (block->addr, block->size);
  
  /* Minimize the fragmentable block ranges.  For starters, reduce
     the most recent fragmentable block.  */
  for (block = pfem_frag_block_avail_list; block != NULL; block = block->next_avail)
    {
      last_fragment = NULL;
      for (fragment = block->free_fragments; fragment != NULL; fragment = fragment->next)
        last_fragment = fragment;
      if ((last_fragment != NULL) 
      	  && (((unsigned long) last_fragment + last_fragment->size)
      	      == ((unsigned long) block->addr + block->size))
      	  && (last_fragment->size >= PFEM_MIN_RECOVERABLE_FRAGMENT_SIZE))
      	pfem_remove_block_from_range_table (last_fragment, last_fragment->size);
    }
#endif

  /* Inform the PFE about ranges by making a call through the 
     function pointer to identify each range.  */
  for (range_idx = 0; range_idx < pfem_range_table_nitems; range_idx++)
    (*id_range_fp) (pfem_range_table[range_idx].start_addr,
    		    pfem_range_table[range_idx].end_addr);
}

/* Indicates if the pointer is to memory controlled by the PFE 
   memory manager.  (The memory may not currently be allocated.)  */

int 
pfem_is_pfe_mem (ptr)
     void *ptr;
{
  int lower_idx = 0;
  int upper_idx = pfem_range_table_nitems - 1;
  int middle_idx;
  
  while (lower_idx <= upper_idx)
    {
      middle_idx = (lower_idx + upper_idx) / 2;
      if ((unsigned long) ptr < pfem_range_table[middle_idx].start_addr)
	upper_idx = middle_idx - 1;
      else if ((unsigned long) ptr >= pfem_range_table[middle_idx].end_addr)
	lower_idx = middle_idx + 1;
      else
	return 1;
    }
  return 0;
}