~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to win32/alloca.c

  • Committer: Monty Taylor
  • Date: 2010-08-12 20:27:32 UTC
  • mto: (1720.1.5 build)
  • mto: This revision was merged to the branch mainline in revision 1722.
  • Revision ID: mordred@inaugust.com-20100812202732-9kzchbkvkyki4n3u
Merged libdrizzle directly into tree.

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
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 2, this file's not needed.  */
 
43
#if !defined (__GNUC__) || __GNUC__ < 2
 
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
/* If your stack is a linked list of frames, you have to
 
66
   provide an "address metric" ADDRESS_FUNCTION macro.  */
 
67
 
 
68
#  if defined (CRAY) && defined (CRAY_STACKSEG_END)
 
69
long i00afunc ();
 
70
#   define ADDRESS_FUNCTION(arg) (char *) i00afunc (&(arg))
 
71
#  else
 
72
#   define ADDRESS_FUNCTION(arg) &(arg)
 
73
#  endif
 
74
 
 
75
/* Define STACK_DIRECTION if you know the direction of stack
 
76
   growth for your system; otherwise it will be automatically
 
77
   deduced at run-time.
 
78
 
 
79
   STACK_DIRECTION > 0 => grows toward higher addresses
 
80
   STACK_DIRECTION < 0 => grows toward lower addresses
 
81
   STACK_DIRECTION = 0 => direction of growth unknown  */
 
82
 
 
83
#  ifndef STACK_DIRECTION
 
84
#   define STACK_DIRECTION      0       /* Direction unknown.  */
 
85
#  endif
 
86
 
 
87
#  if STACK_DIRECTION != 0
 
88
 
 
89
#   define STACK_DIR    STACK_DIRECTION /* Known at compile-time.  */
 
90
 
 
91
#  else /* STACK_DIRECTION == 0; need run-time code.  */
 
92
 
 
93
static int stack_dir;           /* 1 or -1 once known.  */
 
94
#   define STACK_DIR    stack_dir
 
95
 
 
96
static void
 
97
find_stack_direction (void)
 
98
{
 
99
  static char *addr = NULL;     /* Address of first `dummy', once known.  */
 
100
  auto char dummy;              /* To get stack address.  */
 
101
 
 
102
  if (addr == NULL)
 
103
    {                           /* Initial entry.  */
 
104
      addr = ADDRESS_FUNCTION (dummy);
 
105
 
 
106
      find_stack_direction ();  /* Recurse once.  */
 
107
    }
 
108
  else
 
109
    {
 
110
      /* Second entry.  */
 
111
      if (ADDRESS_FUNCTION (dummy) > addr)
 
112
        stack_dir = 1;          /* Stack grew upward.  */
 
113
      else
 
114
        stack_dir = -1;         /* Stack grew downward.  */
 
115
    }
 
116
}
 
117
 
 
118
#  endif /* STACK_DIRECTION == 0 */
 
119
 
 
120
/* An "alloca header" is used to:
 
121
   (a) chain together all alloca'ed blocks;
 
122
   (b) keep track of stack depth.
 
123
 
 
124
   It is very important that sizeof(header) agree with malloc
 
125
   alignment chunk size.  The following default should work okay.  */
 
126
 
 
127
#  ifndef       ALIGN_SIZE
 
128
#   define ALIGN_SIZE   sizeof(double)
 
129
#  endif
 
130
 
 
131
typedef union hdr
 
132
{
 
133
  char align[ALIGN_SIZE];       /* To force sizeof(header).  */
 
134
  struct
 
135
    {
 
136
      union hdr *next;          /* For chaining headers.  */
 
137
      char *deep;               /* For stack depth measure.  */
 
138
    } h;
 
139
} header;
 
140
 
 
141
static header *last_alloca_header = NULL;       /* -> last alloca header.  */
 
142
 
 
143
/* Return a pointer to at least SIZE bytes of storage,
 
144
   which will be automatically reclaimed upon exit from
 
145
   the procedure that called alloca.  Originally, this space
 
146
   was supposed to be taken from the current stack frame of the
 
147
   caller, but that method cannot be made to work for some
 
148
   implementations of C, for example under Gould's UTX/32.  */
 
149
 
 
150
void *
 
151
alloca (size_t size)
 
