← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to win32/alloca.c

  • Committer: Stewart Smith
  • Date: 2010-04-08 07:20:26 UTC
  • mto: This revision was merged to the branch mainline in revision 1456.
  • Revision ID: stewart@flamingspork.com-20100408072026-w3s8zblhs35uo5mg
https://launchpad.net/bugs/557880
remove CHECKSUM TABLE

Show diffs side-by-side

added added

removed removed

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