I’m not sure what the author means here. They’re recursing into a directory with maxpath=260, so worst case 130 levels of directories. This is guaranteed for the app to never go deeper… what’s to be nervous about? (And what influence is there from the language?)
I believe MSVC defaults to 1 MiB of stack space, if you assume 130 recursive calls, that is less than 8 KiB each, which you could easily use in local arrays if you are not mindful.
Some programming languages are generally implemented using a fixed-size stack. C is one such. Some other programming languages, however, are generally implemented using a dynamically growable stack, which can use as much memory as is available on the system, just like heap allocation. I posit that, all other things being equal, it is better to belong to the second category.
C does a dynamically growing stack for the initial thread of the process (MAP_GROWSDOWN) and a fixed stack for the following threads. On 64b machines that’s really limited by rlimit and other resource settings rather than an actual fixed-size stack. I’d say that puts C somewhere in between those options.
That’s not what MAP_GROWSDOWN / MAP_STACK means. There are three concepts that are somewhat conflated as a single thing in *NIX APIs and as two things in Win32 APIs:
Reserving a chunk of the address space.
Committing to provide pages there in such a way that their lack is not observable to userspace (may be immediately, may be lazily after the kernel handles a fault).
Backing the reservation with physical pages.
With mmap and MAP_STACK, you are still reserving a fixed-size chunk of the address space. The kernel is still committing to provide pages when they are required. The argument is just a hint that the kernel should expect that the direction of access is downwards and so if you take a fault somewhere in that region then expect everything above that to be used immediately (if you allocate a 128 KiB array on the stack and initialise it from the start, you don’t want to take 32 page faults, you want to populate all of the stack between the start of the stack frame and start of the array).
On old UNIX systems, memory was split into the stack at the top, the program at the bottom, and the heap in the middle. The heap grew upwards on demand and the stack grew downwards. If they hit in the middle, very bad things happened. This approach doesn’t work with APIs such as mmap that allow you to map things anywhere in the address space, including right below the stack (well, below the guard page at the bottom of the stack, unless you explicitly pass the flag indicating that you’re happy to replace an existing mapping).
I feel like that’s a very theoretical limitation. As in, yes it’s true, but outside of embedded systems / talking to hardware, why would you ever run into a situation where you want to mmap anything in a very specific place, especially just below the live stack? Especially in 64b environment where my heap starts 140 TB below the stack?
In practice if you know you mmap things at weird place, you can be worried about the stack growth. Otherwise, if you want GBs of stack on the main thread… it just works. (2s for 1GB worth of page faults)
(the page fault delay is of course there, if you need extreme speed that could be an issue)
I feel like that’s a very theoretical limitation. As in, yes it’s true, but outside of embedded systems / talking to hardware, why would you ever run into a situation where you want to mmap anything in a very specific place, especially just below the live stack? Especially in 64b environment where my heap starts 140 TB below the stack?
The stack, on a *NIX system, will grow within the limits of its reservation. To grow beyond this, you must reserve more memory (using MAP_FIXED so that it ends up in the right place). In theory, you could catch the SIGSEGV that’s triggered when you hit the bottom of the stack and try to reserve more, but you have to actually write that signal handler. On most *NIX systems the default size for the mains stack is 8 MiB, but for thread stacks it ranges from 64 KiB to 8 MiB. If you hit the 8 MiB limit, on any more-or-less mainstream *NIX system, then you will get a SIGSEGV and it’s up to you to manually grow the stack if that’s what you want. Note that large stack frames may go past the guard page (see: StackClash) and so this isn’t completely reliable.
On modern systems, the stack doesn’t start at the top of the address space, it starts at a random location because putting the main thread’s stack in a predictable location is a great tool for attackers. With OpenBSD’s ASR, for example, every allocation is completely randomised and so there’s a non-zero chance that your binary will be mapped immediately below the guard page for your stack. Thread stacks come from the normal mmap pool and so will be similarly randomised and their location will depend on the other allocations that precede their creation.
On Windows, the situation is a bit different. There’s still a fixed reservation for the stack but it is not committed. The C runtime installs an exception handler that catches the exception for going off the end, moves the guard page down, and commits a new page. Functions that dynamically allocate stack space begin with a call to a function to probe the stack, which commits all of the pages in the required range.
True, although mlock is typically restricted quite aggressively because unprivileged processes can easily kill the system if they’re allowed to lock arbitrary amounts of memory.
Linux 5.17 lets me go higher without issues, the limit you mention comes from ulimit only. It’s more of seatbelt protection than real limit. ulimit -s 1000000 and you get up to ~1GB stack limit (with allocation only as it’s used)
Yes, I’m not recommending this as a solution for most situations - there are good reasons not to do it. Just mentioning the C stack is not fixed-size from the language point of view and there are real systems confirming that.
I don’t think he realizes that he can turn his recursion-less BFS into a DFS by just popping from the opposite end of the queue. Most directory-tree traversal algorithms are DFS (including find) because DFS is memory conservative in comparison to BFS.
It is a great shame that languages force people into such patterns.
I’m not sure what the author means here. They’re recursing into a directory with maxpath=260, so worst case 130 levels of directories. This is guaranteed for the app to never go deeper… what’s to be nervous about? (And what influence is there from the language?)
I believe MSVC defaults to 1 MiB of stack space, if you assume 130 recursive calls, that is less than 8 KiB each, which you could easily use in local arrays if you are not mindful.
Some programming languages are generally implemented using a fixed-size stack. C is one such. Some other programming languages, however, are generally implemented using a dynamically growable stack, which can use as much memory as is available on the system, just like heap allocation. I posit that, all other things being equal, it is better to belong to the second category.
C does a dynamically growing stack for the initial thread of the process (MAP_GROWSDOWN) and a fixed stack for the following threads. On 64b machines that’s really limited by rlimit and other resource settings rather than an actual fixed-size stack. I’d say that puts C somewhere in between those options.
That’s not what
MAP_GROWSDOWN/MAP_STACKmeans. There are three concepts that are somewhat conflated as a single thing in *NIX APIs and as two things in Win32 APIs:With
mmapandMAP_STACK, you are still reserving a fixed-size chunk of the address space. The kernel is still committing to provide pages when they are required. The argument is just a hint that the kernel should expect that the direction of access is downwards and so if you take a fault somewhere in that region then expect everything above that to be used immediately (if you allocate a 128 KiB array on the stack and initialise it from the start, you don’t want to take 32 page faults, you want to populate all of the stack between the start of the stack frame and start of the array).On old UNIX systems, memory was split into the stack at the top, the program at the bottom, and the heap in the middle. The heap grew upwards on demand and the stack grew downwards. If they hit in the middle, very bad things happened. This approach doesn’t work with APIs such as
mmapthat allow you to map things anywhere in the address space, including right below the stack (well, below the guard page at the bottom of the stack, unless you explicitly pass the flag indicating that you’re happy to replace an existing mapping).I feel like that’s a very theoretical limitation. As in, yes it’s true, but outside of embedded systems / talking to hardware, why would you ever run into a situation where you want to mmap anything in a very specific place, especially just below the live stack? Especially in 64b environment where my heap starts 140 TB below the stack?
In practice if you know you mmap things at weird place, you can be worried about the stack growth. Otherwise, if you want GBs of stack on the main thread… it just works. (2s for 1GB worth of page faults)
(the page fault delay is of course there, if you need extreme speed that could be an issue)
The stack, on a *NIX system, will grow within the limits of its reservation. To grow beyond this, you must reserve more memory (using
MAP_FIXEDso that it ends up in the right place). In theory, you could catch the SIGSEGV that’s triggered when you hit the bottom of the stack and try to reserve more, but you have to actually write that signal handler. On most *NIX systems the default size for the mains stack is 8 MiB, but for thread stacks it ranges from 64 KiB to 8 MiB. If you hit the 8 MiB limit, on any more-or-less mainstream *NIX system, then you will get a SIGSEGV and it’s up to you to manually grow the stack if that’s what you want. Note that large stack frames may go past the guard page (see: StackClash) and so this isn’t completely reliable.On modern systems, the stack doesn’t start at the top of the address space, it starts at a random location because putting the main thread’s stack in a predictable location is a great tool for attackers. With OpenBSD’s ASR, for example, every allocation is completely randomised and so there’s a non-zero chance that your binary will be mapped immediately below the guard page for your stack. Thread stacks come from the normal
mmappool and so will be similarly randomised and their location will depend on the other allocations that precede their creation.On Windows, the situation is a bit different. There’s still a fixed reservation for the stack but it is not committed. The C runtime installs an exception handler that catches the exception for going off the end, moves the guard page down, and commits a new page. Functions that dynamically allocate stack space begin with a call to a function to probe the stack, which commits all of the pages in the required range.
Win32 distinguishes 1 (‘reserve’) and conflates 2 with 3 (‘commit’). Unix conflates 1 with 2 (‘map’), but distinguishes 3 (‘mlock’).
True, although
mlockis typically restricted quite aggressively because unprivileged processes can easily kill the system if they’re allowed to lock arbitrary amounts of memory.On which operating system is this? On all major unices that I know of, the stack has a fixed limit, somewhere between 64k and 8m.
Linux 5.17 lets me go higher without issues, the limit you mention comes from ulimit only. It’s more of seatbelt protection than real limit.
ulimit -s 1000000and you get up to ~1GB stack limit (with allocation only as it’s used)Right … so if you want to write portable c code, you can’t count on the environment being set up with a large stack.
The stack will grow dynamically, but it will not shrink. The best you can hope for is that the bits you aren’t using will be swapped out.
Yes, I’m not recommending this as a solution for most situations - there are good reasons not to do it. Just mentioning the C stack is not fixed-size from the language point of view and there are real systems confirming that.
I don’t think he realizes that he can turn his recursion-less BFS into a DFS by just popping from the opposite end of the queue. Most directory-tree traversal algorithms are DFS (including
find) because DFS is memory conservative in comparison to BFS.