152
{
 
153
  auto char probe;              /* Probes stack depth: */
 
154
  register char *depth = ADDRESS_FUNCTION (probe);
 
155
 
 
156
#  if STACK_DIRECTION == 0
 
157
  if (STACK_DIR == 0)           /* Unknown growth direction.  */
 
158
    find_stack_direction ();
 
159
#  endif
 
160
 
 
161
  /* Reclaim garbage, defined as all alloca'd storage that
 
162
     was allocated from deeper in the stack than currently.  */
 
163
 
 
164
  {
 
165
    register header *hp;        /* Traverses linked list.  */
 
166
 
 
167
#  ifdef emacs
 
168
    BLOCK_INPUT;
 
169
#  endif
 
170
 
 
171
    for (hp = last_alloca_header; hp != NULL;)
 
172
      if ((STACK_DIR > 0 && hp->h.deep > depth)
 
173
          || (STACK_DIR < 0 && hp->h.deep < depth))
 
174
        {
 
175
          register header *np = hp->h.next;
 
176
 
 
177
          free (hp);            /* Collect garbage.  */
 
178
 
 
179
          hp = np;              /* -> next header.  */
 
180
        }
 
181
      else
 
182
        break;                  /* Rest are not deeper.  */
 
183
 
 
184
    last_alloca_header = hp;    /* -> last valid storage.  */
 
185
 
 
186
#  ifdef emacs
 
187
    UNBLOCK_INPUT;
 
188
#  endif
 
189
  }
 
190
 
 
191
  if (size == 0)
 
192
    return NULL;                /* No allocation required.  */
 
193
 
 
194
  /* Allocate combined header + user data storage.  */
 
195
 
 
196
  {
 
197
    /* Address of header.  */
 
198
    register header *new;
 
199
 
 
200
    size_t combined_size = sizeof (header) + size;
 
201
    if (combined_size < sizeof (header))
 
202
      memory_full ();
 
203
 
 
204
    new = malloc (combined_size);
 
205
 
 
206
    if (! new)
 
207
      memory_full ();
 
208
 
 
209
    new->h.next = last_alloca_header;
 
210
    new->h.deep = depth;
 
211
 
 
212
    last_alloca_header = new;
 
213
 
 
214
    /* User storage begins just after header.  */
 
215
 
 
216
    return (void *) (new + 1);
 
217
  }
 
218
}
 
219
 
 
220
#  if defined (CRAY) && defined (CRAY_STACKSEG_END)
 
221
 
 
222
#   ifdef DEBUG_I00AFUNC
 
223
#    include <stdio.h>
 
224
#   endif
 
225
 
 
226
#   ifndef CRAY_STACK
 
227
#    define CRAY_STACK
 
228
#    ifndef CRAY2
 
229
/* Stack structures for CRAY-1, CRAY X-MP, and CRAY Y-MP */
 
230
struct stack_control_header
 
231
  {
 
232
    long shgrow:32;             /* Number of times stack has grown.  */
 
233
    long shaseg:32;             /* Size of increments to stack.  */
 
234
    long shhwm:32;              /* High water mark of stack.  */
 
235
    long shsize:32;             /* Current size of stack (all segments).  */
 
236
  };
 
237
 
 
238
/* The stack segment linkage control information occurs at
 
239
   the high-address end of a stack segment.  (The stack
 
240
   grows from low addresses to high addresses.)  The initial
 
241
   part of the stack segment linkage control information is
 
242
   0200 (octal) words.  This provides for register storage
 
243
   for the routine which overflows the stack.  */
 
244
 
 
245
struct stack_segment_linkage
 
246
  {
 
247
    long ss[0200];              /* 0200 overflow words.  */
 
248
    long sssize:32;             /* Number of words in this segment.  */
 
249
    long ssbase:32;             /* Offset to stack base.  */
 
250
    long:32;
 
251
    long sspseg:32;             /* Offset to linkage control of previous
 
252
                                   segment of stack.  */
 
253
    long:32;
 
254
    long sstcpt:32;             /* Pointer to task common address block.  */
 
255
    long sscsnm;                /* Private control structure number for
 
256
                                   microtasking.  */
 
257
    long ssusr1;                /* Reserved for user.  */
 
258
    long ssusr2;                /* Reserved for user.  */
 
259
    long sstpid;                /* Process ID for pid based multi-tasking.  */
 
260
    long ssgvup;                /* Pointer to multitasking thread giveup.  */
 
261
    long sscray[7];             /* Reserved for Cray Research.  */
 
262
    long ssa0;
 
263
    long ssa1;
 
264
    long ssa2;
 
265
    long ssa3;
 
266
    long ssa4;
 
267
    long ssa5;
 
268
    long ssa6;
 
269
    long ssa7;
 
270
    long sss0;
 
271
    long sss1;
 
272
    long sss2;
 
273
    long sss3;
 
274
    long sss4;
 
275
    long sss5;
 
276
    long sss6;
 
277
    long sss7;
 
278
  };
 
