# GeneralAllocator

The core allocator of PPMalloc is GeneralAllocator and its user-level debug layer, GeneralAllocatorDebug. GeneralAllocator is a replacement for new/delete and malloc/free and does a lot more as well. GeneralAllocator combined with GeneralAllocatorDebug provide a rich set of functionality not found in most memory allocation packages.

### GeneralAllocator Features

See the Detailed Feature List for more extensive descriptions of these features and others.

- High performance and high efficiency. No generalized allocator is known to have a better combination.
- Scales very well from small consoles with < 10,000 blocks to large systems with > 1,000,000 blocks.
- Nominal overhead is only 4 bytes per block.
- Highly resistant to both internal and external fragmentation.
- Useful malloc variants, including MallocAligned, Calloc, Realloc, MallocMultiple.
- Extensive internal consistency checking in debug builds.
- Ability to create independent peer heaps and sub-heaps.
- Portability to all platforms (including 64 bit platforms) yet isn't limited or crippled to any least-common denominator platform.
- Fairly extensive heap tracing, reporting, hooking, snapshot taking, and validation functionality.
- Extensive leak reporting output.
- Optional thread-safety.
- Can assign your own core memory to the heap or let it get it from the system itself.
- Automated heap allocation activity recording and playback via AllocationRecorder.
- Manual or automatic expansion of internal memory source.
- Many compile time and runtime configurable options.

### GeneralAllocatorDebug Features

- Delayed frees with user-definable delayed free policy (time-based, volume based, count based, etc.)
- Advanced guard fill (a.k.a. sentinel) functionality such as scaling guard fill sizes and min/max fill size clamps.
- Various debug fills, including new fill, free fill, delayed free fill, guard fill.
- Pointer validation. Say goodbye to mysterious double-free bugs.
- Ability to associate names with allocations.
- Ability to automatically store call stacks with allocations (globally or on a per-allocation basis).
- Ability to store file/line allocation place with allocations.
- Ability to automatically store debug overhead with allocations.
- Various other storage as well.
- Ability for the user to associate any arbitrary data with an allocation.

### Quick Interface Summary

The primary interface for GeneralAllocator is this (please refer to the Doxygen documentation or the source code itself for the most up-to-date version of this interface):

>     class GeneralAllocator
>     {
>     public:
>        GeneralAllocator(void* pInitialCore = NULL, size_t nInitialCoreSize = 0, bool bShouldFreeInitialCore = true, bool bShouldTrimInitialCore = false, CoreFreeFunction pInitialCoreFreeFunction = NULL, void* pInitialCoreFreeFunctionContext = NULL)
>       ~GeneralAllocator();

>        bool   Init(void* pInitialCore = NULL, size_t nInitialCoreSize = 0, bool bShouldFreeInitialCore = true, bool bShouldTrimInitialCore = false, CoreFreeFunction pInitialCoreFreeFunction = NULL, void* pInitialCoreFreeFunctionContext = NULL);
>        bool   Shutdown();

>        void*  Malloc(size_t nSize);
>        void*  MallocAligned(size_t nSize, size_t nAlignment = 0, size_t nAlignmentOffset = 0);
>        void** MallocMultiple(size_t nElementCount, size_t nElementSize, void* pResultArray[]);
>        void** MallocMultiple(size_t nElementCount, const size_t nElementSizes[], void* pResultArray[]);
>        void*  Calloc(size_t nElementCount, size_t nElementSize);
>        void*  Realloc(void* p, size_t nNewSize);
>        void   Free(void* p);

>        bool   AddCore(void* pInitialCore, size_t nInitialCoreSize);
>        size_t TrimCore(size_t nPadding);
>        void   SetThreadSafetyEnabled(bool bEnable);
>        void   Lock(bool bEnable);

>        size_t GetUsableSize(void* pData);
>        size_t GetBlockSize(const void* pData) const;
>        void   SetTraceFunction(TraceFunction pTraceFunction, void* pContext);
>        void   SetTraceFieldDelimiters(unsigned char fieldDelimiter, unsigned char recordDelimiter);
>        bool   ValidateAdress(void* pAddress, bool bPointerIsAllocation);
>        bool   ValidateHeap(HeapValidationLevel heapValidationLevel = kHeapValidationLevelBasic);
>        void   SetAutoHeapValidation(HeapValidationLevel heapValidationLevel, size_t nFrequency);
>        void   SetMallocFailureFunction(MallocFailureFunction pMallocFailureFunction, void* pContext);
>        void   SetAssertionFailureFunction(AssertionFailureFunction pAssertionFailureFunction, void* pContext);
>        void   SetHookFuncton(HookFunction* pHookFunction, void* pContext);
>        void   SetTraceFunction(TraceFunction pTraceFunction, void* pContext);
>        void   TraceAllocatedMemory(TraceFunction pTraceFunction = NULL, void* pTraceFunctionContext = NULL);
>        size_t DescribeData(const void* pData, char* pBuffer, size_t nBufferLength);
>        bool   ReportHeap(HeapReportFunction, void* pContext, int nBlockTypeFlags, bool bMakeCopy = false, void* pStorage = NULL, size_t nStorageSize = 0);
>        void*  TakeSnapshot(int nBlockTypeFlags = kBlockTypeAll, bool bMakeCopy = false, void* pStorage = NULL, size_t nStorageSize = 0);
>        void   FreeSnapshot(void* pSnapshot);
>        void*  ReportBegin(void* pSnapshot = NULL, int nBlockTypeFlags = kBlockTypeAll, bool bMakeCopy = false, void* pStorage = NULL, size_t nStorageSize = 0);
>        void*  ReportNext(const void* pContext, int nBlockTypeFlags = kBlockTypeAll);
>        void   ReportEnd(const void* pContext);
>     };

