What is a stack?

Discussion in 'C Programming' started by spinoza1111, May 29, 2010.

  1. spinoza1111

    spinoza1111 Guest

    Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    and I am an IT and nursing student in Manila. My teacher uses the word
    "stack". What does she mean?
     
    spinoza1111, May 29, 2010
    #1
    1. Advertising

  2. spinoza1111

    osmium Guest

    "spinoza1111" wrote:

    > Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    > and I am an IT and nursing student in Manila. My teacher uses the word
    > "stack". What does she mean?


    Well, princess, only your teacher knows what she means when she uses a word.
    Here are two possible meanings:

    o A stack, as in a stack of pancakes.
    o A woman, often young, with appealing mammary glands. Unfortunately, due to
    one warped old man (Hugh Hefner) and his impact on the culture, appealing is
    oftentimes equated to "large".
     
    osmium, May 29, 2010
    #2
    1. Advertising

  3. spinoza1111

    Seebs Guest

    On 2010-05-29, osmium <> wrote:
    > "spinoza1111" wrote:
    >> Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,


    Why did you respond to the obvious fakepost from Nilges?

    Admittedly, yours was funny in a way that hers wasn't.

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

    spinoza1111 Guest

    On May 30, 3:04 am, Seebs <> wrote:
    > On 2010-05-29, osmium <> wrote:
    >
    > > "spinoza1111" wrote:
    > >> Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,

    >
    > Why did you respond to the obvious fakepost from Nilges?
    >
    > Admittedly, yours was funny in a way that hers wasn't.


    Perhaps. But can you define a stack?
    >
    > -s
    > --
    > Copyright 2010, all wrongs reversed.  Peter Seebach / ://www.seebs.net/log/<-- lawsuits, religion, and funny pictureshttp://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    spinoza1111, May 30, 2010
    #4
  5. spinoza1111

    spinoza1111 Guest

    On May 30, 3:06 pm, "io_x" <> wrote:
    > a stack is a common array of memory where is defined the functions push()
    > and pop() [and descrive what the functions do]


    Pretty good, not bad, but could be better
    First of all, you shouldn't the meaning so to fetter
    To a "common" region of allocation
    To do so is itself common, and and instance of inanition.
    A stack can be a private thing and not for the public eye
    Like when you're hungry and eat a whole pizza pie.

    Nor 'tis it by necessity
    An array...ain't pretty.
    It can be a list what is linked
    Just don't mess it up as does Heathfield whose tool, stinked.

    And your worst error was that you left the interesting part
    Subject to the student's random brain fart.
    You do not define push and you don't define pull
    That is how you look like, well, sort of a fool.

    A stack is a data set,
    A collection of items without predefined order,
    Which can be accessed only at one end.
    It's not a mouth and an anus
    Nor is it a moon or Uranus,
    But the top element can be removed by means of an operation called
    onomatopoeiatistically , pop
    And an element can be added by another operation called push, and push
    and pop can be used in principle and sub specie aeternitatis, without
    stop.

    Managers do not love stacks
    Great programmers like them
    Managers fear that a sort of collection of hacks
    Or, a Communist conspiracy, ahem,
    Lurks in the very idea of separation of concerns
    It gives managers heart burns.
    A stack says, get back to later,
    Alligator,
    Once I've solved another problem.
    >
    > "spinoza1111" <> ha scritto nel messaggionews:...
    >
    >
    >
    > > Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    > > and I am an IT and nursing student in Manila. My teacher uses the word
    > > "stack". What does she mean?
     
    spinoza1111, May 30, 2010
    #5
  6. spinoza1111

    spinoza1111 Guest

    On May 30, 9:19 pm, spinoza1111 <> wrote:
    > On May 30, 3:06 pm, "io_x" <> wrote:
    >
    > > a stack is a common array of memory where is defined the functions push()
    > > and pop() [and descrive what the functions do]

    >
    > Pretty good, not bad, but could be better
    > First of all, you shouldn't the meaning so to fetter
    > To a "common" region of allocation
    > To do so is itself common, and and instance of inanition.
    > A stack can be a private thing and not for the public eye
    > Like when you're hungry and eat a whole pizza pie.
    >
    > Nor 'tis it by necessity
    > An array...ain't pretty.
    > It can be a list what is linked
    > Just don't mess it up as does Heathfield whose tool, stinked.
    >
    > And your worst error was that you left the interesting part
    > Subject to the student's random brain fart.
    > You do not define push and you don't define pull
    > That is how you look like, well, sort of a fool.
    >
    > A stack is a data set,
    > A collection of items without predefined order,
    > Which can be accessed only at one end.
    > It's not a mouth and an anus
    > Nor is it a moon or Uranus,
    > But the top element can be removed by means of an operation called
    > onomatopoeiatistically , pop
    > And an element can be added by another operation called push, and push
    > and pop can be used in principle and sub specie aeternitatis, without
    > stop.
    >
    > Managers do not love stacks
    > Great programmers like them
    > Managers fear that a sort of collection of hacks
    > Or, a Communist conspiracy, ahem,
    > Lurks in the very idea of separation of concerns
    > It gives managers heart burns.
    > A stack says, get back to later,
    > Alligator,
    > Once I've solved another problem.
    >
    >
    >
    >
    >
    > > "spinoza1111" <> ha scritto nel messaggionews:...

    >
    > > > Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    > > > and I am an IT and nursing student in Manila. My teacher uses the word
    > > > "stack". What does she mean?


    Revised Poem about Stacks

    Pretty good, not bad, but could be better
    First of all, you shouldn't the meaning so to fetter
    To a "common" region of allocation
    To do so is itself common, and and instance of inanition.
    A stack can be a private thing and not for the public eye
    Like when you're hungry and eat a whole pizza pie.

    Nor 'tis it by necessity
    An array...ain't pretty.
    It can be a list what is linked
    Just don't mess it up as does Heathfield whose tool, stinked.

    And your worst error was that you left the interesting part
    Subject to the student's random brain fart.
    You do not define push and you don't define pull
    That is how you look like, well, sort of a fool.

    A stack is a data set,
    A collection of items without predefined order,
    Which can be accessed only at one end.
    It's not a mouth and an anus
    Nor is it a moon of Uranus,
    But the top element can be removed by means of an operation called
    onomatopoeiatistically , pop
    And an element can be added by another operation called push, and
    push
    and pop can be used in principle and sub specie aeternitatis, without
    stop.

    Managers do not love stacks
    Great programmers like them
    Managers fear that a sort of collection of hacks
    Or, a Communist conspiracy, ahem,
    Lurks in the very idea of separation of concerns
    It gives managers heart burns.
    A stack says, get back to ya later,
    Alligator,
    Once I've solved another problem.

    The stack is a scandal, and the stack is a shame
    For those who think that programming is a child's game
    Who get a job as a senior software engineer,
    And sneer,
    At Schildt because they think he's queer,
    Without having the guts to take computer science
    Lest Mommy's little darling have to suffer the defiance
    Of some prof who doesn't think he's a genius
    Who think in fact he's a weirdo and a wuss.

    You see, the American university
    Teaches the little darlings that anything expressed parenthetically
    Can be disregarded by the high level hotshots they aspire to be.
    Whereas the stack declares that God is in the details
    Inside those cute little parentheses with their funny little tails
    Even as Mies von der Rohe
    Said, take care of everything thoroughly.
     
    spinoza1111, May 30, 2010
    #6
  7. spinoza1111

    spinoza1111 Guest

    On May 30, 9:40 pm, spinoza1111 <> wrote:
    > On May 30, 9:19 pm, spinoza1111 <> wrote:
    >
    >
    >
    >
    >
    > > On May 30, 3:06 pm, "io_x" <> wrote:

    >
    > > > a stack is a common array of memory where is defined the functions push()
    > > > and pop() [and descrive what the functions do]

    >
    > > Pretty good, not bad, but could be better
    > > First of all, you shouldn't the meaning so to fetter
    > > To a "common" region of allocation
    > > To do so is itself common, and and instance of inanition.
    > > A stack can be a private thing and not for the public eye
    > > Like when you're hungry and eat a whole pizza pie.

    >
    > > Nor 'tis it by necessity
    > > An array...ain't pretty.
    > > It can be a list what is linked
    > > Just don't mess it up as does Heathfield whose tool, stinked.

    >
    > > And your worst error was that you left the interesting part
    > > Subject to the student's random brain fart.
    > > You do not define push and you don't define pull
    > > That is how you look like, well, sort of a fool.

    >
    > > A stack is a data set,
    > > A collection of items without predefined order,
    > > Which can be accessed only at one end.
    > > It's not a mouth and an anus
    > > Nor is it a moon or Uranus,
    > > But the top element can be removed by means of an operation called
    > > onomatopoeiatistically , pop
    > > And an element can be added by another operation called push, and push
    > > and pop can be used in principle and sub specie aeternitatis, without
    > > stop.

    >
    > > Managers do not love stacks
    > > Great programmers like them
    > > Managers fear that a sort of collection of hacks
    > > Or, a Communist conspiracy, ahem,
    > > Lurks in the very idea of separation of concerns
    > > It gives managers heart burns.
    > > A stack says, get back to later,
    > > Alligator,
    > > Once I've solved another problem.

    >
    > > > "spinoza1111" <> ha scritto nel messaggionews:...

    >
    > > > > Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    > > > > and I am an IT and nursing student in Manila. My teacher uses the word
    > > > > "stack". What does she mean?

    >
    > Revised Poem about Stacks
    >
    > Pretty good, not bad, but could be better
    > First of all, you shouldn't the meaning so to fetter
    > To a "common" region of allocation
    > To do so is itself common, and and instance of inanition.
    > A stack can be a private thing and not for the public eye
    > Like when you're hungry and eat a whole pizza pie.
    >
    > Nor 'tis it by necessity
    > An array...ain't pretty.
    > It can be a list what is linked
    > Just don't mess it up as does Heathfield whose tool, stinked.
    >
    > And your worst error was that you left the interesting part
    > Subject to the student's random brain fart.
    > You do not define push and you don't define pull
    > That is how you look like, well, sort of a fool.
    >
    > A stack is a data set,
    > A collection of items without predefined order,
    > Which can be accessed only at one end.
    > It's not a mouth and an anus
    > Nor is it a moon of Uranus,
    > But the top element can be removed by means of an operation called
    > onomatopoeiatistically , pop
    > And an element can be added by another operation called push, and
    > push
    > and pop can be used in principle and sub specie aeternitatis, without
    > stop.
    >
    > Managers do not love stacks
    > Great programmers like them
    > Managers fear that a sort of collection of hacks
    > Or, a Communist conspiracy, ahem,
    > Lurks in the very idea of separation of concerns
    > It gives managers heart burns.
    > A stack says, get back to ya later,
    > Alligator,
    > Once I've solved another problem.
    >
    > The stack is a scandal, and the stack is a shame
    > For those who think that programming is a child's game
    > Who get a job as a senior software engineer,
    > And sneer,
    > At Schildt because they think he's queer,
    > Without having the guts to take computer science
    > Lest Mommy's little darling have to suffer the defiance
    > Of some prof who doesn't think he's a genius
    > Who think in fact he's a weirdo and a wuss.
    >
    > You see, the American university
    > Teaches the little darlings that anything expressed parenthetically
    > Can be disregarded by the high level hotshots they aspire to be.
    > Whereas the stack declares that God is in the details
    > Inside those cute little parentheses with their funny little tails
    > Even as Mies von der Rohe
    > Said, take care of everything thoroughly.


    Johnny: Mister Science! Mister Science! What is a stack? Petey Seebach
    says they are a Communist Conspiracy!

    Mister Science: Well, Johnny, let a list be a set that can contain
    duplicates; since you've already read Principia Mathematica,
    Grundgezetze der Arithmetik, and Set Theory and Its Logic, you know
    that a set is an unordered collection of things that cannot contain
    duplicates. A stack is a list, then, over which only the operations
    pop() and push(x) are defined. pop() deletes the "top" element of the
    list (you will shortly learn the meaning of the word "top" in this
    context). If the stack is empty, pop() may be implemented as a no
    operation, but for best results should signal or raise an error.
    push() adds an element to the stack. Now, what is the "top" element of
    a stack? First of all, let the stack be empty.

    Johnny: OK!

    Mister Science: push(x) followed by pop() will result in an empty
    stack.

    Johnny: Wow!

    Mister Science: Furthermore, if pop is defined as a function, its
    value will be x.

    Johnny: Cool!

    Mister Science: More generally, the second will be true of any stack
    no matter how many elements it contains. As long as these assertions,
    and no other, hold, the data structure is a stack. The stack can be an
    array, it can be a linked list, it can be bugger all if I care as long
    as these assertions are satisfied.

    Johnny: OOOOO you said a bad word.

    Mister Science: Sorry, little Johnny, but remember what Lenin said:
    you cannot make an omelette without breaking heads!

    Johnny: OK! I sure will! Thanks, Mister Science!
     
    spinoza1111, May 30, 2010
    #7
  8. spinoza1111

    spinoza1111 Guest

    On May 29, 9:18 pm, "osmium" <> wrote:
    > "spinoza1111" wrote:
    > > Hi, my name is Corazon Rosa Princess MacArthur Mirador de los Angeles,
    > > and I am an IT and nursing student in Manila. My teacher uses the word
    > > "stack". What does she mean?

    >
    > Well, princess, only your teacher knows what she means when she uses a word.
    > Here are two possible meanings:
    >
    > o A stack, as in a stack of pancakes.
    > o A woman, often young, with appealing mammary glands. Unfortunately, due to
    > one warped old man (Hugh Hefner) and his impact on the culture, appealing is
    > oftentimes equated to "large".


    To vicious children who inherit the universal license and could not
    live without it, all old men are by definition warped, since they've
    killed the father without resolving the Oedipal crisis.

    That's why they AP out of survey classes. The class might be taught by
    a warped old man.

    Besides, real men like enormous bazongas.
     
    spinoza1111, May 30, 2010
    #8
  9. spinoza1111

    Chad Guest

    On May 30, 12:06 am, "io_x" <> 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?
     
    Chad, May 30, 2010
    #9
  10. Chad <> writes:
    > On May 30, 12:06 am, "io_x" <> 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.

    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.

    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
    any kind of stack for function calls; such systems cannot directly
    support recursion, and therefore cannot support a C implementation.
    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.
    Don't let them confuse you..

    --
    Keith Thompson (The_Other_Keith) <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"
     
    Keith Thompson, May 30, 2010
    #10
  11. spinoza1111

    spinoza1111 Guest

    On May 31, 3:05 am, Keith Thompson <> wrote:
    > Chad <> writes:
    > > On May 30, 12:06 am, "io_x" <> 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 fuckin' guy, named Kiki.

    >
    > --
    > Keith Thompson (The_Other_Keith)  <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"
     
    spinoza1111, May 31, 2010
    #11
  12. spinoza1111

    Tim Harig Guest

    On 2010-05-30, Keith Thompson <> 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.
     
    Tim Harig, May 31, 2010
    #12
  13. spinoza1111

    Seebs Guest

    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 /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, May 31, 2010
    #13
  14. spinoza1111

    Tim Harig Guest

    On 2010-05-31, Seebs <> 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.
     
    Tim Harig, May 31, 2010
    #14
  15. spinoza1111

    Tim Harig Guest

    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.
     
    Tim Harig, May 31, 2010
    #15
  16. On 31 May, 08:23, Tim Harig <> wrote:
    > On 2010-05-31, Seebs <> 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.)


    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...
     
    Nick Keighley, Jun 1, 2010
    #16
  17. On May 30, 10:05 pm, Keith Thompson <> wrote:
    > Chad <> 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, Jun 1, 2010
    #17
  18. Malcolm McLean <> writes:
    > On May 30, 10:05 pm, Keith Thompson <> wrote:
    >> Chad <> 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) <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"
     
    Keith Thompson, Jun 1, 2010
    #18
  19. spinoza1111

    Seebs Guest

    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 /
    http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
    http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
     
    Seebs, Jun 1, 2010
    #19
  20. On Jun 2, 11:09 am, "io_x" <> wrote:
    > "spinoza1111" <> ha scritto nel messaggionews:...
    >
    > 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.
     
    Malcolm McLean, Jun 2, 2010
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Surinder Singh
    Replies:
    1
    Views:
    1,213
    Richard Bos
    Dec 20, 2007
  2. Casey Hawthorne
    Replies:
    3
    Views:
    1,104
    Flash Gordon
    Nov 1, 2009
  3. Debajit Adhikary
    Replies:
    36
    Views:
    2,318
    Andre Kaufmann
    Feb 10, 2011
  4. Sam Roberts
    Replies:
    1
    Views:
    228
    Yukihiro Matsumoto
    Feb 11, 2005
  5. Kenneth McDonald

    Why stack overflow with such a small stack?

    Kenneth McDonald, Aug 30, 2007, in forum: Ruby
    Replies:
    7
    Views:
    264
    Kenneth McDonald
    Sep 1, 2007
Loading...

Share This Page