ralloc.c

内存分配的各种包装函数

  for (b = bloc; b != NIL_BLOC; b = b->next)
    {
      /* Advance through heaps, marking them empty,
	 till we get to the one that B is in.  */
      while (heap)
	{
	  if (heap->bloc_start <= b->data && b->data <= heap->end)
	    break;
	  heap = heap->next;
	  /* We know HEAP is not null now,
	     because there has to be space for bloc B.  */
	  heap->first_bloc = NIL_BLOC;
	  heap->last_bloc = NIL_BLOC;
	  heap->free = heap->bloc_start;
	}

      /* Update HEAP's status for bloc B.  */
      heap->free = b->data + b->size;
      heap->last_bloc = b;
      if (heap->first_bloc == NIL_BLOC)
	heap->first_bloc = b;

      /* Record that B is in HEAP.  */
      b->heap = heap;
    }

  /* If there are any remaining heaps and no blocs left,
     mark those heaps as empty.  */
  heap = heap->next;
  while (heap)
    {
      heap->first_bloc = NIL_BLOC;
      heap->last_bloc = NIL_BLOC;
      heap->free = heap->bloc_start;
      heap = heap->next;
    }
}

/* Resize BLOC to SIZE bytes.  This relocates the blocs
   that come after BLOC in memory.  */

static int
resize_bloc (bloc, size)
    bloc_ptr bloc;
    SIZE size;
{
  register bloc_ptr b;
  heap_ptr heap;
  POINTER address;
  SIZE old_size;

  if (bloc == NIL_BLOC || size == bloc->size)
    return 1;

  for (heap = first_heap; heap != NIL_HEAP; heap = heap->next)
    {
      if (heap->bloc_start <= bloc->data && bloc->data <= heap->end)
	break;
    }

  if (heap == NIL_HEAP)
    abort ();

  old_size = bloc->size;
  bloc->size = size;

  /* Note that bloc could be moved into the previous heap.  */
  address = (bloc->prev ? bloc->prev->data + bloc->prev->size
	     : first_heap->bloc_start);
  while (heap)
    {
      if (heap->bloc_start <= address && address <= heap->end)
	break;
      heap = heap->prev;
    }

  if (! relocate_blocs (bloc, heap, address))
    {
      bloc->size = old_size;
      return 0;
    }

  if (size > old_size)
    {
      for (b = last_bloc; b != bloc; b = b->prev)
	{
	  safe_bcopy (b->data, b->new_data, b->size);
	  *b->variable = b->data = b->new_data;
	}
      safe_bcopy (bloc->data, bloc->new_data, old_size);
      bzero (bloc->new_data + old_size, size - old_size);
      *bloc->variable = bloc->data = bloc->new_data;
    }
  else
    {
      for (b = bloc; b != NIL_BLOC; b = b->next)
	{
	  safe_bcopy (b->data, b->new_data, b->size);
	  *b->variable = b->data = b->new_data;
	}
    }

  update_heap_bloc_correspondence (bloc, heap);

  break_value = (last_bloc ? last_bloc->data + last_bloc->size
		 : first_heap->bloc_start);
  return 1;
}

/* Free BLOC from the chain of blocs, relocating any blocs above it.
   This may return space to the system.  */

static void
free_bloc (bloc)
     bloc_ptr bloc;
{
  heap_ptr heap = bloc->heap;

  resize_bloc (bloc, 0);

  if (bloc == first_bloc && bloc == last_bloc)
    {
      first_bloc = last_bloc = NIL_BLOC;
    }
  else if (bloc == last_bloc)
    {
      last_bloc = bloc->prev;
      last_bloc->next = NIL_BLOC;
    }
  else if (bloc == first_bloc)
    {
      first_bloc = bloc->next;
      first_bloc->prev = NIL_BLOC;
    }
  else
    {
      bloc->next->prev = bloc->prev;
      bloc->prev->next = bloc->next;
    }

  /* Update the records of which blocs are in HEAP.  */
  if (heap->first_bloc == bloc)
    {
      if (bloc->next->heap == heap)
	heap->first_bloc = bloc->next;
      else
	heap->first_bloc = heap->last_bloc = NIL_BLOC;
    }
  if (heap->last_bloc == bloc)
    {
      if (bloc->prev->heap == heap)
	heap->last_bloc = bloc->prev;
      else
	heap->first_bloc = heap->last_bloc = NIL_BLOC;
    }

  relinquish ();
  free (bloc);
}

