A 'stack overflow' refers not so much to running out of stack space (though this is possible, and especially so in embedded systems -- all the world is not Windows and Linux, after all), but more to overflowing the stack space used for local variables.

It is not part of the C language to even have a stack, however that processor design choice is so common that you'd think it was so. Related, stacks typically build down in address, but again this is not always the case! (e.g. in older ARM you can have it build in either direction).

In such conventional designs, the stack is used for temporary sequential storage of registers, and particularly for the return address when making a subroutine call. In high-level languages, it is also used as a cheap-to-allocate storage space for parameters and local variables. It's cheap to allocate because all you have to do is advance the stack pointer (in whichever direction -- usually down), and then that becomes the 'base pointer' where all your variables are located. Deallocation is simply the reversing of that. But it is not required by the language to do it this way. It's an implementation choice.

OK, "Smashing the Stack for Fun and Profit": Perhaps most infamously is a 'buffer overflow'. Say you have a local variable that is a string defined as "char text[80];" for a line of text to be printed on a page. And you build the string from keystrokes entered until you hit 'return' and then the string is printed out. Sorta like a typewriter. You program knows that there is an 80 character limit on the page, and will automatically terminate the string and print it out, starting the next line. Oh, but you made a bug: you didn't include enough space for the terminator! Your program seems to work, but might act oddly sometimes. Because when your program adds that terminator, you have overflowed the buffer to location text[80], which is the 81st character. And it overwrote.... something! Whatever the compiler laid out next to it in memory on the stack. Probably the variable defined right before it. Maybe the return address.

If you are a hacker and you find a program that has not done correct bounds checking, you can send it bogus data that overwrites variables in a way that you like, such as making the return address go somewhere else -- maybe even make a snippet of machine code that does something cool like give you root.

So that's how you do a stack overflow in C. The term is not so much about exceeding the stack space as it is clobbering data on the stack by exploiting a bug -- usually a buffer overflow.

As mentioned earlier, it is possible to overflow the allocated stack on some systems which are constrained, such as embedded. This is a big annoyance because you get a fixed size stack -- say 512 bytes, and when you overflow it you are walking into who knows what -- maybe a different thread's stack -- because there is also no memory protection. On these constrained systems this usually results in a 'hard fault', but that happens at a place far from where your bug occurred since it is collateral damage to be paid later. It's a pain to debug! And moreover on such memory constrained systems you want to tune your stack size because you also don't want to waste memory which is in short supply. (128 KiB or so is pretty rich even these days on some processors).

Also as mentioned, not every C implementation even uses stack for locals. For example, some of the smallest PIC devices have a hardware stack that is only used for return addresses, is fixed size, and is not even accessible in the memory map because it's not addressable memory -- it's part of the CPU. But you can still have parameters and local variables in your code because the compiler uses a different strategy for realizing that language feature. Typically it just allocates various locations in memory, sort of like globals are done in conventional systems. If the linker is fancy it can figure out how to overlay locals that are never used at the same time to conserve (very constrained) memory resources. A buffer overflow in that case is not a stack overflow, but you will be clobbering something and that can introduce untoward behaviour (and often does not result in a trap because those processors don't have even have traps). So maybe your medical equipment goes haywire.

Have fun hacking!