18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project alloca -- (mostly) portable public-domain implementation -- D A Gwyn 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project last edit: 86/05/30 rms 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project include config.h, since on VMS it renames some symbols. 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Use xmalloc instead of malloc. 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project This implementation of the PWB library alloca() function, 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project which is used to allocate space off the run-time stack so 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project that it is automatically reclaimed upon procedure exit, 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project was inspired by discussions with J. Q. Johnson of Cornell. 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project It should work under any C implementation that uses an 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project actual procedure stack (as opposed to a linked list of 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project frames). There are some preprocessor constants that can 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project be defined when compiling for your specific system, for 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project improved efficiency; however, the defaults should be okay. 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project The general concept of this implementation is to keep 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project track of all alloca()-allocated blocks, and reclaim any 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project that are found to be deeper in the stack than the current 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project invocation. This heuristic does not reclaim storage as 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project soon as it becomes invalid, but it will do so eventually. 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project As a special case, alloca(0) reclaims storage without 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project allocating any. It is a good idea to use alloca(0) in 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project your main control loop, etc. to force garbage collection. 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project*/ 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef lint 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstatic char SCCSid[] = "@(#)alloca.c 1.1"; /* for the "what" utility */ 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef emacs 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "config.h" 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef static 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* actually, only want this if static is defined as "" 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project -- this is for usg, in which emacs must undefine static 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project in order to make unexec workable 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef STACK_DIRECTION 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectyou 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectlose 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project-- must know STACK_DIRECTION at compile-time 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* STACK_DIRECTION undefined */ 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* static */ 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* emacs */ 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef alloca /* If compiling with GCC, this file's not needed. */ 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef __STDC__ 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttypedef void *pointer; /* generic pointer type */ 528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttypedef char *pointer; /* generic pointer type */ 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define NULL 0 /* null pointer constant */ 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectextern void free(); 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectextern pointer xmalloc(); 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Define STACK_DIRECTION if you know the direction of stack 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project growth for your system; otherwise it will be automatically 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deduced at run-time. 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project STACK_DIRECTION > 0 => grows toward higher addresses 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project STACK_DIRECTION < 0 => grows toward lower addresses 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project STACK_DIRECTION = 0 => direction of growth unknown 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project*/ 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef STACK_DIRECTION 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define STACK_DIRECTION 0 /* direction unknown */ 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if STACK_DIRECTION != 0 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define STACK_DIR STACK_DIRECTION /* known at compile-time */ 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else /* STACK_DIRECTION == 0; need run-time code */ 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstatic int stack_dir; /* 1 or -1 once known */ 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define STACK_DIR stack_dir 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstatic void 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectfind_stack_direction (/* void */) 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static char *addr = NULL; /* address of first 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project `dummy', once known */ 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project auto char dummy; /* to get stack address */ 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (addr == NULL) 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { /* initial entry */ 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project addr = &dummy; 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project find_stack_direction (); /* recurse once */ 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else /* second entry */ 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (&dummy > addr) 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project stack_dir = 1; /* stack grew upward */ 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project stack_dir = -1; /* stack grew downward */ 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* STACK_DIRECTION == 0 */ 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project An "alloca header" is used to: 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project (a) chain together all alloca()ed blocks; 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project (b) keep track of stack depth. 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project It is very important that sizeof(header) agree with malloc() 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project alignment chunk size. The following default should work okay. 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project*/ 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef ALIGN_SIZE 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define ALIGN_SIZE sizeof(double) 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttypedef union hdr 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project char align[ALIGN_SIZE]; /* to force sizeof(header) */ 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project union hdr *next; /* for chaining headers */ 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project char *deep; /* for stack depth measure */ 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } h; 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} header; 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project alloca( size ) returns a pointer to at least `size' bytes of 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project storage which will be automatically reclaimed upon exit from 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project the procedure that called alloca(). Originally, this space 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project was supposed to be taken from the current stack frame of the 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project caller, but that method cannot be made to work for some 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project implementations of C, for example under Gould's UTX/32. 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project*/ 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectstatic header *last_alloca_header = NULL; /* -> last alloca header */ 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectpointer 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectalloca (size) /* returns pointer to storage */ 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned size; /* # bytes to allocate */ 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project auto char probe; /* probes stack depth: */ 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project register char *depth = &probe; 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if STACK_DIRECTION == 0 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (STACK_DIR == 0) /* unknown growth direction */ 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project find_stack_direction (); 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Reclaim garbage, defined as all alloca()ed storage that 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project was allocated from deeper in the stack than currently. */ 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project register header *hp; /* traverses linked list */ 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (hp = last_alloca_header; hp != NULL;) 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if ((STACK_DIR > 0 && hp->h.deep > depth) 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project || (STACK_DIR < 0 && hp->h.deep < depth)) 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project register header *np = hp->h.next; 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project free ((pointer) hp); /* collect garbage */ 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hp = np; /* -> next header */ 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; /* rest are not deeper */ 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project last_alloca_header = hp; /* -> last valid storage */ 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (size == 0) 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return NULL; /* no allocation required */ 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Allocate combined header + user data storage. */ 1788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project register pointer new = xmalloc (sizeof (header) + size); 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* address of header */ 1838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ((header *)new)->h.next = last_alloca_header; 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ((header *)new)->h.deep = depth; 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project last_alloca_header = (header *)new; 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* User storage begins just after header. */ 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return (pointer)((char *)new + sizeof(header)); 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif /* no alloca */ 196