The primary interface for GeneralAllocatorDebug is this:

>     class GeneralAllocatorDebug
>     {
>        GeneralAllocatorDebug();
>       ~GeneralAllocatorDebug();

>        bool     Init(void* pInitialCore = NULL, size_t nInitialCoreSize = 0);
>        bool     Shutdown();

>        void*    Malloc(size_t nSize, unsigned nDebugDataFlags, const char* pName = NULL, const char* pFile = NULL, int nLine = 0);
>        void*    MallocAligned(size_t nSize, size_t nAlignment, size_t nAlignmentOffset, unsigned nDebugDataFlags, const char* pName = NULL, const char* pFile = NULL, int nLine = 0);
>        void*    Calloc(size_t nElementCount, size_t nElementSize, unsigned nDebugDataFlags, const char* pName = NULL, const char* pFile = NULL, int nLine = 0);

>        void     SetAllocator(GeneralAllocator* pAllocator);

>        unsigned GetDefaultDebugDataFlags() const;
>        bool     GetDefaultDebugDataFlag(unsigned debugDataFlag) const;
>        void     SetDefaultDebugDataFlags(unsigned flags);
>        void     SetDefaultDebugDataFlag(unsigned debugDataFlag);

>        void     SetDelayedFreePolicy(DelayedFreePolicy policy, int value);
>        void     ClearDelayedFreeList();

>        void     EnableValidPointerTracking(bool bEnable);

>        bool     ValidateAddress(const void* pData, bool bPointerIsAllocation = true);

>        void     SetGuardSize(float fGuardSizeRatio, size_t nMinGuardSize, size_t nMaxGuardSize);
>        void     SetFillValues(unsigned char cFree        = kDefaultFillValueFree,
>                               unsigned char cDelayedFree = kDefaultFillValueDelayedFree,
>                               unsigned char cNew         = kDefaultFillValueNew,
>                               unsigned char cGuard       = kDefaultFillValueGuard,
>                               unsigned char cUnusedCore  = kDefaultFillValueUnusedCore);
>        int       GetCurrentGroupId() const;
>        void      SetDefaultDebugDataLocation(DebugDataLocation debugDataLocation);
>        size_t    GetDebugDataLength(const void* pData, DebugDataLocation debugDataLocation = kDebugDataLocationDefault, void** ppDebugData = NULL);
>        void*     GetDebugData(const void* pData, DebugDataIdType id,
>                               void* pDebugData, size_t nDataLength, size_t* pActualDataLength = NULL,
>                               DebugDataLocation debugDataLocation = kDebugDataLocationDefault);
>        void*     SetDebugData(void* pData, DebugDataIdType id,
>                               const void* pDebugData, size_t nDataLength,
>                               DebugDataLocation debugDataLocation = kDebugDataLocationDefault);
>         const     Metrics& GetMetrics(MetricType metricsType);
>     };

