Architectures with a non-contiguous stack?
Adam Warner
If I write an otherwise conforming ISO C program that makes a single
non-portable assumption--that the stack is contiguous (in order to cheaply
distinguish addresses into the stack from addresses of explicitly malloc'd
or mmap'd memory)--are there any architectures in common use where my
program may break?
So far I've only found the Acorn Archimedes has a non-contiguous stack,
which for my purposes is merely of historical interest.
Many thanks,
Adam
Dave Vandervies
Adam Warner <use...@consulting.net.nz> wrote:
>Hi all,
>
>If I write an otherwise conforming ISO C program that makes a single
>non-portable assumption--that the stack is contiguous (in order to cheaply
>distinguish addresses into the stack from addresses of explicitly malloc'd
>or mmap'd memory)--are there any architectures in common use where my
>program may break?
Implementations on some IBM mainframes use heap-allocated stack frames,
which implies no guarantees that the stack is contiguous.
I don't know whether any that do that are still in common use. I expect
that at the very least you Would Know if your code was going to run
on one.
The traditional question to ask at this point is: What are you Really
Trying To Do? Why do you want to distinguish stack from non-stack memory?
dave
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
Its not, but anyway -273.15 is not exactly representable by an IEEE float so
its inexact as well as being inexact (!!).
--Mark McIntyre in comp.lang.c
Adam Warner
>>If I write an otherwise conforming ISO C program that makes a single
>>non-portable assumption--that the stack is contiguous (in order to
>>cheaply distinguish addresses into the stack from addresses of
>>explicitly malloc'd or mmap'd memory)--are there any architectures in
>>common use where my program may break?
>
> Implementations on some IBM mainframes use heap-allocated stack frames,
> which implies no guarantees that the stack is contiguous. I don't know
> whether any that do that are still in common use. I expect that at the
> very least you Would Know if your code was going to run on one.
Though I should expect recent IBM mainframes that virtualise GNU/Linux
operating systems to provide contiguous stacks?
With address space becoming far less scarce as 64-bit workstations and
operating systems become mainstream there should no future pressure to
fragment stacks.
> The traditional question to ask at this point is: What are you Really
> Trying To Do? Why do you want to distinguish stack from non-stack
> memory?
I'm just considering garbage collection ideas that avoid the optimism of
conservative garbage collectors. Conservative garbage collection is
generally a misnomer. It typically assumes the hostile compilation
environment doesn't disguise any pointers at high optimisation levels.
Any behaviour I can essentially rely upon beyond the constraints of ISO C
is an opportunity to implement garbage collection with a lower run time
overhead.
Thanks Dave,
Adam
CBFalconer
> Adam Warner <use...@consulting.net.nz> wrote:
>>
>> If I write an otherwise conforming ISO C program that makes a
>> single non-portable assumption--that the stack is contiguous
>> (in order to cheaply distinguish addresses into the stack from
>> addresses of explicitly malloc'd or mmap'd memory)--are there
>> any architectures in common use where my program may break?
>
>
> The traditional question to ask at this point is: What are you
> Really Trying To Do? Why do you want to distinguish stack from
> non-stack memory?
I would guess that he is trying to avoid freeing or reallocing some
types that he usually mallocs, but also creates in automatic
storage. If so, he would be better off revising his program flow.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
webs...@gmail.com
> non-portable assumption--that the stack is contiguous (in order to
> cheaply distinguish addresses into the stack from addresses of
> explicitly malloc'd or mmap'd memory)--are there any architectures
> in common use where my program may break?
Yes, any architecture that supports shared memory multithreading --
they need to "allocate their stacks" from seperate memory structures
(usually the heap, or system memory.) Also, when using "stack address
tricks", you have to be careful of whether or not they still work with
"setjmp" and "longjmp".
But your general idea speaks to an inherent weakness of the C-language.
There should be standardized library functions that can test memory
pointers:
int isInHeap (void * p, size_t len);
int isAuto (void * p, size_t len);
int isGlobal (void * p, size_t len);
Which would test if a pointer starting at the position p and spanning
for a length len has been allocated on the heap, is in the storage area
used for auto variables, or in the static/global file scope. The idea
is that you would return 1 if its definately all in that memory scope,
0 if at least some of it definately is not, and maybe say -1, if it not
possible to really tell for sure, but certainly plausible. They all
must return 0 if p is NULL.
This would allow lame vendors to just punt and always return -1. While
minimal vendors would at least keep min, and max addresses lying around
to do simplistic range checks (which is good enough for debugging, 99%
of the time), and aggressive vendors could do more sophisticating
things like walking the heap, and checking each stack (corresponding to
each thread.) Actually isGlobal() is likely to be the hardest, since
it requires link-time knowledge -- but presumably there might be a way
to fetch that information from the loader (getting the Init segment and
Data segments.)
Besides being used for debugging, its also possible to be used for
actual functional purposes -- lets say a cleanup/destructor routine
wants to clean up an object that might be allocated from either the
stack or the heap, but its not clear which -- it could use such calls
to perform that distinction.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
Adam Warner
>> If I write an otherwise conforming ISO C program that makes a single
>> non-portable assumption--that the stack is contiguous (in order to
>> cheaply distinguish addresses into the stack from addresses of
>> explicitly malloc'd or mmap'd memory)--are there any architectures in
>> common use where my program may break?
>
> Yes, any architecture that supports shared memory multithreading -- they
> need to "allocate their stacks" from separate memory structures (usually
> the heap, or system memory.)
This shouldn't be a problem so long as each thread's stack is contiguous.
I understand for example that 2MB of contiguous space is allocated by
default for each Linux thread.
Many thanks for the additional commentary.
Regards,
Adam
MSCHAEF.COM
There are a number of programming environments, particulaly those that
support first-order continuations or lexical closures, that heap allocate
what would normally be on a stack. There's no guarantee that the "stack"
is even linear, it could well be a tree.
It's also worth pointing out that in multi-threaded environments, there
are multiple stacks, and no guarantees about where they are relative to
each other. IsOnStack(void *) could therefore be more complex than a
simple range check.
-Mike
--
http://www.mschaef.com
Dave Vandervies
>> Implementations on some IBM mainframes use heap-allocated stack frames,
>> which implies no guarantees that the stack is contiguous. I don't know
>> whether any that do that are still in common use. I expect that at the
>> very least you Would Know if your code was going to run on one.
>
>Though I should expect recent IBM mainframes that virtualise GNU/Linux
>operating systems to provide contiguous stacks?
Whether or not they're running Linux in a VM, I'd expect any reasonably
recent IBM mainframe to have instruction set support for a stack, and
the C implementation to use it.
>With address space becoming far less scarce as 64-bit workstations and
>operating systems become mainstream there should no future pressure to
>fragment stacks.
If I'm not mistaken, it wasn't actually an address space issue; the
instruction set didn't support it, and it was easier to allocate stack
frames on the heap than to set aside a chunk of memory for the stack and
do The Right Thing with it without the CPU's support. But I doubt any new
instruction set is going to make it difficult to use a contiguous chunk
of memory for the function-invocation stack in conventional programming
languages anytime soon.
>> The traditional question to ask at this point is: What are you Really
>> Trying To Do? Why do you want to distinguish stack from non-stack
>> memory?
>
>I'm just considering garbage collection ideas that avoid the optimism of
>conservative garbage collectors. Conservative garbage collection is
>generally a misnomer. It typically assumes the hostile compilation
>environment doesn't disguise any pointers at high optimisation levels.
>
>Any behaviour I can essentially rely upon beyond the constraints of ISO C
>is an opportunity to implement garbage collection with a lower run time
>overhead.
If you're implementing a garbage collector, you'll already need to make
assumptions beyond what ISO C gives you, so if assuming a contiguous
stack makes your life easier, go ahead and make (and document!) that
assumption It will help with the most common case, and you'll probably
have some rewriting to do for weirder implementations anyways.
As noted elsethread, if the program you're working with is multithreaded,
you'll have to be able to deal with multiple stacks, and possibly stacks
being created and destroyed. You can probably still assume that a
particular stack will be contiguous, which may or may not still be useful.
dave
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
I'll take the lighter weight in exchange for having to shoot a "really lethal"
weapon instead of a "really, really lethal" one.
--Chris Klein in the scary devil monastery
Dave Vandervies
MSCHAEF.COM <mscha...@mschaef.com> wrote:
>In article <pan.2005.01.31....@consulting.net.nz>,
>Adam Warner <use...@consulting.net.nz> wrote:
>>Hi all,
>>
>>If I write an otherwise conforming ISO C program that makes a single
>>non-portable assumption--that the stack is contiguous (in order to cheaply
>>distinguish addresses into the stack from addresses of explicitly malloc'd
>>or mmap'd memory)--are there any architectures in common use where my
>>program may break?
>There are a number of programming environments, particulaly those that
>support first-order continuations or lexical closures, that heap allocate
>what would normally be on a stack. There's no guarantee that the "stack"
>is even linear, it could well be a tree.
I somehow doubt that a program running in these environments would look
remotely similar to an otherwise-conforming ISO C program.
But this isn't entirely irrelevant to the OP's question - garbage
collection in these environments is an interesting problem, and it seems
to be understood well enough to be done effectively. (But OTGH, these
environments typically have other advantages over C from the GC point
of view, so I'm not sure how much of The Way Things Are Done there would
be useful in a C environment.)