alloc.c

早期freebsd实现

/* Storage allocation and gc for GNU Emacs Lisp interpreter.
   Copyright (C) 1985, 1986 Free Software Foundation, Inc.

This file is part of GNU Emacs.

GNU Emacs 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 1, or (at your option)
any later version.

GNU Emacs 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 Emacs; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */


#include "config.h"
#include "lisp.h"
#ifndef standalone
#include "buffer.h"
#include "window.h"
#endif

#define max(A,B) ((A) > (B) ? (A) : (B))

/* Macro to verify that storage intended for Lisp objects is not
   out of range to fit in the space for a pointer.
   ADDRESS is the start of the block, and SIZE
   is the amount of space within which objects can start.  */
#define VALIDATE_LISP_STORAGE(address, size)			\
do								\
  {								\
    Lisp_Object val;						\
    XSET (val, Lisp_Cons, (char *) address + size);		\
    if ((char *) XCONS (val) != (char *) address + size)	\
      {								\
	free (address);						\
	memory_full ();						\
      }								\
  } while (0)

/* Number of bytes of consing done since the last gc */
int consing_since_gc;

/* Number of bytes of consing since gc before another gc should be done. */
int gc_cons_threshold;

/* value of consing_since_gc when undos were last truncated.  */
int consing_at_last_truncate;

/* Nonzero during gc */
int gc_in_progress;

#ifndef VIRT_ADDR_VARIES
extern
#endif /* VIRT_ADDR_VARIES */
 int malloc_sbrk_used;

#ifndef VIRT_ADDR_VARIES
extern
#endif /* VIRT_ADDR_VARIES */
 int malloc_sbrk_unused;

/* Two thresholds controlling how much undo information to keep.  */
int undo_threshold;
int undo_high_threshold;

/* Non-nil means defun should do purecopy on the function definition */
Lisp_Object Vpurify_flag;

/* Argument we give to Fsignal when memory is full.
   Preallocated since perhaps we can't allocate it when memory is full.  */
Lisp_Object memory_exhausted_message;

#ifndef HAVE_SHM
int pure[PURESIZE / sizeof (int)] = {0,};   /* Force it into data space! */
#define PUREBEG (char *) pure
#else
#define pure PURE_SEG_BITS   /* Use shared memory segment */
#define PUREBEG (char *)PURE_SEG_BITS
#endif /* not HAVE_SHM */

/* Index in pure at which next pure object will be allocated. */
int pureptr;

/* If nonzero, this is a warning delivered by malloc and not yet displayed.  */
char *pending_malloc_warning;

Lisp_Object
malloc_warning_1 (str)
     Lisp_Object str;
{
  Fprinc (str, Vstandard_output);
  write_string ("\nKilling some buffers may delay running out of memory.\n", -1);
  write_string ("However, certainly by the time you receive the 95% warning,\n", -1);
  write_string ("you should clean up, kill this Emacs, and start a new one.", -1);
  return Qnil;
}

/* malloc calls this if it finds we are near exhausting storage */
malloc_warning (str)
     char *str;
{
  pending_malloc_warning = str;
}

display_malloc_warning ()
{
  register Lisp_Object val;

  val = build_string (pending_malloc_warning);
  pending_malloc_warning = 0;
  internal_with_output_to_temp_buffer (" *Danger*", malloc_warning_1, val);
}

/* Called if malloc returns zero */
memory_full ()
{
  while (1)
    Fsignal (Qerror, memory_exhausted_message);
}

/* like malloc and realloc but check for no memory left */

long *
xmalloc (size)
     int size;
{
  register long *val;
  /* Avoid failure if malloc (0) returns 0.  */
  if (size == 0)
    size = 1;
  val = (long *) malloc (size);
  if (!val) memory_full ();
  return val;
}

long *
xrealloc (block, size)
     long *block;
     int size;
{
  register long *val;
  /* Avoid failure if malloc (0) returns 0.  */
  if (size == 0)
    size = 1;
  val = (long *) realloc (block, size);
  if (!val) memory_full ();
  return val;
}

/* Allocation of cons cells */
/* We store cons cells inside of cons_blocks, allocating a new
 cons_block with malloc whenever necessary.  Cons cells reclaimed by
 GC are put on a free list to be reallocated before allocating
 any new cons cells from the latest cons_block.

 Each cons_block is just under 1016 bytes long,
 since malloc really allocates in units of powers of two
 and uses 8 bytes for its own overhead. */

#define CONS_BLOCK_SIZE \
  ((1016 - sizeof (struct cons_block *)) / sizeof (struct Lisp_Cons))

struct cons_block
  {
    struct cons_block *next;
    struct Lisp_Cons conses[CONS_BLOCK_SIZE];
  };

struct cons_block *cons_block;
int cons_block_index;

struct Lisp_Cons *cons_free_list;

void
init_cons ()
{
  cons_block = (struct cons_block *) malloc (sizeof (struct cons_block));
  cons_block->next = 0;
  bzero (cons_block->conses, sizeof cons_block->conses);
  cons_block_index = 0;
  cons_free_list = 0;
}

