lib/alloca.c

   1 /* alloca.c -- allocate automatically reclaimed memory
   2    (Mostly) portable public-domain implementation -- D A Gwyn
   3
   4    This implementation of the PWB library alloca function,
   5    which is used to allocate space off the run-time stack so
   6    that it is automatically reclaimed upon procedure exit,
   7    was inspired by discussions with J. Q. Johnson of Cornell.
   8    J.Otto Tennant <jot@cray.com> contributed the Cray support.
   9
  10    There are some preprocessor constants that can
  11    be defined when compiling for your specific system, for
  12    improved efficiency; however, the defaults should be okay.
  13
  14    The general concept of this implementation is to keep
  15    track of all alloca-allocated blocks, and reclaim any
  16    that are found to be deeper in the stack than the current
  17    invocation.  This heuristic does not reclaim storage as
  18    soon as it becomes invalid, but it will do so eventually.
  19
  20    As a special case, alloca(0) reclaims storage without
  21    allocating any.  It is a good idea to use alloca(0) in
  22    your main control loop, etc. to force garbage collection.  */
  23
  24 #include <config.h>
  25
  26 #include <alloca.h>
  27
  28 #include <string.h>
  29 #include <stdlib.h>
  30
  31 #ifdef emacs
  32 # include "lisp.h"
  33 # include "blockinput.h"
  34 # ifdef EMACS_FREE
  35 #  undef free
  36 #  define free EMACS_FREE
  37 # endif
  38 #else
  39 # define memory_full() abort ()
  40 #endif
  41
  42 /* If compiling with GCC or clang, this file is not needed.  */
  43 #if !(defined __GNUC__ || defined __clang__)
  44
  45 /* If someone has defined alloca as a macro,
  46    there must be some other way alloca is supposed to work.  */
  47 # ifndef alloca
  48
  49 #  ifdef emacs
  50 #   ifdef static
  51 /* actually, only want this if static is defined as ""
  52    -- this is for usg, in which emacs must undefine static
  53    in order to make unexec workable
  54    */
  55 #    ifndef STACK_DIRECTION
  56 you
  57 lose
  58 -- must know STACK_DIRECTION at compile-time
  59 /* Using #error here is not wise since this file should work for
  60    old and obscure compilers.  */
  61 #    endif /* STACK_DIRECTION undefined */
  62 #   endif /* static */
  63 #  endif /* emacs */
  64
  65 /* Define STACK_DIRECTION if you know the direction of stack
  66    growth for your system; otherwise it will be automatically
  67    deduced at run-time.
  68
  69    STACK_DIRECTION > 0 => grows toward higher addresses
  70    STACK_DIRECTION < 0 => grows toward lower addresses
  71    STACK_DIRECTION = 0 => direction of growth unknown  */
  72
  73 #  ifndef STACK_DIRECTION
  74 #   define STACK_DIRECTION      0       /* Direction unknown.  */
  75 #  endif
  76
  77 #  if STACK_DIRECTION != 0
  78
  79 #   define STACK_DIR    STACK_DIRECTION /* Known at compile-time.  */
  80
  81 #  else /* STACK_DIRECTION == 0; need run-time code.  */
  82
  83 static int stack_dir;           /* 1 or -1 once known.  */
  84 #   define STACK_DIR    stack_dir
  85
  86 static int
  87 find_stack_direction (int *addr, int depth)
  88 {
  89   int dir, dummy = 0;
  90   if (! addr)
  91     addr = &dummy;
  92   *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1;
  93   dir = depth ? find_stack_direction (addr, depth - 1) : 0;
  94   return dir + dummy;
  95 }
  96
  97 #  endif /* STACK_DIRECTION == 0 */
  98
  99 /* An "alloca header" is used to:
 100    (a) chain together all alloca'ed blocks;
 101    (b) keep track of stack depth.
 102
 103    It is very important that sizeof(header) agree with malloc
 104    alignment chunk size.  The following default should work okay.  */
 105
 106 #  ifndef       ALIGN_SIZE
 107 #   define ALIGN_SIZE   sizeof(double)
 108 #  endif
 109
 110 typedef union hdr
 111 {
 112   char align[ALIGN_SIZE];       /* To force sizeof(header).  */
 113   struct
 114     {
 115       union hdr *next;          /* For chaining headers.  */
 116       char *deep;               /* For stack depth measure.  */
 117     } h;
 118 } header;
 119
 120 static header *last_alloca_header = NULL;       /* -> last alloca header.  */
 121
 122 /* Return a pointer to at least SIZE bytes of storage,
 123    which will be automatically reclaimed upon exit from
 124    the procedure that called alloca.  Originally, this space
 125    was supposed to be taken from the current stack frame of the
 126    caller, but that method cannot be made to work for some
 127    implementations of C, for example under Gould's UTX/32.  */
 128
 129 void *
 130 alloca (size_t size)
 131 {
 132   auto char probe;              /* Probes stack depth: */
 133   register char *depth = &probe;
 134
 135 #  if STACK_DIRECTION == 0
 136   if (STACK_DIR == 0)           /* Unknown growth direction.  */
 137     STACK_DIR = find_stack_direction (NULL, (size & 1) + 20);
 138 #  endif
 139
 140   /* Reclaim garbage, defined as all alloca'd storage that
 141      was allocated from deeper in the stack than currently.  */
 142
 143   {
 144     register header *hp;        /* Traverses linked list.  */
 145
 146 #  ifdef emacs
 147     BLOCK_INPUT;
 148 #  endif
 149
 150     for (hp = last_alloca_header; hp != NULL;)
 151       if ((STACK_DIR > 0 && hp->h.deep > depth)
 152           || (STACK_DIR < 0 && hp->h.deep < depth))
 153         {
 154           register header *np = hp->h.next;
 155
 156           free (hp);            /* Collect garbage.  */
 157
 158           hp = np;              /* -> next header.  */
 159         }
 160       else
 161         break;                  /* Rest are not deeper.  */
 162
 163     last_alloca_header = hp;    /* -> last valid storage.  */
 164
 165 #  ifdef emacs
 166     UNBLOCK_INPUT;
 167 #  endif
 168   }
 169
 170   if (size == 0)
 171     return NULL;                /* No allocation required.  */
 172
 173   /* Allocate combined header + user data storage.  */
 174
 175   {
 176     /* Address of header.  */
 177     register header *new;
 178
 179     size_t combined_size = sizeof (header) + size;
 180     if (combined_size < sizeof (header))
 181       memory_full ();
 182
 183     new = malloc (combined_size);
 184
 185     if (! new)
 186       memory_full ();
 187
 188     new->h.next = last_alloca_header;
 189     new->h.deep = depth;
 190
 191     last_alloca_header = new;
 192
 193     /* User storage begins just after header.  */
 194
 195     return (void *) (new + 1);
 196   }
 197 }
 198
 199 # endif /* no alloca */
 200 #endif /* not GCC || clang */