### Compile-Time Configurable Options

There are a number of compile-time options for GeneralAllocator. Most of these you don't want to change, but the others may have some use.

Option | Description
PPM_DEBUG | Defined as 0, 1, 2, or 3. Default is 1 for debug, 0 for release. If you compile with PPM_DEBUG defined as non-zero, a number of assertion checks are enabled that will catch more memory errors. You probably won't be able to make much sense of the actual assertion errors, but they should help you locate incorrectly overwritten memory. The checking is fairly extensive, and will slow down execution noticeably. The higher the defined value, the more extensive the debugging. Basically, release builds should have PPM_DEBUG = 0, debug builds should have a PPM_DEBUG >= 1, and builds done by maintainers of this library should have PPM_DEBUG >= 3. Setting PPM_DEBUG may also be helpful if you are trying to modify this code. The assertions in the check routines spell out in more detail the assumptions and invariants underlying the algorithms. Setting PPM_DEBUG does not provide an automated mechanism for checking that all accesses to malloced memory stay within their bounds. This kind of functionality is generally considered to be outside the scope of the allocator, as it requires functionality that is often compiler- or platform-specific.
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              | PPM_DEBUG value | Purpose                  | Meaning
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              |   0             | Release builds           | - No GeneralAllocator automatic validation functionality is present.
              |                 |                          | - GeneralAllocatorDebug is not usable.
              |                 |                          | - No GeneralAllocatorDebuig automatic validation functionality is present.
              |                 |                          | - GeneralAllocator and GeneralAllocatorDebug asserts are disabled.
              |                 |                          | - PPM_DEBUG_PRESERVE_PRIOR disabled by default. You can override this.
              |                 |                          | - PPM_VIRTUAL_ENABLED disabled by default. You can override this.
              |                 |                          | - Automatic heap validation is not supported. You can still manually call the function.
              |                 |                          | - This yields the highest performance.
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              |   1             | Basic debug builds       | - Very minimal GeneralAllocator automatic validation functionality is present.
              |                 |                          | - GeneralAllocatorDebug is usable.
              |                 |                          | - Very minimal GeneralAllocatorDebug automatic validation functionality is present.
              |                 |                          | - PPM_DEBUG_PRESERVE_PRIOR enabled by default. You can override this.
              |                 |                          | - PPM_VIRTUAL_ENABLED enabled by default. You can override this,
              |                 |                          |   but PPM_VIRTUAL_ENABLED is required in order to use GeneralAllocatorDebug.
              |                 |                          | - PPM_AUTO_HEAP_VALIDATION_SUPPORTED is enabled by default. This merely means that
              |                 |                          |   you can now set up automatic heap validations to occur.
              |                 |                          | - This yields the highest performance possible while using GeneralAllocatorDebug;
              |                 |                          |   performance should be fast enough for all game and tool applications.
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              |   2             | Extended debug builds    | - Primary GeneralAllocator automatic validation functionality is present.
              |                 |                          | - Primary GeneralAllocatorDebug automatic validation functionality is present.
              |                 |                          | - GeneralAllocatorDebug guard fills enabled by default.
              |                 |                          | - This yields performance that will be adequate for some purposes but slow for others.
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              |   3             | Developer builds         | - Extended GeneralAllocator automatic validation functionality is present.
              |                 |                          | - Extended GeneralAllocatorDebug automatic validation functionality is present.
              |                 |                          | - This mode is only intended for developing and testing the library;
              |                 |                          |   its performance will be slow for many large game applications.
              |-----------------|--------------------------|-----------------------------------------------------------------------------------------
              |   4             | Developer builds         | - Heavy GeneralAllocator automatic validation functionality is present.
              |                 |                          | - Heavy GeneralAllocatorDebug automatic validation functionality is present.
              |                 |                          | - This mode is only intended for developing and testing the library;
              |                 |                          |   its performance will be slow for most large game applications.
              |-----------------|--------------------------------------------------------------------------------------------------------------------
