«

On May 31, 3:05*am, Keith Thompson <ks...@mib.org> wrote:
> Chad <cdal...@gmail.com> writes:
> > On May 30, 12:06*am, "io_x" <a...@b.c.invalid> wrote:
> >> a stack is a common array of memory where is defined the functions push()
> >> and pop() [and descrive what the functions do]
>
> > And what happens if someone changes the array to say a singly linked
> > list?
>
> I didn't respond to the original question because it was an obvious
> troll, but I think you're actually trying to learn something, so ...
>
> The term "stack" has two distinct but related meanings. *(Actually it
> has more than that, but only two are relevant here.)
>
> In computer science terms, a stack is a data structure with last-in
> first-out behavior. *In other words, the available operations are
> "push', which adds a new element to the stack, and "pop", which
> removes the most recently added element (and either gives you its
> value or discards it). *The first element added to an empty stack
> is at the "bottom" of the stack; the most recently added element
> is at the "top".
>
> There are a number of ways to implement a stack. *One is as a
> contiguous chunk of memory, an array, with an index variable that
> indicates where the current "top" of the stack is (the bottom is
> fixed and doesn't need an index variable). *If the array is of a
> fixed size, then the stack can only hold at most a fixed number of
> elements; pushing an additional element causes an overflow error,
> which must be handled somehow; conversely, if you use only a small
> portion of the array, the rest is wasted. *Another way to implement
> a stack is as a linked list, which avoids the overflow and waste
> problems (until you run out of memory), but is a bit more complex
> and probably slower.

This is "probably" wrong. Incrementing or decrementing an index
variable takes place in constant time. If the stack is implemented as
a doubly-linked list, the same is true.

Many programmers use an idiot axiom: "if it's hard to think about, the
code must be inefficient".

>
> The other common meaning of "stack", usually referred to as "the
> stack", is in computer systems architecture. *It's a contiguous
> region of memory where the index variable indicating the current
> "top" of the stack is typically a CPU register, the stack pointer
> (often called the "SP" register). *Many systems use such a stack to
> implement function calls: all the information needed for a function
> call, including local data, possibly parameters, and housekeeping
> data such as the return address, is pushed onto "the stack" when a
> function is called, and popped when the function returns. *The stack
> may grow either up or down in memory, depending on the system.

This is the same thing as your first definition, Kiki. My dear chap,
verbosity is not so much a large word count: it is a low ratio of
ideas to words. Word to the wise.
>
> Most current systems use this kind of stack, but not all do, and the
> C standard doesn't refer to it at all. *There are systems that use a
> linked list of activation records, rather than a contiguous stack,
> to manage function calls. *There have been systems that don't use

That "linked list of activation records"? It's a stack, Kiki.

> any kind of stack for function calls; such systems cannot directly
> support recursion, and therefore cannot support a C implementation.

Which means that the Standard should have mentioned "stacks". Why did
it not do so? My theory is the traditional hatred of American
programmers and managers for the stack.

> Even on systems that do use a contiguous hardware stack, the details
> vary from one system to another. *Unless you're dealing with very
> low-level details, you don't need to know about how the hardware
> stack works to understand how a C program works.
>
> I'm going into all this gory detail because some people in this
> newsgroup have (perhaps deliberately) confused the two concepts,
> and others have refused to acknowledge that a C implementation can
> possibly use anything other than contiguous hardware stack.

I don't know who you're talking about. We know that the stack can be
implemented in many ways. My more abstract and better factored
definition allows this.

> Don't let them confuse you..

There is a guy named Kiki
Who said, don't let them...let me
Confuse you
And abuse you
That ****in' guy, named Kiki.

>
> --
> Keith Thompson (The_Other_Keith) ks...@mib.org *<http://www.ghoti.net/~kst>
> Nokia
> "We must do something. *This is something. *Therefore, we must do this."
> * * -- Antony Jay and Jonathan Lynn, "Yes Minister"

On 2010-05-30, Keith Thompson <kst-> wrote:
> Even on systems that do use a contiguous hardware stack, the details
> vary from one system to another. Unless you're dealing with very
> low-level details, you don't need to know about how the hardware
> stack works to understand how a C program works.

While this is theoretically true, I think it is still useful for C
programmers to have some idea about how the stack is implemented on their
system/compiler; especially for stacks that are effectively continuous
arrays whether hardware implemented or not.

1. It can simplifly debugging.
A. Being able to look at the process stack can give you an idea of
the history of the current context.
B. Understanding how your stack is structured can help you diagnose
local buffer overflow problems that might otherwise be more
difficult to locate. Some compilers can help with this.
They have the ability to check stack frame boundries
using magic numbers that can be checked for clobbering
at some point during runtime.

2. It can improve security. Many buffer overflow vulnerabilities are
based on trying to overwrite the pointer used to return to
the previous function. Understanding this attack can help a
programmer take extra security precautions in their code.

3. Knowing that local variables are saved in a limited stack area can be
important as saving large data structures or arrays on the stack can
cause it to overflow. As can excessive recursion.

On 2010-05-31, Tim Harig <> wrote:
> While this is theoretically true, I think it is still useful for C
> programmers to have some idea about how the stack is implemented on their
> system/compiler; especially for stacks that are effectively continuous
> arrays whether hardware implemented or not.

It can be. However, it's important to get it right -- if you know how the
stack was implemented on something else, it can be extremely bad, because
it can lead to you *mistakenly* thinking it has provided any of these
benefits... And it's surprising just how often these things can change.
There are cases where a compiler option can result in different behavior
for the same compiler, same operating system, and same hardware...

> 2. It can improve security. Many buffer overflow vulnerabilities are
> based on trying to overwrite the pointer used to return to
> the previous function. Understanding this attack can help a
> programmer take extra security precautions in their code.

I don't buy this one. You don't have to know anything about a stack to
understand the basics of why buffer overruns are a big deal.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

On 2010-05-31, Seebs <usenet-> wrote:
> On 2010-05-31, Tim Harig <> wrote:
>> While this is theoretically true, I think it is still useful for C
>> programmers to have some idea about how the stack is implemented on their
>> system/compiler; especially for stacks that are effectively continuous
>> arrays whether hardware implemented or not.
> It can be. However, it's important to get it right -- if you know how the
> stack was implemented on something else, it can be extremely bad, because
> it can lead to you *mistakenly* thinking it has provided any of these
> benefits... And it's surprising just how often these things can change.
> There are cases where a compiler option can result in different behavior
> for the same compiler, same operating system, and same hardware...

I thought that being correct went without saying. Using mistaken
information always puts you at risk of doing the wrong thing. (I could make
a political statement here; but, I will refrain.)

>> 2. It can improve security. Many buffer overflow vulnerabilities are
>> based on trying to overwrite the pointer used to return to
>> the previous function. Understanding this attack can help a
>> programmer take extra security precautions in their code.
>
> I don't buy this one. You don't have to know anything about a stack to
> understand the basics of why buffer overruns are a big deal.

Yes, buffer overflows are a bad thing. Unfortunately, they also still seem
to happen again and again. Bug reports and vulnerability databases are
full of buffer overflows. So, while I agree that buffer overflows should
be minimized, it makes sense to have a backup plan to minimize the damage
that they may have caused. High security systems such as FLASK start by
assuming that problems such as buffer overflows are present and design ways
to minimize the exposure that these vunerabilities are able to leverage.
Having a server crash is a bad thing; but, having a server rooted so that
internal data is exposed or other exploits become possible is often worse.

A buffer overflow itself causes currupt memory which is likely to crash the
program and/or cause any number of issues; but, while this is effectively a
denial of service attack, simple explotation of a buffer overflows does not
provide a hacker with access to the system. Buffer overflows on the stack
are the traditional method for gaining access to the system and there are
many of them available, they are often easier to implement, and they are
fairly reliable. If you know what exploits are possible on your platform,
there may be ways to help aleviate them.

Buffer overflows on the heap are generally more difficult to implement,
they are less exact do to the more or less random nature of heap layout at
any given point, and they less known. Heap expoits in the wild didn't
become a major issue until mechanisms designed at stopping stack overflow
exploits started to become more common. It is also somewhat easier to
impliment checks for heap based exploits directly within your code while
many stack protection mechanisms require compiler, operating system, or
even hardware support. Therefore, it makes some sense, if you have a
section of code that is in a likely position for encountering exploit
attempts and (such as network communication buffers) and your
compiler/system uses a hardware based stack, that you might prefer to
allocate memory for them on the heap even if their size is small and
predetermined.

On 2010-05-31, Tim Harig <> wrote:
> A buffer overflow itself causes currupt memory which is likely to crash the
> program and/or cause any number of issues; but, while this is effectively a
> denial of service attack, simple explotation of a buffer overflows does not
> provide a hacker with access to the system. Buffer overflows on the stack
> are the traditional method for gaining access to the system and there are
> many of them available, they are often easier to implement, and they are
> fairly reliable. If you know what exploits are possible on your platform,
> there may be ways to help aleviate them.
>
> Buffer overflows on the heap are generally more difficult to implement,
> they are less exact do to the more or less random nature of heap layout at
> any given point, and they less known. Heap expoits in the wild didn't
> become a major issue until mechanisms designed at stopping stack overflow
> exploits started to become more common. It is also somewhat easier to
> impliment checks for heap based exploits directly within your code while
> many stack protection mechanisms require compiler, operating system, or
> even hardware support. Therefore, it makes some sense, if you have a
> section of code that is in a likely position for encountering exploit
> attempts and (such as network communication buffers) and your
> compiler/system uses a hardware based stack, that you might prefer to
> allocate memory for them on the heap even if their size is small and
> predetermined.

I meant to add:

That said, some systems now have stacks that are execution protected while
the heaps are not. On those systems it might make sense to prefer the
stack. Once again, it is a choice based on knowing the target system.

On 31 May, 08:23, Tim Harig <user...@ilthio.net> wrote:
> On 2010-05-31, Seebs <usenet-nos...@seebs.net> wrote:
> > On 2010-05-31, Tim Harig <user...@ilthio.net> wrote:


> >> While this is theoretically true, I think it is still useful for C
> >> programmers to have some idea about how the stack is implemented on their
> >> system/compiler; especially for stacks that are effectively continuous
> >> arrays whether hardware implemented or not.
>
> > It can be. *However, it's important to get it right -- if you know how the
> > stack was implemented on something else, it can be extremely bad, because
> > it can lead to you *mistakenly* thinking it has provided any of these
> > benefits... *And it's surprising just how often these things can change.
> > There are cases where a compiler option can result in different behavior
> > for the same compiler, same operating system, and same hardware...
>
> I thought that being correct went without saying. *Using mistaken
> information always puts you at risk of doing the wrong thing. (I could make
> a political statement here; but, I will refrain.)

the point is you can write C programs without knowing the deatils of
the stack layout (or even if it has a contiguous in memory stack) for
your particular implementation. You can even write programs not
knowing what the program is going to run on. Newbie questions are
often an indication of an unhealthy interest in implementation
details. Knowing how it /could/ be implemented can be useful just so
long as no one walks away thinking it /must/ be implemted that way.

Do you really look at the hardware stack when your program crashes? I
use a debugger. The last time I looked at a stack as a contiguous
series of memory elemts it was was running on a 680x0... ('20? '10?).
We weren't allowed to sell 68030s in some countries then...

On May 30, 10:05*pm, Keith Thompson <ks...@mib.org> wrote:
> Chad <cdal...@gmail.com> writes:
> Unless you're dealing with very
> low-level details, you don't need to know about how the hardware
> stack works to understand how a C program works.
>
Most people need a concrete picture in their mind to understand
something. Whilst theoretically using abstract definitions like
"automatic storage duration" gives someone the information required to
understand how a C program works, in fact it takes most people an
unacceptably long time to understand something described in those
terms. A description of a stack pushing variables on and popping them
off, however, will give most people a good enopugh mental picture.
Much later you can introduce the idea that some very small or very
high-level implemetations might not have harware stacks, but only
after they are already fluent C programmers.

Malcolm McLean <> writes:
> On May 30, 10:05Â*pm, Keith Thompson <ks...@mib.org> wrote:
>> Chad <cdal...@gmail.com> writes:
>> Unless you're dealing with very
>> low-level details, you don't need to know about how the hardware
>> stack works to understand how a C program works.
>>
> Most people need a concrete picture in their mind to understand
> something. Whilst theoretically using abstract definitions like
> "automatic storage duration" gives someone the information required to
> understand how a C program works, in fact it takes most people an
> unacceptably long time to understand something described in those
> terms. A description of a stack pushing variables on and popping them
> off, however, will give most people a good enopugh mental picture.
> Much later you can introduce the idea that some very small or very
> high-level implemetations might not have harware stacks, but only
> after they are already fluent C programmers.

Certainly different people have different ways of understanding
things.

Speaking for myself, it's enough to understand that storage for
called functions is "pushed" when the function is called and "popped"
when it returns (this implies a stack-like data structure but
says nothing about how the storage is allocated). Knowing whether
successive allocations occupy monotonically increasing or decreasing
storage locations is not something I find particularly helpful.
My mental model of the call stack is more like a linked list than
an array.

I can see that others might find the whole thing easier to
understand if they assume a contiguous stack. But IMHO that way
of thinking is dangerously close to treating addresses and integers
as interchangeable. It's also easy to assume that the stack grows
in a particular direction. And, on some unusual platforms, it's
just wrong.

I suggest that trying to think of it more abstractly is worth
the effort. Not only is it closer to what the language actually
specifies, it can help you understand why a contiguous stack is
a good way of implementing it (as well as why it's not the only
possible implementation).

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

On 2010-06-01, Malcolm McLean <> wrote:
> Most people need a concrete picture in their mind to understand
> something.

I am not sure it is "most". It seems to be something of a continuum, with
some people needing a concrete picture more than others. A friend of mine
has sustained permanent long-term damage because of a teaching method which
relied on a concrete picture to teach children numbers; a small percentage
of children, once taught on that, are never able to really comprehend
any number they can't count visually. If there's a way to recover that
capacity, no one's yet found it.

> A description of a stack pushing variables on and popping them
> off, however, will give most people a good enopugh mental picture.
> Much later you can introduce the idea that some very small or very
> high-level implemetations might not have harware stacks, but only
> after they are already fluent C programmers.

And yet, by that time, it may not be possible for them to become fluent
C programmers, because their mental model is incorrect. Some people have
a VERY hard time correcting an incorrect mental model.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / usenet-
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

On Jun 2, 11:09*am, "io_x" <a...@b.c.invalid> wrote:
> "spinoza1111" <spinoza1...@yahoo.com> ha scritto nel messaggionews:84e098eb-8f7e-402e-97af-...
>
> in my naive think, stack should be one array.
> Where are the reasons for use a linked list?
>
With a linked list it is sometimes easier to implement a stack of
variable sized objects. Also, the stack doesn't have to be contiguous
in memory, which means that expensive reallocation and copy operations
aren't needed to expand the buffer when it overflows.