/* Explicitly free a cons cell.  */
free_cons (ptr)
     struct Lisp_Cons *ptr;
{
  XFASTINT (ptr->car) = (int) cons_free_list;
  cons_free_list = ptr;
}

DEFUN ("cons", Fcons, Scons, 2, 2, 0,
  "Create a new cons, give it CAR and CDR as components, and return it.")
  (car, cdr)
     Lisp_Object car, cdr;
{
  register Lisp_Object val;

  if (cons_free_list)
    {
      XSET (val, Lisp_Cons, cons_free_list);
      cons_free_list = (struct Lisp_Cons *) XFASTINT (cons_free_list->car);
    }
  else
    {
      if (cons_block_index == CONS_BLOCK_SIZE)
	{
	  register struct cons_block *new = (struct cons_block *) malloc (sizeof (struct cons_block));
	  if (!new) memory_full ();
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = cons_block;
	  cons_block = new;
	  cons_block_index = 0;
	  XSET (val, Lisp_Cons, &cons_block->conses[CONS_BLOCK_SIZE - 1]);
	}
      XSET (val, Lisp_Cons, &cons_block->conses[cons_block_index++]);
    }
  XCONS (val)->car = car;
  XCONS (val)->cdr = cdr;
  consing_since_gc += sizeof (struct Lisp_Cons);
  return val;
}

DEFUN ("list", Flist, Slist, 0, MANY, 0,
  "Return a newly created list whose elements are the arguments (any number).")
  (nargs, args)
     int nargs;
     register Lisp_Object *args;
{
  register Lisp_Object len, val, val_tail;

  XFASTINT (len) = nargs;
  val = Fmake_list (len, Qnil);
  val_tail = val;
  while (!NULL (val_tail))
    {
      XCONS (val_tail)->car = *args++;
      val_tail = XCONS (val_tail)->cdr;
    }
  return val;
}

DEFUN ("make-list", Fmake_list, Smake_list, 2, 2, 0,
  "Return a newly created list of length LENGTH, with each element being INIT.")
  (length, init)
     register Lisp_Object length, init;
{
  register Lisp_Object val;
  register int size;

  if (XTYPE (length) != Lisp_Int || XINT (length) < 0)
    length = wrong_type_argument (Qnatnump, length);
  size = XINT (length);

  val = Qnil;
  while (size-- > 0)
    val = Fcons (init, val);
  return val;
}

/* Allocation of vectors */

struct Lisp_Vector *all_vectors;

DEFUN ("make-vector", Fmake_vector, Smake_vector, 2, 2, 0,
  "Return a newly created vector of length LENGTH, with each element being INIT.")
  (length, init)
     register Lisp_Object length, init;
{
  register int sizei, index;
  register Lisp_Object vector;
  register struct Lisp_Vector *p;

  if (XTYPE (length) != Lisp_Int || XINT (length) < 0)
    length = wrong_type_argument (Qnatnump, length);
  sizei = XINT (length);

  p = (struct Lisp_Vector *) malloc (sizeof (struct Lisp_Vector) + (sizei - 1) * sizeof (Lisp_Object));
  if (p == 0)
    memory_full ();
  VALIDATE_LISP_STORAGE (p, 0);

  XSET (vector, Lisp_Vector, p);
  consing_since_gc += sizeof (struct Lisp_Vector) + (sizei - 1) * sizeof (Lisp_Object);

  p->size = sizei;
  p->next = all_vectors;
  all_vectors = p;

  for (index = 0; index < sizei; index++)
    p->contents[index] = init;

  return vector;
}

DEFUN ("vector", Fvector, Svector, 0, MANY, 0,
  "Return a newly created vector with our arguments (any number) as its elements.")
  (nargs, args)
     register int nargs;
     Lisp_Object *args;
{
  register Lisp_Object len, val;
  register int index;
  register struct Lisp_Vector *p;

  XFASTINT (len) = nargs;
  val = Fmake_vector (len, Qnil);
  p = XVECTOR (val);
  for (index = 0; index < nargs; index++)
    p->contents[index] = args[index];
  return val;
}

/* Allocation of symbols.
 Just like allocation of conses!

 Each symbol_block is just under 1016 bytes long,
 since malloc really allocates in units of powers of two
 and uses 8 bytes for its own overhead. */

#define SYMBOL_BLOCK_SIZE \
  ((1016 - sizeof (struct symbol_block *)) / sizeof (struct Lisp_Symbol))

struct symbol_block
  {
    struct symbol_block *next;
    struct Lisp_Symbol symbols[SYMBOL_BLOCK_SIZE];
  };

struct symbol_block *symbol_block;
int symbol_block_index;

struct Lisp_Symbol *symbol_free_list;

void
init_symbol ()
{
  symbol_block = (struct symbol_block *) malloc (sizeof (struct symbol_block));
  symbol_block->next = 0;
  bzero (symbol_block->symbols, sizeof symbol_block->symbols);
  symbol_block_index = 0;
  symbol_free_list = 0;
}