PPM_VIRTUAL_ENABLED | Defined as 0 or 1. Default is same as PPM_DEBUG. PPM_VIRTUAL is optionally defined as 'virtual' in order to allow PPMalloc functions to become virtual. For normal usage, virtual isn't required and would impose a performance penalty. However, there are times where virtual may be useful, particularly in the case where you want to subclass PPMalloc in order to provide a debug-time variation (e.g. class PPMallocDebug).
PPM_HOOKS_SUPPORTED | Defined as 0 or 1. Default is same as PPM_DEBUG. If true, then the user can install callback hooks that notify the user of high level allocation events.
PPM_THREAD_SAFETY_SUPPORTED | Defined as 0 or 1. Default is 1 if the platform supports it. Defines whether thread safety is supported, which is not the same thing as thread safety being enabled. You need the former before you can have the latter. If thread safety is supported, then you can optionally define PPM_THREAD_SAFETY_BY_DEFAULT to 1 to enable it by default. It can always be enabled or disabled at runtime by calling SetThreadSafetyEnabled, but if GeneralAllocator is being statically created, then you might need to have thread safety enabling defined ahead of time.
PPM_THREAD_SAFETY_BY_DEFAULT | Defined as 0 or 1. Default is same as PPM_THREAD_SAFETY_SUPPORTED. Defines if upon initialization of a GeneralAllocation instance it is thread safe.
PPM_INTERRUPT_DISABLING_ENABLED | Defined as 0 or 1. Default is 1 for console platforms with slow mutexes and if PPM_THREAD_SAFETY_SUPPORTED is enabled. If disabling of interrupts is allowed, then GeneralAllocator very briefly (~10 CPU cycles) disables interrupts on systems with slow mutexes in order to greatly speed mutex locking and unlocking. The PS2 console in particular has a reputation for having very slow mutex locking and so allocation speed greatly improves when this option is enabled.
PPM_ASSERT_ENABLED | Defined as 0 or 1. Default is same as PPM_DEBUG. If true, then assertion failures are reported via GeneralAllocator::AssertionFailure. Note that PPM_ASSERT_ENABLED is usable even if PPM_DEBUG is 0; this comes into play in particular when doing heap validations, as all validation failures are reported through the AssertionFailure mechanism. Note that you do not want this feature enabled in a shipping build, as it costs CPU cycles.
PPM_DEBUG_FILL | Defined as 0 or 2+. Default is 0 for PPM_DEBUG <= 1; otherwise same as PPM_DEBUG) Enables GeneralAllocator internal debug fills and validation of those fills.
PPM_DEBUG_PRESERVE_PRIOR | Defined as 0 or 1. Default is same as PPM_DEBUG This is a define that tells whether we are saving the mnPrior field of chunks for debug purposes instead of letting them be (intentionally) overrun by the previous chunk (in order to save memory). You generally don't want to change this value unless you are doing maintenance and testing work on this library.
PPM_NULL_POINTER_FREE_ENABLED | Defined as 0 or 1. Default is 1. Defines whether or not the Free function allows passing of a NULL pointer as an argument. Since the C language standard free() allows passing NULL pointers, we duplicate this behaviour by default.
PPM_AUTO_HEAP_VALIDATION_SUPPORTED | Defined as 0 or 1. Default is same as PPM_DEBUG. If defined as non-zero, then automatic heap validation code is compiled and usable via the SetAutomaticHeapValidation user function.
PPM_FASTBIN_TRIM_ENABLED | Defined as 0 or 1. Default is 0. This controls whether Free() of a very small chunk can immediately lead to trimming. Setting to non-zero can reduce memory footprint, but will almost always slow down programs that use a lot of small chunks.
PPM_INTERNAL_CORE_FREE_ENABLED | Defined as 0 or 1. Default is 1 When defined to 1, core that is set to be freed but has no callback function will be freed via a call to the platform-specific memory freeing function. For basic console platforms this function is usually malloc, while for PC platforms this is VirtualFree.
PPM_MALLOC_AS_COREALLOC | Defined as 0 or 1. Default is 1 unless the platform supports advanced memory management. When defined to 1, this instructs the system to get core from malloc and not directly from the system. You must be careful with this in that if you are using this allocator to directly replace malloc, you probably don't want to set PPM_MALLOC_AS_COREALLOC to be 1, as it would cause an infinite loop at runtime if AddCoreInternal was called.
PPM_MALLOC_AS_MMAPALLOC | Defined as 0 or 1. Default is 0. When defined to 1, this causes the memory mapped allocations to instead use plain old malloc to retrieve the memory. You probably don't want to change this value unless you are doing some kind of testing during library maintenance.
PPM_MMAP_SUPPORTED | Defined as 0 or 1. Default is 1 if the system supports mapped memory. If true, Malloc makes use mapped memory to allocate very large blocks. This also enables the use of mapped memory if normal core memory allocation mechanisms fail.
PPM_HIGH_SUPPORTED | Defined as 0 or 1. Default is 1 for console platforms, and 0 for others. Defines whether or not the concept of requesting from 'high' memory is supported. The idea behind requesting high memory allocation is that you are requesting the allocator to return memory that is separate from normal memory. Usually this is done with the intent of reducing fragmentation. If you allocate memory that you know will be permanent as high but leave other more dynamic allocations as 'low', then you will likely get less fragmentation due to there being no holes in the high memory. The concept of high memory can be implemented by truly using high memory addresses or can also be implemented by having separate pools for high and low memory.
PPM_NEW_CORE_SIZE_DEFAULT | Unsigned integer. Default value is platform-specific. Default size of new core memory blocks when they are automatically internally allocated.
PPM_CORE_INCREMENT_SIZE_DEFAULT | Unsigned integer <= PPM_NEW_CORE_SIZE_DEFAULT. Default value is platform-specific. Default size to add to core memory blocks when the system supports extending existing blocks.
PPM_REALLOC_C99_ENABLED | Defined as 0 or 1. Default is 1 (C99 behaviour enabled). Defines whether or not the Realloc function behaves as per the C89 standard or per the C99 standard. There are small differences between the two which are documented with the GeneralAllocator::Realloc source code.

