3 ms·

You're right, I leapt over some points, and landed slightly outside the discussion - I guess I think of growing the stack and allocating heap memory as somethin

by e12e 9y ago

You're right, I leapt over some points, and landed slightly outside the discussion - I guess I think of growing the stack and allocating heap memory as something the kernel should be the arbiter of - and that the api should never allow you to grow into your own (or another process') memory. I suppose it's fine to say mallloc will return memory, but it's up to the process to check if there are any overlaps - but that sounds a little crazy?

caf 9y ago
That is basically how it works, with the caveat that if you want the kernel to arbitrate your stack expansion you must only expand by a page at a time (and that's what gcc's -fstack-check does). If you decrement your stack pointer by a large value and then offset it - which is essentially what's happening in these cases - the kernel can't arbitrate that because if the access lands in otherwise allocated memory it doesn't fault and so the kernel never sees the access at all.
- e12e 9y ago
  I meant that the equivalent for mallloc would be that if you allocate 1mb buffer and a 2mb buffer, the kernel might return a 2mb buffer overlapping your earlier 1mb buffer - and be all like: "you asked for 1, you asked for 2 - and you've got 2 - if you wanted 3, you should've asked for 3". Afaik mallloc doesn't work like that - it assumes that you want more memory (and can fail or succeed etc). I can see how the current stack/heap thing evolved - but I still think it's crazy :-)
  - caf 9y ago
    The stack doesn't work like that either. All that's happening here is that userspace is moving its stack pointer into the heap it had previously allocated. Note that "moving the stack pointer" is not a kernel-mediated operation.
    - e12e 9y ago
      No of course, but the fact that you can "ask for more memory" by growing the stack onto your heap (rather than say, having the two start somewhere together and grow apart) - means that there's an asymmetry: mallloc will give you more ram or fail; growing the stack - can make your allocated memory overlap.
      - caf 9y ago
        Your stack has to grow towards something. Sure, you can have it grow towards the bottom of the address space (which, due to wraparound, is also the top - where it will safely collide with the kernel addresses) but that only works for one stack - as soon as you create another thread, its thread has to grow towards something else.
geofft 9y ago
The thing is that (as I mentioned upthread) "growing the stack" isn't a well-defined operation. What actually happens is that you overflow the stack by a very little bit, and the kernel says "Oh, I bet you want more stack pages" and maps some virtual memory for you. But the kernel is guessing; it has no way of knowing that you meant to grow the stack. Maybe you dereferenced a wild pointer that, by chance, happened to point right below the current stack. Conversely, if you grow your stack by some value on the order of gigabytes, you're basically coming up with a pointer that appears to have no relation to the stack, and dereferencing it. So the platform is going to do exactly what it does if you were to dereference the same pointer value with no stack involved: read/write memory if it's mapped and segfault if not. You could totally imagine a platform where growing the stack were a more well-defined operation. You want to avoid each function call and local allocation having the overhead of a system call, though: the nice thing about the current scheme is that it's zero-overhead if there's a mapped stack page. So the scheme was designed (or probably emerged more than was intentionally designed) for the case where syscalls are very slow, MMUs work fine, and perfect memory safety isn't the goal, i.e., the original UNIX target audience. :-) You could keep a thread-local variable somewhere indicating the current stack limit, and make a system call when you need to increment it. That doesn't require an MMU at all: the userspace API is that you call some system routine when you need to expand the stack, and it says yes or no (or it either says yes or kills you with a segfault, or whatever). In an MMU-less system, you can just keep track of the amount of heap allocation, and have the system routine fail when you're too close to your heap. Or you could do stack probing, which works but requires an MMU.

by e12e 9y ago

caf 9y ago

That is basically how it works, with the caveat that if you want the kernel to arbitrate your stack expansion you must only expand by a page at a time (and that's what gcc's -fstack-check does). If you decrement your stack pointer by a large value and then offset it - which is essentially what's happening in these cases - the kernel can't arbitrate that because if the access lands in otherwise allocated memory it doesn't fault and so the kernel never sees the access at all.

e12e 9y ago
I meant that the equivalent for mallloc would be that if you allocate 1mb buffer and a 2mb buffer, the kernel might return a 2mb buffer overlapping your earlier 1mb buffer - and be all like: "you asked for 1, you asked for 2 - and you've got 2 - if you wanted 3, you should've asked for 3". Afaik mallloc doesn't work like that - it assumes that you want more memory (and can fail or succeed etc). I can see how the current stack/heap thing evolved - but I still think it's crazy :-)
- caf 9y ago
  The stack doesn't work like that either. All that's happening here is that userspace is moving its stack pointer into the heap it had previously allocated. Note that "moving the stack pointer" is not a kernel-mediated operation.
  - e12e 9y ago
    No of course, but the fact that you can "ask for more memory" by growing the stack onto your heap (rather than say, having the two start somewhere together and grow apart) - means that there's an asymmetry: mallloc will give you more ram or fail; growing the stack - can make your allocated memory overlap.
    - caf 9y ago
      Your stack has to grow towards something. Sure, you can have it grow towards the bottom of the address space (which, due to wraparound, is also the top - where it will safely collide with the kernel addresses) but that only works for one stack - as soon as you create another thread, its thread has to grow towards something else.

geofft 9y ago

The thing is that (as I mentioned upthread) "growing the stack" isn't a well-defined operation. What actually happens is that you overflow the stack by a very little bit, and the kernel says "Oh, I bet you want more stack pages" and maps some virtual memory for you. But the kernel is guessing; it has no way of knowing that you meant to grow the stack. Maybe you dereferenced a wild pointer that, by chance, happened to point right below the current stack. Conversely, if you grow your stack by some value on the order of gigabytes, you're basically coming up with a pointer that appears to have no relation to the stack, and dereferencing it. So the platform is going to do exactly what it does if you were to dereference the same pointer value with no stack involved: read/write memory if it's mapped and segfault if not. You could totally imagine a platform where growing the stack were a more well-defined operation. You want to avoid each function call and local allocation having the overhead of a system call, though: the nice thing about the current scheme is that it's zero-overhead if there's a mapped stack page. So the scheme was designed (or probably emerged more than was intentionally designed) for the case where syscalls are very slow, MMUs work fine, and perfect memory safety isn't the goal, i.e., the original UNIX target audience. :-) You could keep a thread-local variable somewhere indicating the current stack limit, and make a system call when you need to increment it. That doesn't require an MMU at all: the userspace API is that you call some system routine when you need to expand the stack, and it says yes or no (or it either says yes or kills you with a segfault, or whatever). In an MMU-less system, you can just keep track of the amount of heap allocation, and have the system routine fail when you're too close to your heap. Or you could do stack probing, which works but requires an MMU.