279
 
 
280
#    else /* CRAY2 */
 
281
/* The following structure defines the vector of words
 
282
   returned by the STKSTAT library routine.  */
 
283
struct stk_stat
 
284
  {
 
285
    long now;                   /* Current total stack size.  */
 
286
    long maxc;                  /* Amount of contiguous space which would
 
287
                                   be required to satisfy the maximum
 
288
                                   stack demand to date.  */
 
289
    long high_water;            /* Stack high-water mark.  */
 
290
    long overflows;             /* Number of stack overflow ($STKOFEN) calls.  */
 
291
    long hits;                  /* Number of internal buffer hits.  */
 
292
    long extends;               /* Number of block extensions.  */
 
293
    long stko_mallocs;          /* Block allocations by $STKOFEN.  */
 
294
    long underflows;            /* Number of stack underflow calls ($STKRETN).  */
 
295
    long stko_free;             /* Number of deallocations by $STKRETN.  */
 
296
    long stkm_free;             /* Number of deallocations by $STKMRET.  */
 
297
    long segments;              /* Current number of stack segments.  */
 
298
    long maxs;                  /* Maximum number of stack segments so far.  */
 
299
    long pad_size;              /* Stack pad size.  */
 
300
    long current_address;       /* Current stack segment address.  */
 
301
    long current_size;          /* Current stack segment size.  This
 
302
                                   number is actually corrupted by STKSTAT to
 
303
                                   include the fifteen word trailer area.  */
 
304
    long initial_address;       /* Address of initial segment.  */
 
305
    long initial_size;          /* Size of initial segment.  */
 
306
  };
 
307
 
 
308
/* The following structure describes the data structure which trails
 
309
   any stack segment.  I think that the description in 'asdef' is
 
310
   out of date.  I only describe the parts that I am sure about.  */
 
311
 
 
312
struct stk_trailer
 
313
  {
 
314
    long this_address;          /* Address of this block.  */
 
315
    long this_size;             /* Size of this block (does not include
 
316
                                   this trailer).  */
 
317
    long unknown2;
 
318
    long unknown3;
 
319
    long link;                  /* Address of trailer block of previous
 
320
                                   segment.  */
 
321
    long unknown5;
 
322
    long unknown6;
 
323
    long unknown7;
 
324
    long unknown8;
 
325
    long unknown9;
 
326
    long unknown10;
 
327
    long unknown11;
 
328
    long unknown12;
 
329
    long unknown13;
 
330
    long unknown14;
 
331
  };
 
332
 
 
333
#    endif /* CRAY2 */
 
334
#   endif /* not CRAY_STACK */
 
335
 
 
336
#   ifdef CRAY2
 
337
/* Determine a "stack measure" for an arbitrary ADDRESS.
 
338
   I doubt that "lint" will like this much.  */
 
339
 
 
340
static long
 
341
i00afunc (long *address)
 
342
{
 
343
  struct stk_stat status;
 
344
  struct stk_trailer *trailer;
 
345
  long *block, size;
 
346
  long result = 0;
 
347
 
 
348
  /* We want to iterate through all of the segments.  The first
 
349
     step is to get the stack status structure.  We could do this
 
350
     more quickly and more directly, perhaps, by referencing the
 
351
     $LM00 common block, but I know that this works.  */
 
352
 
 
353
  STKSTAT (&status);
 
354
 
 
355
  /* Set up the iteration.  */
 
356
 
 
357
  trailer = (struct stk_trailer *) (status.current_address
 
358
                                    + status.current_size
 
359
                                    - 15);
 
360
 
 
361
  /* There must be at least one stack segment.  Therefore it is
 
362
     a fatal error if "trailer" is null.  */
 
363
 
 
364
  if (trailer == 0)
 
365
    abort ();
 
366
 
 
367
  /* Discard segments that do not contain our argument address.  */
 
368
 
 
369
  while (trailer != 0)
 
370
    {
 
371
      block = (long *) trailer->this_address;
 
372
      size = trailer->this_size;
 
373
      if (block == 0 || size == 0)
 
374
        abort ();
 
375
      trailer = (struct stk_trailer *) trailer->link;
 
376
      if ((block <= address) && (address < (block + size)))
 
377
        break;
 
378
    }
 
379
 
 
380
  /* Set the result to the offset in this segment and add the sizes
 
381
     of all predecessor segments.  */
 
382
 
 
383
  result = address - block;
 
384
 
 
385
  if (trailer == 0)
 
386
    {
 
387
      return result;
 
388
    }
 
389
 
 
390
  do
 
391
    {
 
392
      if (trailer->this_size <= 0)
 
393
        abort ();
 
394
      result += trailer->this_size;
 
395
      trailer = (struct stk_trailer *) trailer->link;
 
396
    }
 
397
  while (trailer != 0);
 
398
 
 
399
  /* We are done.  Note that if you present a bogus address (one
 
400
     not in any segment), you will get a different number back, formed
 
401
     from subtracting the address of the first block.  This is probably
 
402
     not what you want.  */
 
403
 
 
404
  return (result);
 
405
}
 