/* Interface routines.  */

static int use_relocatable_buffers;
static int r_alloc_freeze_level;

/* Obtain SIZE bytes of storage from the free pool, or the system, as
   necessary.  If relocatable blocs are in use, this means relocating
   them.  This function gets plugged into the GNU malloc's __morecore
   hook.

   We provide hysteresis, never relocating by less than extra_bytes.

   If we're out of memory, we should return zero, to imitate the other
   __morecore hook values - in particular, __default_morecore in the
   GNU malloc package.  */

POINTER 
r_alloc_sbrk (size)
     long size;
{
  register bloc_ptr b;
  POINTER address;

  if (! use_relocatable_buffers)
    return (*real_morecore) (size);

  if (size == 0)
    return virtual_break_value;

  if (size > 0)
    {
      /* Allocate a page-aligned space.  GNU malloc would reclaim an
	 extra space if we passed an unaligned one.  But we could
	 not always find a space which is contiguos to the previous.  */
      POINTER new_bloc_start;
      heap_ptr h = first_heap;
      SIZE get = ROUNDUP (size);

      address = (POINTER) ROUNDUP (virtual_break_value);

      /* Search the list upward for a heap which is large enough.  */
      while ((char *) h->end < (char *) MEM_ROUNDUP ((char *)address + get))
	{
	  h = h->next;
	  if (h == NIL_HEAP)
	    break;
	  address = (POINTER) ROUNDUP (h->start);
	}

      /* If not found, obtain more space.  */
      if (h == NIL_HEAP)
	{
	  get += extra_bytes + page_size;

	  if (r_alloc_freeze_level > 0 || ! obtain (address, get))
	    return 0;

	  if (first_heap == last_heap)
	    address = (POINTER) ROUNDUP (virtual_break_value);
	  else
	    address = (POINTER) ROUNDUP (last_heap->start);
	  h = last_heap;
	}

      new_bloc_start = (POINTER) MEM_ROUNDUP ((char *)address + get);

      if (first_heap->bloc_start < new_bloc_start)
	{
	  /* Move all blocs upward.  */
	  if (r_alloc_freeze_level > 0
	      || ! relocate_blocs (first_bloc, h, new_bloc_start))
	    return 0;

	  /* Note that (POINTER)(h+1) <= new_bloc_start since
	     get >= page_size, so the following does not destroy the heap
	     header.  */
	  for (b = last_bloc; b != NIL_BLOC; b = b->prev)
	    {
	      safe_bcopy (b->data, b->new_data, b->size);
	      *b->variable = b->data = b->new_data;
	    }

	  h->bloc_start = new_bloc_start;

	  update_heap_bloc_correspondence (first_bloc, h);
	}

      if (h != first_heap)
	{
	  /* Give up managing heaps below the one the new
	     virtual_break_value points to.  */
	  first_heap->prev = NIL_HEAP;
	  first_heap->next = h->next;
	  first_heap->start = h->start;
	  first_heap->end = h->end;
	  first_heap->free = h->free;
	  first_heap->first_bloc = h->first_bloc;
	  first_heap->last_bloc = h->last_bloc;
	  first_heap->bloc_start = h->bloc_start;

	  if (first_heap->next)
	    first_heap->next->prev = first_heap;
	  else
	    last_heap = first_heap;
	}

      bzero (address, size);
    }
  else /* size < 0 */
    {
      SIZE excess = (char *)first_heap->bloc_start
		      - ((char *)virtual_break_value + size);

      address = virtual_break_value;

      if (r_alloc_freeze_level == 0 && excess > 2 * extra_bytes)
	{
	  excess -= extra_bytes;
	  first_heap->bloc_start
	    = (POINTER) MEM_ROUNDUP ((char *)first_heap->bloc_start - excess);

	  relocate_blocs (first_bloc, first_heap, first_heap->bloc_start);

	  for (b = first_bloc; b != NIL_BLOC; b = b->next)
	    {
	      safe_bcopy (b->data, b->new_data, b->size);
	      *b->variable = b->data = b->new_data;
	    }
	}

      if ((char *)virtual_break_value + size < (char *)first_heap->start)
	{
	  /* We found an additional space below the first heap */
	  first_heap->start = (POINTER) ((char *)virtual_break_value + size);
	}
    }

  virtual_break_value = (POINTER) ((char *)address + size);
  break_value = (last_bloc
		 ? last_bloc->data + last_bloc->size
		 : first_heap->bloc_start);
  if (size < 0)
    relinquish ();

  return address;
}

