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 #ifdef emacs 34 # include "lisp.h" 35 # include "blockinput.h" 36 # ifdef EMACS_FREE 37 # undef free 38 # define free EMACS_FREE 39 # endif 40 #else 41 # define memory_full() abort () 42 #endif 43 44 /* If compiling with GCC or clang, this file is not needed. */ 45 #if !(defined __GNUC__ || defined __clang__) 46 47 /* If someone has defined alloca as a macro, 48 there must be some other way alloca is supposed to work. */ 49 # ifndef alloca 50 51 # ifdef emacs 52 # ifdef static 53 /* actually, only want this if static is defined as "" 54 -- this is for usg, in which emacs must undefine static 55 in order to make unexec workable 56 */ 57 # ifndef STACK_DIRECTION 58 you 59 lose 60 -- must know STACK_DIRECTION at compile-time 61 /* Using #error here is not wise since this file should work for 62 old and obscure compilers. */ 63 # endif /* STACK_DIRECTION undefined */ 64 # endif /* static */ 65 # endif /* emacs */ 66 67 /* Define STACK_DIRECTION if you know the direction of stack 68 growth for your system; otherwise it will be automatically 69 deduced at run-time. 70 71 STACK_DIRECTION > 0 => grows toward higher addresses 72 STACK_DIRECTION < 0 => grows toward lower addresses 73 STACK_DIRECTION = 0 => direction of growth unknown */ 74 75 # ifndef STACK_DIRECTION 76 # define STACK_DIRECTION 0 /* Direction unknown. */ 77 # endif 78 79 # if STACK_DIRECTION != 0 80 81 # define STACK_DIR STACK_DIRECTION /* Known at compile-time. */ 82 83 # else /* STACK_DIRECTION == 0; need run-time code. */ 84 85 static int stack_dir; /* 1 or -1 once known. */ 86 # define STACK_DIR stack_dir 87 88 static int 89 find_stack_direction (int *addr, int depth) /* */ 90 { 91 int dir, dummy = 0; 92 if (! addr) 93 addr = &dummy; 94 *addr = addr < &dummy ? 1 : addr == &dummy ? 0 : -1; 95 dir = depth ? find_stack_direction (addr, depth - 1) : 0; 96 return dir + dummy; 97 } 98 99 # endif /* STACK_DIRECTION == 0 */ 100 101 /* An "alloca header" is used to: 102 (a) chain together all alloca'ed blocks; 103 (b) keep track of stack depth. 104 105 It is very important that sizeof(header) agree with malloc 106 alignment chunk size. The following default should work okay. */ 107 108 # ifndef ALIGN_SIZE 109 # define ALIGN_SIZE sizeof(double) 110 # endif 111 112 typedef union hdr 113 { 114 char align[ALIGN_SIZE]; /* To force sizeof(header). */ 115 struct 116 { 117 union hdr *next; /* For chaining headers. */ 118 char *deep; /* For stack depth measure. */ 119 } h; 120 } header; 121 122 static header *last_alloca_header = NULL; /* -> last alloca header. */ 123 124 /* Return a pointer to at least SIZE bytes of storage, 125 which will be automatically reclaimed upon exit from 126 the procedure that called alloca. Originally, this space 127 was supposed to be taken from the current stack frame of the 128 caller, but that method cannot be made to work for some 129 implementations of C, for example under Gould's UTX/32. */ 130 131 void * 132 alloca (size_t size) /* */ 133 { 134 auto char probe; /* Probes stack depth: */ 135 register char *depth = &probe; 136 137 # if STACK_DIRECTION == 0 138 if (STACK_DIR == 0) /* Unknown growth direction. */ 139 STACK_DIR = find_stack_direction (NULL, (size & 1) + 20); 140 # endif 141 142 /* Reclaim garbage, defined as all alloca'd storage that 143 was allocated from deeper in the stack than currently. */ 144 145 { 146 register header *hp; /* Traverses linked list. */ 147 148 # ifdef emacs 149 BLOCK_INPUT; 150 # endif 151 152 for (hp = last_alloca_header; hp != NULL;) 153 if ((STACK_DIR > 0 && hp->h.deep > depth) 154 || (STACK_DIR < 0 && hp->h.deep < depth)) 155 { 156 register header *np = hp->h.next; 157 158 free (hp); /* Collect garbage. */ 159 160 hp = np; /* -> next header. */ 161 } 162 else 163 break; /* Rest are not deeper. */ 164 165 last_alloca_header = hp; /* -> last valid storage. */ 166 167 # ifdef emacs 168 UNBLOCK_INPUT; 169 # endif 170 } 171 172 if (size == 0) 173 return NULL; /* No allocation required. */ 174 175 /* Allocate combined header + user data storage. */ 176 177 { 178 /* Address of header. */ 179 register header *new; 180 181 size_t combined_size = sizeof (header) + size; 182 if (combined_size < sizeof (header)) 183 memory_full (); 184 185 new = malloc (combined_size); 186 187 if (! new) 188 memory_full (); 189 190 new->h.next = last_alloca_header; 191 new->h.deep = depth; 192 193 last_alloca_header = new; 194 195 /* User storage begins just after header. */ 196 197 return (void *) (new + 1); 198 } 199 } 200 201 # endif /* no alloca */ 202 #endif /* not GCC || clang */