### Example Usage

Here we provide some basic examples showing how to use GeneralAllocator.

Here's an example of how to simply create an allocator and use it.

>     #include "PPMalloc/EAGeneralAllocator.h"

>     EA::Allocator::GeneralAllocator allocator;
>     void* p = allocator.Malloc(20);
>     allocator.Free(p);

To use GeneralAllocatorDebug, you simply substitute that class for GeneralAllocator, like this:

>     #include "PPMalloc/EAGeneralAllocatorDebug.h"
>     using namespace EA::Allocator;

>     GeneralAllocatorDebug allocator;
>     void* p = allocator.Malloc(20);
>     allocator.Free(p);

If you want to initialize the allocator with a large block of existing memory, you simply pass that memory into the constructor or Init function, like so:

>     GeneralAllocator allocator(pMemory, nMemorySize);

If you would like to use GeneralAllocatorDebug to allocate memory with a name attached to it, you would simply construct this:

    allocator.MallocDebug(20, 0, "model");

If you would like to use GeneralAllocatorDebug to allocate memory which tracks the full call stack and the allocation time along with a name, you would do this:

>     unsigned flags = (1 << GeneralAllocatorDebug::kDebugDataIdCallStack) ||
>                      (1 << GeneralAllocatorDebug::kDebugDataIdAllocationTime);
>     allocator.MallocDebug(20, flags, "model");

If you would like to validate the heap to see if there has been any corruption, you would do this:

>     allocator.ValidateHeap(GeneralAllocator::kHeapValidationLevelFull);

If you would like to provide a C++ hook function to track all allocation activity, you would use SetHookFunction like this:

>     void SomeClass::SetupHook()
>     {
>         allocator.SetHookFunction(HookFunction, this);
>     }

>     static void HookFunction(const GeneralAllocator::HookInfo* pHI, void* pContext)
>     {
>         SomeClass* const pSomeClass = (SomeClass*)pContext; // Possibly use this.

>         if(!pHookInfo->mbEntry) // If we are being called at the end of the function (so we can see the result)...
>         {
>             if(pHookInfo->mHookType == GeneralAllocator::kHookTypeMalloc)
>                 pHookInfo->mnSizeInputTotal, pHookInfo->mpDataOutput;
>             else if(pHookInfo->mHookType == GeneralAllocator::kHookTypeFree)
>                 pHookInfo->mpDataInput;
>         }
>     }