DEFUN ("make-symbol", Fmake_symbol, Smake_symbol, 1, 1, 0,
  "Return a newly allocated uninterned symbol whose name is NAME.\n\
Its value and function definition are void, and its property list is NIL.")
  (str)
     Lisp_Object str;
{
  register Lisp_Object val;
  register struct Lisp_Symbol *p;

  CHECK_STRING (str, 0);

  if (symbol_free_list)
    {
      XSET (val, Lisp_Symbol, symbol_free_list);
      symbol_free_list
	= (struct Lisp_Symbol *) XFASTINT (symbol_free_list->value);
    }
  else
    {
      if (symbol_block_index == SYMBOL_BLOCK_SIZE)
	{
	  struct symbol_block *new = (struct symbol_block *) malloc (sizeof (struct symbol_block));
	  if (!new) memory_full ();
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = symbol_block;
	  symbol_block = new;
	  symbol_block_index = 0;
	}
      XSET (val, Lisp_Symbol, &symbol_block->symbols[symbol_block_index++]);
    }
  p = XSYMBOL (val);
  p->name = XSTRING (str);
  p->plist = Qnil;
  p->value = Qunbound;
  p->function = Qunbound;
  p->next = 0;
  consing_since_gc += sizeof (struct Lisp_Symbol);
  return val;
}

/* Allocation of markers.
 Works like allocation of conses. */

#define MARKER_BLOCK_SIZE \
  ((1016 - sizeof (struct marker_block *)) / sizeof (struct Lisp_Marker))

struct marker_block
  {
    struct marker_block *next;
    struct Lisp_Marker markers[MARKER_BLOCK_SIZE];
  };

struct marker_block *marker_block;
int marker_block_index;

struct Lisp_Marker *marker_free_list;

void
init_marker ()
{
  marker_block = (struct marker_block *) malloc (sizeof (struct marker_block));
  marker_block->next = 0;
  bzero (marker_block->markers, sizeof marker_block->markers);
  marker_block_index = 0;
  marker_free_list = 0;
}

DEFUN ("make-marker", Fmake_marker, Smake_marker, 0, 0, 0,
  "Return a newly allocated marker which does not point at any place.")
  ()
{
  register Lisp_Object val;
  register struct Lisp_Marker *p;

  if (marker_free_list)
    {
      XSET (val, Lisp_Marker, marker_free_list);
      marker_free_list
	= (struct Lisp_Marker *) XFASTINT (marker_free_list->chain);
    }
  else
    {
      if (marker_block_index == MARKER_BLOCK_SIZE)
	{
	  struct marker_block *new = (struct marker_block *) malloc (sizeof (struct marker_block));
	  if (!new) memory_full ();
	  VALIDATE_LISP_STORAGE (new, sizeof *new);
	  new->next = marker_block;
	  marker_block = new;
	  marker_block_index = 0;
	}
      XSET (val, Lisp_Marker, &marker_block->markers[marker_block_index++]);
    }
  p = XMARKER (val);
  p->buffer = 0;
  p->bufpos = 0;
  p->chain = Qnil;
  consing_since_gc += sizeof (struct Lisp_Marker);
  return val;
}

/* Allocation of strings */

/* Strings reside inside of string_blocks.  The entire data of the string,
 both the size and the contents, live in part of the `chars' component of a string_block.
 The `pos' component is the index within `chars' of the first free byte.

 first_string_block points to the first string_block ever allocated.
 Each block points to the next one with its `next' field.
 The `prev' fields chain in reverse order.
 The last one allocated is the one currently being filled.
 current_string_block points to it.

 The string_blocks that hold individual large strings
 go in a separate chain, started by large_string_blocks.  */


/* String blocks contain this many useful bytes.
   8184 is power of 2, minus 8 for malloc overhead. */
#define STRING_BLOCK_SIZE (8184 - sizeof (struct string_block_head))

/* A string bigger than this gets its own specially-made string block
 if it doesn't fit in the current one. */
#define STRING_BLOCK_OUTSIZE 1024

struct string_block_head
  {
    struct string_block *next, *prev;
    int pos;
  };

struct string_block
  {
    struct string_block *next, *prev;
    int pos;
    char chars[STRING_BLOCK_SIZE];
  };

/* This points to the string block we are now allocating strings.  */

struct string_block *current_string_block;

/* This points to the oldest string block, the one that starts the chain.  */

struct string_block *first_string_block;

/* Last string block in chain of those made for individual large strings.  */

struct string_block *large_string_blocks;

/* If SIZE is the length of a string, this returns how many bytes
   the string occupies in a string_block (including padding).  */

#define STRING_FULLSIZE(SIZE)   \
(((SIZE) + 2 * sizeof (int)) & ~(sizeof (int) - 1))

void
init_strings ()
{
  current_string_block = (struct string_block *) malloc (sizeof (struct string_block));
  first_string_block = current_string_block;
  consing_since_gc += sizeof (struct string_block);
  current_string_block->next = 0;
  current_string_block->prev = 0;
  current_string_block->pos = 0;
  large_string_blocks = 0;
}