406
 
 
407
#   else /* not CRAY2 */
 
408
/* Stack address function for a CRAY-1, CRAY X-MP, or CRAY Y-MP.
 
409
   Determine the number of the cell within the stack,
 
410
   given the address of the cell.  The purpose of this
 
411
   routine is to linearize, in some sense, stack addresses
 
412
   for alloca.  */
 
413
 
 
414
static long
 
415
i00afunc (long address)
 
416
{
 
417
  long stkl = 0;
 
418
 
 
419
  long size, pseg, this_segment, stack;
 
420
  long result = 0;
 
421
 
 
422
  struct stack_segment_linkage *ssptr;
 
423
 
 
424
  /* Register B67 contains the address of the end of the
 
425
     current stack segment.  If you (as a subprogram) store
 
426
     your registers on the stack and find that you are past
 
427
     the contents of B67, you have overflowed the segment.
 
428
 
 
429
     B67 also points to the stack segment linkage control
 
430
     area, which is what we are really interested in.  */
 
431
 
 
432
  stkl = CRAY_STACKSEG_END ();
 
433
  ssptr = (struct stack_segment_linkage *) stkl;
 
434
 
 
435
  /* If one subtracts 'size' from the end of the segment,
 
436
     one has the address of the first word of the segment.
 
437
 
 
438
     If this is not the first segment, 'pseg' will be
 
439
     nonzero.  */
 
440
 
 
441
  pseg = ssptr->sspseg;
 
442
  size = ssptr->sssize;
 
443
 
 
444
  this_segment = stkl - size;
 
445
 
 
446
  /* It is possible that calling this routine itself caused
 
447
     a stack overflow.  Discard stack segments which do not
 
448
     contain the target address.  */
 
449
 
 
450
  while (!(this_segment <= address && address <= stkl))
 
451
    {
 
452
#    ifdef DEBUG_I00AFUNC
 
453
      fprintf (stderr, "%011o %011o %011o\n", this_segment, address, stkl);
 
454
#    endif
 
455
      if (pseg == 0)
 
456
        break;
 
457
      stkl = stkl - pseg;
 
458
      ssptr = (struct stack_segment_linkage *) stkl;
 
459
      size = ssptr->sssize;
 
460
      pseg = ssptr->sspseg;
 
461
      this_segment = stkl - size;
 
462
    }
 
463
 
 
464
  result = address - this_segment;
 
465
 
 
466
  /* If you subtract pseg from the current end of the stack,
 
467
     you get the address of the previous stack segment's end.
 
468
     This seems a little convoluted to me, but I'll bet you save
 
469
     a cycle somewhere.  */
 
470
 
 
471
  while (pseg != 0)
 
472
    {
 
473
#    ifdef DEBUG_I00AFUNC
 
474
      fprintf (stderr, "%011o %011o\n", pseg, size);
 
475
#    endif
 
476
      stkl = stkl - pseg;
 
477
      ssptr = (struct stack_segment_linkage *) stkl;
 
478
      size = ssptr->sssize;
 
479
      pseg = ssptr->sspseg;
 
480
      result += size;
 
481
    }
 
482
  return (result);
 
483
}
 
484
 
 
485
#   endif /* not CRAY2 */
 
486
#  endif /* CRAY */
 
487
 
 
488
# endif /* no alloca */
 
489
#endif /* not GCC version 2 */