lib/alloca.c

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