/* Allocate a relocatable bloc of storage of size SIZE.  A pointer to
   the data is returned in *PTR.  PTR is thus the address of some variable
   which will use the data area.

   If we can't allocate the necessary memory, set *PTR to zero, and
   return zero.  */

POINTER
r_alloc (ptr, size)
     POINTER *ptr;
     SIZE size;
{
  register bloc_ptr new_bloc;

  if (! r_alloc_initialized)
    r_alloc_init ();

  new_bloc = get_bloc (MEM_ROUNDUP (size));
  if (new_bloc)
    {
      new_bloc->variable = ptr;
      *ptr = new_bloc->data;
    }
  else
    *ptr = 0;

  return *ptr;
}

/* Free a bloc of relocatable storage whose data is pointed to by PTR.
   Store 0 in *PTR to show there's no block allocated.  */

void
r_alloc_free (ptr)
     register POINTER *ptr;
{
  register bloc_ptr dead_bloc;

  dead_bloc = find_bloc (ptr);
  if (dead_bloc == NIL_BLOC)
    abort ();

  free_bloc (dead_bloc);
  *ptr = 0;
}

/* Given a pointer at address PTR to relocatable data, resize it to SIZE.
   Do this by shifting all blocks above this one up in memory, unless
   SIZE is less than or equal to the current bloc size, in which case
   do nothing.

   Change *PTR to reflect the new bloc, and return this value.

   If more memory cannot be allocated, then leave *PTR unchanged, and
   return zero.  */

POINTER
r_re_alloc (ptr, size)
     POINTER *ptr;
     SIZE size;
{
  register bloc_ptr bloc;

  bloc = find_bloc (ptr);
  if (bloc == NIL_BLOC)
    abort ();

  if (size <= bloc->size)
    /* Wouldn't it be useful to actually resize the bloc here?  */
    return *ptr;

  if (! resize_bloc (bloc, MEM_ROUNDUP (size)))
    return 0;

  return *ptr;
}

/* Disable relocations, after making room for at least SIZE bytes
   of non-relocatable heap if possible.  The relocatable blocs are
   guaranteed to hold still until thawed, even if this means that
   malloc must return a null pointer.  */

void
r_alloc_freeze (size)
     long size;
{
  /* If already frozen, we can't make any more room, so don't try.  */
  if (r_alloc_freeze_level > 0)
    size = 0;
  /* If we can't get the amount requested, half is better than nothing.  */
  while (size > 0 && r_alloc_sbrk (size) == 0)
    size /= 2;
  ++r_alloc_freeze_level;
  if (size > 0)
    r_alloc_sbrk (-size);
}

void
r_alloc_thaw ()
{
  if (--r_alloc_freeze_level < 0)
    abort ();
}

