I did this mistake years ago with an electric kart ... I had said "I don't see what could go wrong, let's do it with the the cheapest wrenches", then I lost one wheel in a corner ... and I crashed into a hay bale. Now I know, why pneumatic ratchet wrenches are better.
I then found out that below -20C they break. At -45 ° C, it means no fire, no liquid water to drink, no food.
Linus complains that [variable length arrays on stack] generates less efficient code than a statically-sized array. True, but it's a lot more efficient than malloc() at the start of the function and free() at the end.
I think I can safely say that I have never written a dynamically sized array in C. I do however use alloca() sometimes, which amounts to the same thing.
Efficiency counts for nought if you run out of stack.
A scope-assisted no-realloc heap allocator would be very nice. Within each scope, allocating more memory for local data would basically boil down to extending the stack (but that stack pointer probably being at say TLS rather than in a dedicated register). Passing out of a scope would simply reset that data stack pointer to a previous value, essentially freeing everything without any explicit free() type calls. So, it would really boil down into a secondary stack for local data, without a hardware stack pointer register.
A scope-assisted no-realloc heap allocator would be very nice. Within each scope, allocating more memory for local data would basically boil down to extending the stack (but that stack pointer probably being at say TLS rather than in a dedicated register). Passing out of a scope would simply reset that data stack pointer to a previous value, essentially freeing everything without any explicit free() type calls. So, it would really boil down into a secondary stack for local data, without a hardware stack pointer register.
I fail to see the point of this, assuming you're not on a 6502 or something.
Appropriately sizing one stack per thread can be a challenge. Figuring out the right size for *two* stacks per thread, and the balance between them, just seems harder.
Ah, yes. As I say, not enough coffee yet
char c[strlen(a)+strlen(b)+2]; // Urgh! What where they thinking!
Quote from: dunkemhigh on Today at 01:03:23
it's usually possible to know where the limit of the stack is
You still do not seem to be able to differentiate between "heuristic" and "deterministic", it seems.
Appropriately sizing one stack per thread can be a challenge. Figuring out the right size for *two* stacks per thread, and the balance between them, just seems harder.
QuoteYou still do not seem to be able to differentiate between "heuristic" and "deterministic", it seems.I am well aware of the difference.
One advantage I see is that overflow of the separate allocation stack can be easily and reliably detected, and max. usage can be tracked (w/o support from the compiler or hardware).
Furthermore, the "stack" of this allocator could also be segmented (i.e. a list of big chunks), so that it could even grow dynamically by adding additional chunks/pages on demand.
(Depending on the particular use case, dynamic growth may or may not be desired, of course.)
A dynamic-size stack would be pretty inefficient. Obviously depending on the memory layout, it could require being reallocated
A dynamic-size stack would be pretty inefficient. Obviously depending on the memory layout, it could require being reallocatedNo, that won't work. We do not know which of the values in the stack are addresses to the stack, so cannot do a fixup pass. In other words, the stacks must never move.
That doesn't sound practical for small embedded stuff obviously though. It requires a full-fledged MMU with corresponding software support.
On larger systems, that's usually not a big problem to largely oversize the stacks, even if that means some wasted memory.
Appropriately sizing one stack per thread can be a challenge. Figuring out the right size for *two* stacks per thread, and the balance between them, just seems harder.The second one grows and shrinks dynamically; it is not sized beforehand.
With that said, there is a common conception that heap allocation would be more "reliable" than allocating stuff on the stack. This just isn't true. It mostly comes from two facts: one, that on most systems these days, return addresses are stored in the same stack as local objects, which is pretty bad (we already discussed this in other threads), and second, that again on most common systems and programming languages, the allocated stack is usually much smaller than the space reserved for the heap, because heap allocation is favored. We can think of almost-fully stack-based languages that would make this irrelevant.
On embedded targets, I'd love to have that hardware stack pointer relative effective address checks as a tool for "cancelling" recursive processing when it cannot complete within currently available stack space. It would rely on the compiler generating code that always uses stack-pointer relative addressing (even a dummy load) before assigning it to a pointer, so I guess it would make more sense to work on integrating stack address check support into a compiler one uses instead.
Hey, does anyone have any contacts with clang/llvm AVR developers? If they did not reject such an extension (function preamble and stack allocations checking the resulting effective address against a runtime limit) as an idea before seeing some patches first, I might just try and find out what they'd think of some suggested patches. As mentioned before, I do not have the ability to push through GCC levels of cliqueness, though.
It would not help with buffer under/overrun bugs, but it would give those of us interested almost complete control over stack overflows. (Almost, because correctness when an interrupt causes the stack overflow is something I have not worked out yet. Is complicated.) And, of course, it would also work as runtime stack use instrumentation.
decide on how far apart to put them.
This is easier for something with a MMU where you can just place things very far apart, especially with a 64 bit address space, but you still have to decide on the maximum stack size beforehand.
decide on how far apart to put them.Exactly; but that does NOT determine the size of the stack, only the maximum possible size of the stack.
As a side note, it is interesting to examine how C processes asked more data memory from the kernel prior to memory mapping interfaces: the brk() function.
Essentially, it maintains the size of the uninitialized data section (or program break, the end of the uninitialized data section) in exactly the way a local data stack would be maintained by functions requiring space for local variables.
Nothing new under the sun, eh?
When I say something like "you have to figure out the size to allocate for the stack" I'm of course talking about the maximum possible size the stack can grow to. The stack starts off empty.
Sure. You can call sbrk() with a negative increment (or call brk() with a smaller value than you previously called it with) and thus use it as a stack. But not if, as is usual, you used that space as a heap and there are objects allocated and not free'd at the end of the heap space.
Sure. Because C "arrays" in general are not arrays, but only allocating space and pointing at it.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
struct Foo {
int x;
char y[100];
int z;
};
struct Bar {
int x;
char* y;
int z;
};
int main(void) {
printf("Foo: x:%zu z:%zu\n",
offsetof(struct Foo, x), offsetof(struct Foo, z));
printf("Bar: x:%zu z:%zu\n",
offsetof(struct Bar, x), offsetof(struct Bar, z));
return EXIT_SUCCESS;
}
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int array[10];
printf("%s", _Generic((&array),
int*: "int*", int(*)[10]: "int[10]"));
return EXIT_SUCCESS;
}
void bar(int** ptr);
void foo(void) {
int array[10];
bar(&array); // Would be no error, if `array` was a pointer
}
In C++, in which arrays work in a similar manner, it is much easier not notice, as you can have C++ references to arrays as a type.
When I say something like "you have to figure out the size to allocate for the stack" I'm of course talking about the maximum possible size the stack can grow to. The stack starts off empty.When we have virtual memory, and this indeed requires that to be useful, that is not a useful simplification.
We do need to consider the stack a mapping to physical memory here. The current size of this mapping is the current size of the stack. Assuming the stack grows downwards, the stack pointer (roughly, *) points to the smallest address currently in use in the stack. Above that the stack contains data needed by code in the current call chain; below that is unused stack space.
Right now, on AMD64 in Linux, the default stack size is 8 MiB, and typical virtual host environments start at 2 GiB of RAM.
If you use a kernel which initializes and/or fully backs each stack with RAM, you are limited to less than 256 processes and threads, because their stacks alone consume all available RAM.
With that said, there is a common conception that heap allocation would be more "reliable" than allocating stuff on the stack. This just isn't true. It mostly comes from two facts: one, that on most systems these days, return addresses are stored in the same stack as local objects, which is pretty bad (we already discussed this in other threads), and second, that again on most common systems and programming languages, the allocated stack is usually much smaller than the space reserved for the heap, because heap allocation is favored. We can think of almost-fully stack-based languages that would make this irrelevant.
There is a large and important class of programs which absolutely can not be fully stack based.
This is programs based on an event loop, with an amount of state retained between iterations that is not known in advance.
This includes any interactive program (whether character based or GUI) where the user is creating or maintaining a document or in-memory database of some kind.
Sure. Because C "arrays" in general are not arrays, but only allocating space and pointing at it.They are not. Arrays are proper C objects and they’re accessible as arrays, not pointers. Don’t confuse object type with implicit conversions it may undergo.
- The sizeof operator gives you the size of the allocated memory;