I'm working on a program that reserves two big blocks of virtual memory for use as stacks for things whose size is not statically known. The program tracks pointers to tops of each stack, which I call stack_cursors, and making an allocation consists of calling a function that increments the stack_cursor by the size of the block one wants, commits the next page of memory if this causes it to cross a page boundary, and returns what the position of the cursor was before it was incremented. A function that needs to allocate something that persists beyond its own scope takes a pointer to a stack_cursor, while a function that needs to allocate things for internal use takes a stack_cursor directly, so that its incrementing of the stack_cursor isn't reflected on the caller's end, and the caller's subsequent uses of the stack can overwrite the function's. There are functions that do both internal-only allocations and persistent ones, hence the existence of two stacks.
A shortcoming of this scheme is that, though it commits new pages when a stack grows large enough to need them, it never decommits them if the stack shrinks again. As far as I can tell, whereas stack_cursor "rewinding," such as it is currently, is entirely automatic as long as I correctly pass the stack_cursor by value, if I wanted to support decommitting pages I would have to add a call that manually rewinds the stack_cursor at the end of the scope, to a position that I saved at the beginning of the scope. At that point, continuing to make the distinction between passing a stack_cursor by value versus by reference would only serve as insurance in case I forgot to call the rewind function. There are other reasons taking away that distinction and always passing by pointer is appealing.
It's the kind of repetitive pattern that suggests the need for an abstraction, but I don't really see a way to take the usual approach of "factor it into a function." Is this the kind of situation where metaprogramming could help? Some kind of syntactic extension to C that automates my more specialized stacks like C automates its own stack seems plausible to me, but I've never done that kind of thing before. I don't know how hard it typically is.
A shortcoming of this scheme is that, though it commits new pages when a stack grows large enough to need them, it never decommits them if the stack shrinks again. As far as I can tell, whereas stack_cursor "rewinding," such as it is currently, is entirely automatic as long as I correctly pass the stack_cursor by value, if I wanted to support decommitting pages I would have to add a call that manually rewinds the stack_cursor at the end of the scope, to a position that I saved at the beginning of the scope. At that point, continuing to make the distinction between passing a stack_cursor by value versus by reference would only serve as insurance in case I forgot to call the rewind function. There are other reasons taking away that distinction and always passing by pointer is appealing.
It's the kind of repetitive pattern that suggests the need for an abstraction, but I don't really see a way to take the usual approach of "factor it into a function." Is this the kind of situation where metaprogramming could help? Some kind of syntactic extension to C that automates my more specialized stacks like C automates its own stack seems plausible to me, but I've never done that kind of thing before. I don't know how hard it typically is.
Edited by AlexKindel
on
It's patterns like this that make scope guards and RAII such a useful feature.
However the temp stack would only grow to some "high water level" and no further. Adding logic to reduce the stack size would only mean that the stack will very likely grow again to that point in the future.
One way to avoid that is to keep a high water mark per frame (updated on each allocation) and at the end of each frame copy it into a little ring buffer of stack sizes and only shrink the stack it when multiple frames have passed that didn't need the last k pages.
However the temp stack would only grow to some "high water level" and no further. Adding logic to reduce the stack size would only mean that the stack will very likely grow again to that point in the future.
One way to avoid that is to keep a high water mark per frame (updated on each allocation) and at the end of each frame copy it into a little ring buffer of stack sizes and only shrink the stack it when multiple frames have passed that didn't need the last k pages.
I was in the process of typing up an explanation of what I meant by "there are other reasons...always passing by pointer is appealing," but I decided in the middle of it that they weren't good reasons either, haha.
Would any language's built-in RAII mechanism give me a close equivalent of what I'm doing here? If I were to try to leverage C++ constructors and destructors I guess it would mean doing something with placement new.
Would any language's built-in RAII mechanism give me a close equivalent of what I'm doing here? If I were to try to leverage C++ constructors and destructors I guess it would mean doing something with placement new.
A simple way would be to have a single place in your application loop where you would always de-commit unused pages. With the watermark ring buffer like ratchetfreak said.
AlexKindel
Would any language's built-in RAII mechanism give me a close equivalent of what I'm doing here? If I were to try to leverage C++ constructors and destructors I guess it would mean doing something with placement new.
To clarify the question more: suppose that, instead of having the function that does stack allocations take a stack_cursor, I needed to have it take a large Stack struct that contains a stack_cursor. If I wanted a function's internal allocations to get wiped out without any extra work, as is happening now, I would have to pass the Stack by value, but if it was a large enough struct, I wouldn't want to. At that point I would again start considering always passing by pointer, saving the cursor position at the start of the function, and manually resetting it to the saved position before returning, even if I don't care about decommitting memory pages. Would any language's built-in RAII mechanisms help with that?
I have in fact replaced stack_cursors with small structs - a cursor together with a pointer to the end of the reserved block so the allocation function can check whether there is room for the allocation, and to enable splitting off the upper half of the free portion of the reserved block into a second stack in cases where I want to start a new thread. It's still small enough that switching to manual rewinding in order to be able to always pass by pointer probably wouldn't reduce overhead, much less enough to justify the extra code, but it might get bigger. I don't know yet. I suppose it would always be possible to split the stack_cursors back out of the structs and pass them separately, the structs always by pointer and the cursors by pointer or by value as necessary, but I wouldn't look forward to the verbosity of that.
Edited by AlexKindel
on
I'm not using C++ much but at some point I used "defered statements": defining some code that will be called at the end of the scope:
In my own code to handle temporary stack I do something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | /* Include this somewhere */ #include <utility> template <typename F> struct Defer { Defer( F f ) : f( f ) {} ~Defer( ) { f( ); } F f; }; template <typename F> Defer<F> makeDefer( F f ) { return Defer<F>( f ); }; #define __defer( line ) defer_ ## line #define _defer( line ) __defer( line ) struct defer_dummy { }; template<typename F> Defer<F> operator+( defer_dummy, F&& f ) { return makeDefer<F>( std::forward<F>( f ) ); } #define defer auto _defer( __LINE__ ) = defer_dummy( ) + [ & ]( ) /* --- */ /* Use it like this: */ void example( ) { stack_thing_to_do( ); defer { stack_clean_up( ); /* Will be executed at the end of the function. */ /* Any code can go here. */ } /* body of the function here */ } |
In my own code to handle temporary stack I do something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | typedef struct data { umm reserved; umm used; union { u8* bytes; char* text; umm offset; void* raw; }; } data; data memory_get_temp( data* memory ){ data result; result.reserved = memory->reserved - memory->used; result.used = 0; result.bytes = memory->bytes + memory->used; return result; } void example( data* memory ) { data temp = memory_get_temp( memory ); /* Do things with temp, memory stays unchanged. */ } |