🚀 go-pugleaf

mec@treflan.shout.net (Michael Elizabeth Chastain) writes:

>Fergus Henderson <fjh@munta.cs.mu.OZ.AU> wrote:
>> But as you suggest below, on platforms for which stack allocation is
>> difficult, the compiler could simply allocate such arrays on the heap.
[...]
>I accept the prior-art argument and the usefulness argument.
>
>But I don't accept this part: 'the compiler could simply allocate such
>arrays on the heap.'
>
>The compiler may have to use a hidden auto-pointer-like mechanism for
>removing such arrays from the heap in cases of function returns,
>longjmp, and exceptions.  I expect this would be reasonable for function
>returns and exceptions.  But it would be new functionality for
>'longjmp'.

OK, I agree that if you don't want memory leaks in the presence of longjmp(),
it is slightly more complicated.  But still not too hard.

One very simple way of doing it would be to allocate such arrays using
alloca(), and use Doug Gwyn's mostly portable public domain
implementation of alloca().  This is what GNU C does.  Here's an extract
from the comments in alloca.c in the gcc distribution:

|    The general concept of this implementation is to keep
|    track of all alloca-allocated blocks, and reclaim any
|    that are found to be deeper in the stack than the current
|    invocation.  This heuristic does not reclaim storage as
|    soon as it becomes invalid, but it will do so eventually.
| 
|    As a special case, alloca(0) reclaims storage without
|    allocating any.  It is a good idea to use alloca(0) in
|    your main control loop, etc. to force garbage collection.  */

So all you would need to do is allocate variable length arrays using
alloca(), and if you really need to recover memory ASAP, put a
call to alloca(0) in setjmp().

	#define setjmp(buf) (tmp = __setjmp(buf), alloca(0), tmp)

Another approach would be for the compiler to keep a linked list of all
the memory areas allocated for variable-length arrays.  When entering
the scope of a variable-length array, the compiler would allocate the
memory from the heap, and then insert a pointer to the memory at the
front of this linked list.  On exit, it would deallocate the memory and
remove the entry from the list.  Then in setjmp() it would save a
pointer to the front of the linked list, and in longjmp() it would
iterate down the list, deallocating the memory, until it reached the
link stored by setjmp().  This approach is actually pretty similar to how
Doug Gwyn's alloca() implementation works, except that it is (more) portable.

So for

	void foo(int n) {
		char s[n];	
		bar(s);
	}

the compiler could generate code equivalent to

	struct __link {
		void *ptr; __link *next;
		__link(void *p, __link *n) : ptr(p), next(n) {}
	} __list;

	void foo(int n) {
		char *s = new char[n];
		__list = new __link(s, __list);
		bar(s);
		__link *__old = __list;
		__list = __list->next;
		delete __old;
	}

setjmp(buf) would include `buf.link = __list;',
and longjmp(buf) would include

	while (__list != buf.link) {
		__link *__old = __list;
		__list = __list->next;
		delete __old;
	}

>I say 'may have to' because every processor I know can implement
>variable-sized stack frames by subtracting an appropriate value from
>the stack pointer at the appropriate time.  But what about processors I
>don't know about?  Are there truly any processors in use which don't
>support subtracting a computed value from the stack pointer?

The comments in Doug Gwyn's alloca() name "Gould's UTX/32" C
implementation, whatever that is, as being one for which this is not
possible.

But I think comercially significant machines for which this is not possible
are pretty thin on the ground these days, and in any case as demonstrated
above it is not difficult to implement variable length arrays even for such
machines without longjmp() causing any memory leaks.

--
Fergus Henderson             	WWW: http://www.cs.mu.oz.au/~fjh
fjh@cs.mu.oz.au              	PGP: finger fjh@128.250.37.3
I will have little or no net access from Nov 30 until Dec 25.
---
[ comp.std.c++ is moderated.  Submission address: std-c++@ncar.ucar.edu.
  Contact address: std-c++-request@ncar.ucar.edu.  The moderation policy
  is summarized in http://dogbert.lbl.gov/~matt/std-c++/policy.html. ]