/* The hook `malloc' uses for the function which gets more space
   from the system.  */
extern POINTER (*__morecore) ();

/* Initialize various things for memory allocation.  */

static void
r_alloc_init ()
{
  if (r_alloc_initialized)
    return;

  r_alloc_initialized = 1;
  real_morecore = __morecore;
  __morecore = r_alloc_sbrk;

  first_heap = last_heap = &heap_base;
  first_heap->next = first_heap->prev = NIL_HEAP;
  first_heap->start = first_heap->bloc_start
    = virtual_break_value = break_value = (*real_morecore) (0);
  if (break_value == NIL)
    abort ();

  page_size = PAGE;
  extra_bytes = ROUNDUP (50000);

  first_heap->end = (POINTER) ROUNDUP (first_heap->start);

  /* The extra call to real_morecore guarantees that the end of the
     address space is a multiple of page_size, even if page_size is
     not really the page size of the system running the binary in
     which page_size is stored.  This allows a binary to be built on a
     system with one page size and run on a system with a smaller page
     size.  */
  (*real_morecore) (first_heap->end - first_heap->start);

  /* Clear the rest of the last page; this memory is in our address space
     even though it is after the sbrk value.  */
  /* Doubly true, with the additional call that explicitly adds the
     rest of that page to the address space.  */
  bzero (first_heap->start, first_heap->end - first_heap->start);
  virtual_break_value = break_value = first_heap->bloc_start = first_heap->end;
  use_relocatable_buffers = 1;
}
#ifdef DEBUG
#include <assert.h>

int
r_alloc_check ()
{
    int found = 0;
    heap_ptr h, ph = 0;
    bloc_ptr b, pb = 0;

    if (!r_alloc_initialized)
      return;

    assert (first_heap);
    assert (last_heap->end <= (POINTER) sbrk (0));
    assert ((POINTER) first_heap < first_heap->start);
    assert (first_heap->start <= virtual_break_value);
    assert (virtual_break_value <= first_heap->end);

    for (h = first_heap; h; h = h->next)
      {
	assert (h->prev == ph);
	assert ((POINTER) ROUNDUP (h->end) == h->end);
	assert ((POINTER) MEM_ROUNDUP (h->start) == h->start);
	assert ((POINTER) MEM_ROUNDUP (h->bloc_start) == h->bloc_start);
	assert (h->start <= h->bloc_start && h->bloc_start <= h->end);

	if (ph)
	  {
	    assert (ph->end < h->start);
	    assert (h->start <= (POINTER)h && (POINTER)(h+1) <= h->bloc_start);
	  }

	if (h->bloc_start <= break_value && break_value <= h->end)
	    found = 1;

	ph = h;
      }

    assert (found);
    assert (last_heap == ph);

    for (b = first_bloc; b; b = b->next)
      {
	assert (b->prev == pb);
	assert ((POINTER) MEM_ROUNDUP (b->data) == b->data);
	assert ((SIZE) MEM_ROUNDUP (b->size) == b->size);

	ph = 0;
	for (h = first_heap; h; h = h->next)
	  {
	    if (h->bloc_start <= b->data && b->data + b->size <= h->end)
		break;
	    ph = h;
	  }

	assert (h);

	if (pb && pb->data + pb->size != b->data)
	  {
	    assert (ph && b->data == h->bloc_start);
	    while (ph)
	      {
		if (ph->bloc_start <= pb->data
		    && pb->data + pb->size <= ph->end)
		  {
		    assert (pb->data + pb->size + b->size > ph->end);
		    break;
		  }
		else
		  {
		    assert (ph->bloc_start + b->size > ph->end);
		  }
		ph = ph->prev;
	      }
	  }
	pb = b;
      }

    assert (last_bloc == pb);

    if (last_bloc)
	assert (last_bloc->data + last_bloc->size == break_value);
    else
	assert (first_heap->bloc_start == break_value);
}
#endif /* DEBUG */