If you would like to use GeneralAllocator as a sub heap of some other heap (e.g. another GeneralAllocator), you would simply do this:

>     GeneralAllocator gaParent;
>     GeneralAllocator gaChild(gParent.Malloc(1000000), 1000000, false);

If you want to have a sub heap that grows on demand, you would do this:

>     size_t SubHeapCoreFreeFunction(GeneralAllocator* /*pChild*/, void* pCore, size_t nSize, void* pContext)
>     {
>         GeneralAllocator* const pParent = (GeneralAllocator*)pContext;
>         pParent->Free(pCore);
>         return nSize;
>     }

>     bool MallocFailureFunction(GeneralAllocator* pChild, size_t nMallocRequestedSize,
>                                 size_t nAllocatorRequestedSize, void* pContext)
>     {
>         GeneralAllocator* const pParent = (GeneralAllocator*)pContext;

>         if(nAllocatorRequestedSize < 1000000) // Allocate at least N bytes of new core.
>            nAllocatorRequestedSize = 1000000; // This is not necessarily required.

>         nAllocatorRequestedSize = EA::Allocator::PPM_AlignUp(nSize, EA::Allocator::GetPageSize());

>         void* const pNewCore = pParent->Malloc(nAllocatorRequestedSize);

>         if(pNewCore)
>            pChild->AddCore(pNewCore, nAllocatorRequestedSize, true, false, SubHeapCoreFreeFunction, pParent);

>         return (pNewCore != NULL);
>     }

>     // Create a main heap.
>     GeneralAllocator gaParent;

>     // Create a sub heap from the main heap.
>     GeneralAllocator gaChild(gaParent.Malloc(1000000), 1000000, false, false, SubHeapCoreFreeFunction, &gaParent);
>     gaChild.SetMallocFailureFunction(MallocFailureFunction, &gaParent);
>     gaChild.SetOption(GeneralAllocator::kOptionEnableSystemAlloc, 0);

### Block Overhead

Here we make a table showing block size overhead for GeneralAllocator when compiled with optimizations enabled. All user request sizes are rounded up to the next 4 byte boundary in GeneralAllocator. We show only up to allocation sizes of 128; the pattern of actual memory usage is evident and can be scaled up to any allocation size. These overhead values apply to both normally allocated blocks and blocks allocated with a specified alignment. In summary, blocks have an overhead of 4 or 8 bytes above the user request size, depending on the size.

User Request Size | Actual Memory Usage
0 | 16
4 | 16
8 | 16
12 | 16
16 | 24
20 | 24
24 | 32
28 | 32
32 | 40
36 | 40
40 | 48
44 | 48
48 | 56
52 | 56
56 | 64
60 | 64
64 | 72
68 | 72
72 | 80
76 | 80
80 | 88
84 | 88
88 | 96
92 | 96
96 | 104
100 | 104
104 | 112
108 | 112
112 | 120
116 | 120
120 | 128
124 | 128
128 | 136

### Debugging Chunk corruption

One way to track down Chunk corruption is to find out exactly how the Chunk is being corrupted and put a memory change watch on a byte being corrupted. To do that requires a small amount of knowledge about how the Chunks are organized.

Allocated Chunk

> struct Chunk {
> size_type mnPriorSize;
> size_type mnSize;
> char userData[]; // This is at least 8 bytes.
> };

Free Chunk

> struct Chunk {
> size_type mnPriorSize;
> size_type mnSize; // bit 0 tells if previous Chunk in memory is allocated.
> Chunk* mpPrevChunk;
> Chunk* mpNextChunk;
> // 0 or more bytes here
> };

In a new heap there is just one free Chunk, and it has an mnSize of some big value. In a heap with a bunch of allocated memory, there is a bunch of Chunks of variable size in memory one after another, like so:

> Chunk 0 (low memory)
> Chunk 1
> Chunk 2
> Chunk 3 (high memory)

