0

For reference, I am reading from "Game Engine Architecture 2nd Edition" by Jason Gregory.

Although I understand the theory behind Stack Allocators, I am having trouble implementing it fully. The book goes over Stack-Based Allocators and here is what I have so far in terms of code.

Memory.h file:

#pragma once
#include <iostream>
#include <stack>

typedef std::uint8_t U8;
typedef std::uint16_t U16;
typedef std::uint32_t U32;

typedef std::uintptr_t Marker;

class StackAllocator
{
public:

    explicit StackAllocator(U32 nBytes);    // Allocate all the memory that will be needed
    Marker getMarker();
    void* allocateUnaligned(U32 nBytes);    
    void clear();
    void freeToMarker(const Marker& marker);
private:
    void* bufferptr;            // Start of memory allocated from heap
    U32 nBytes;                 // How large the allocated memory is in # of bytes
};

Memory.cpp file:

#include "Memory.h"

//Stack Allocator
StackAllocator::StackAllocator(U32 nBytes)
    : bufferptr(malloc(nBytes))
    , nBytes(nBytes)
{}

Marker StackAllocator::getMarker()
{

}

void* StackAllocator::allocateUnaligned(U32 nBytes)
{
    
}

void StackAllocator::clear()
{

}

void StackAllocator::freeToMarker(const Marker &marker)
{

}

Admittedly, a lot of this code is copied from the book which is probably why I am confused. Jason Gregory says in the book.

"To ensure this is done properly, a stack allocator often provides a function that returns a marker representing the current top of the stack. The roll-back function then takes one of these markers as its argument."

So either I am completely stupid or there is a contradiction. In the book, he implements the getMarker() function and the freeToMarker(Marker marker) function in the same class, so which scope is managing the markers for the Stack Allocator? Is the class scope supposed to manage a marker stack or is the scope of whatever is calling it supposed to manage a marker stack. Is there even supposed to be a marker stack? He later says that you shouldn't free from arbitrary locations which makes sense but his solution was to roll back all the markers. Where are all of the markers supposed to be stored? From what it looks like, it should be the class scope but then why would the freeToMarker(Marker marker) function take a Marker as one of its arguments if it is already inside the class as a private member. Is this just a mistake by the author or am I missing something important?

P.S: None of the functions are implemented except for the constructor because I am confused about the whole Marker situation

1 Answer 1

2

TL;DR #1

The game application code that you will be writing that which will be making use of a Stack Allocator is responsible for determining (1) when to read the marker, (2) which scope should the marker be associated with, and (3) when to use the marker to free the allocations.

The second responsibility is essentially the scope lifetime analysis for your game application code.

The Stack Allocator merely provides the methods. It has very little responsibilities. All responsibilities are either: eliminated by adhering to the natural laws of SBRM, or, assumed by the programmer who writes the game application code.

To determine how you should design your code (architecture) to allow safe use of Stack Allocator, please conduct a SBRM analysis of your code (or design). A code skeleton and call graph will be needed.

To help visualize the situation, write down a sample call tree by hand. A parent function can give permission to its callee (chain of called functions) to use a Stack Allocator that the parent function has created. When the callee finishes, the parent function can wipe out the section of memory that was used by the callee.

Acronyms:

  • SBRM: Scope-Based Resource Management

TL;DR #2

The "Marker" is simply a marker for point-in-time rollback.

  • It basically tells, directly or indirectly, how many bytes have been used inside the Stack Allocator.
    • Any currently executing code can take a snapshot of the marker.
  • It is basically an integer or pointer value.
    • It is not an "object-oriented" object.
    • It does not perform any duty according to RAII.
    • It does not have a destructor.
  • It may be trivially easy for your to fake this integer value. By passing in a different marker value of your choice, you can wipe out whatever is in the Stack Allocator.

What happens when you call the "free-to-marker" method:

  • Any allocations made prior to the point-in-time represented by the marker will continue to be usable.
  • Any allocations made after the point-in-time represented by the marker will be considered to have been freed.

Visual aid

Imagine a Stack Allocator like a lava flow. Each allocation is given the space that follows immediately after the previous allocation.


Full answer

A Stack Allocator is a do-it-yourself implementation of memory management that follows the spirit of Scope-Based Resource Management (SBRM).

Scope-Based Resource Management is the generalization of the concept of RAII. Or, rather, the RAII feature of C++ is an example of SBRM.

A Stack Allocator has no safety features. It has barely enough tools that will let you implement a correctly-working program following the spirit of SBRM, but only if you use it correctly.

The "Stack" in Stack Allocator has no relationship with the stack segment associated with the current execution thread. However, because of the lack of safety features, it is only suitable for use in a programming style that is strictly single-threaded and minimizes the creation of heap-based "object-oriented" objects.

Think of Stack Allocator as being suitable for a single execution of an algorithm that causes a short-duration burst of high CPU and high RAM usage. The Stack Allocator can provide the temporary memory, but the algorithm's inputs and outputs must reside on the heap that is not managed by a Stack Allocator. Such usage scenarios happen a lot in most types of game programming and data processing.

Stack Allocator is incompatible with multi-threaded programming: any data, object, addresses residing in a Stack Allocator must not be accessed by another thread. Also, anything residing in a Stack Allocator shall not be referenced from an object that is potentially long-living ("escaping"), i.e. any object that may survive past the scope where the object is initially created. That basically means any object that is created on the heap (to an approximation; technically not 100% correct).

The "Marker" is simply a marker for point-in-time rollback.
Refer to the TL;DR section #2 in the beginning.


To determine how you should design your code (architecture) to allow safe use of Stack Allocator, please conduct a SBRM analysis of your code (or design). A code skeleton and call graph will be needed.

2
  • So, if I am understanding correctly, you are saying that the stack allocator should not be managing the memory itself but be used as a tool by the programmer to manage the memory on their own? Jul 29, 2020 at 6:59
  • 2
    @AmeerAbdallah, yes, if my understanding of Stack Allocator is correct (based on: what I already know, what I found online, and the skeleton code you provided.) The big chunk of memory is owned by the stack allocator (and the stack allocator does have a destructor which frees the memory), but that memory is "sub-leased" to callees for use as a giant temporary memory space.
    – rwong
    Jul 29, 2020 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.