The diagram above makes it look like each chunk is of the same size, but they are of variable sizes but a minimum of 16 bytes each. When you have a pointer to an object, it is the userData section of a Chunk, and the start of the Chunk is 8 bytes prior to it. In the case of a C++ array, the pointer that operator new[] returns to you is going to be 4 or 8 bytes beyond userData (depending on the alignment requirements of your class), as the compiler stores its own 'array count' variable at the beginning of the userData.

When a Chunk is corrupted, usually the mnPriorSize or mnSize variables are overwritten. The heap can tell they are corrupted because they will have an overly high value or because there will be a mismatch between a Chunk's mnSize and the next Chunk in memory's mnPriorSize. So if you are freeing an array belonging to Chunk 1 above and you get an error saying that Chunk 2 is corrupted, then you want to watch the mnPriorSize and mnSize fields of Chunk2.

### GeneralAllocatorDebug Chunks

#### Chunk

The primary allocation unit of a GeneralAllocator heap is a Chunk. A Chunk is what is returned to the user from an allocation call, though the user is given a pointer to 8 bytes within the Chunk, after the header. The user data of a chunk is of variable size and is of course based on the requested allocation size.

> Head[8] | Data[]

#### Heap

A GeneralAllocator heap consists of a big block of memory (called Core) which is a bunch of Chunks one after another. As memory is allocated the Core space is dynamically divided into Chunks which are returned to the user. When memory is freed, newly contiguous free Chunks may be coalesced into larger free Chunks.

> H[8] | D[] | H[8] | D[] | H[8] | D[] | ...

#### Debug Chunk

GeneralAllocatorDebug associates meta-data with each Chunk, based on the debug options enabled by the user. The user can choose, for example, to enable saving the allocation time and allocation call stack for the allocation. See enum DebugDataId for more. This is accomplished by making a making a little database of tagged info at the end debug Chunks and increasing the size of the Chunk to accomodate this storage. GeneralAllocatorDebug intercepts all allocation calls in order to bump up this size before the memory is actually allocated by GeneralAllocator. The format of the storage is:

> uint16_t debugInfoSize (size of all debug info, not including this uint16_t)
> uint16_t info1Size (size of all of info1, not including this uitn16_t)
> uint16_t info1Type (arbitrary unique numeric id for the given type)
> char[] info1Data
> uint16_t info2Size
> uint16_t info2Type
> char[] info2Data
> etc.

This variable data struct is written backwards in the Chunk, starting from the end, and it isn't aligned on any boundary. So a debug Chunk in memory that has two debug info entries looks like this:

> H | D | info2Data | info2Type | info2Size | info1Data | info1Type | info1Size | debugInfoSize

GeneralAllocatorDebug also supports guard fills, which is extra padding beyond the user-requested amount of memory. Guard fills are placed after the user data and before the debug data:

> H | D | 0xababababababab | info2Data | info2Type | info2Size | info1Data | info1Type | info1Size | debugInfoSize

When debug data is looked up with the GeneralAllocatorDebug::GetDebugData function, it goes to the end of the block and reads debugInfoSize. It asserts that the size is sane and then walks info1Size, info1Type, info2Size, info2Type, etc. to find the type of data it's looking for. It asserts along the way that the sizes are sane. If one of the sanity checks fails, then it means one of two things:

- The heap has been corrupted by some misplaced memory write.
- Somehow GeneralAllocatorDebug's attempts to intercept calls and write the debug info struct have been subverted. This isn't supposed to happen, but a bug in PPMalloc or a miscompile of some sort could be a cause of it.

### PPMalloc Debug Fills

Fill Type | Fill Pattern Default | Meaning
--- | --- | ---
Free | 0xdd | Fill value for user memory that has been freed.
Delayed Free | 0xde | Fill value for user memory which is in delayed free state. Delayed free memory is memory that has been freed by the user but is kept in limbo and not yet available for new allocations.
New | 0xcd | Fill value for newly allocated user memory.
Guard | 0xab | Fill value for guard memory returned in new user memory. Guard memory is extra padding beyond the user-requested amount of memory.
Unused Core | 0xfe | Fill value for core that is unassigned to free or allocated memory. Core memory is the large blocks of memory obtained from the system which are used to fund the allocator.

End of document