Environment: Win32
In many cases it is necessary to store data of unpredictable size in a memory buffer. I have seen a large number of cases where the programmer has thought “that buffer size is ten times bigger than we will ever need” and, of course, the application crashes in many user environments because the buffer was actually of insufficient size. Or the buffer size is big enough at the expense of inefficient memory management. The inflatable array described here allows to declare really huge buffers without actually allocating much more memory than is really needed to store the actual data.
This code has been inspired by an example from a previous edition of the MUST READ book “Programming Applications for Microsoft Windows” by Jeffrey Richter. I don’t know why this part is missing in the latest edition. I can say for sure there were two or three serious bugs in the code sample there which I remember I had to fix when I needed sizeable memory storage in a project three years ago. In my latest project I needed such functionality again. Since I have no access to the code I wrote then nor could I find an old edition of the book, I decided to write the inflable array funtionality on my own.
The idea behind the inflable array is to reserve a really large block of virtual memory, but leave the memory uncommitted. The access to that memory is guarded by an exception handler. When a location within the inflatable array is accessed, an access violation exception occurs (unless the same location has been previously accessed and memory has been already commited). The handler catches the exception, commits the memory if it is within the array limits and returns the code execution to exactly the place where the access violation occured.
I agree this technique doesn’t provide unlimited array size, but the limit is orders of magnitude higher than with statically allocated buffers. Additionally, no memory is allocated before it is needed.
The use of the inflable array is very simple and is illustrated in the source.
CallocInflable.h
#if !defined(__CALLOCINFLABLE_H__)
#define __CALLOCINFLABLE_H__#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000#include <windows.h>
__int32 UTL_CommitMemory(LPEXCEPTION_POINTERS ep,
void * pBaseAddress,
void * pLastAddress,
unsigned __int32 dwElementSize);
void UTL_DecommitMemory(void * pBaseAddress,
unsigned __int32 dwTotalSize);
void UTL_ReleaseMemory(void * pBaseAddress,
unsigned __int32 dwTotalSize);#define VIRTUAL_CALLOC(POINTER,NUMBER)
{
void * __pBaseAddress = NULL;
void * __pLastAddress = NULL;
unsigned __int32 __dwElementSize = sizeof(*POINTER);
unsigned __int32 __dwNumberOfElements = (NUMBER);
unsigned __int64 __qwTotalSize =
(unsigned __int64)__dwElementSize *
(unsigned __int64)__dwNumberOfElements;
__try {
__pBaseAddress =
::VirtualAlloc(NULL,
(unsigned __int32)__qwTotalSize,
MEM_RESERVE, PAGE_READWRITE);
if ( __pBaseAddress == NULL ) {
__leave;
}
__pLastAddress = (char*)__pBaseAddress + __qwTotalSize;
*((void**)&(POINTER)) = __pBaseAddress;
__try {#define VIRTUAL_FREE
} __except ( ::GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?
UTL_CommitMemory(GetExceptionInformation(),
__pBaseAddress,
__pLastAddress,
__dwElementSize) :
EXCEPTION_CONTINUE_SEARCH ) {
}
} __finally {
UTL_ReleaseMemory(__pBaseAddress,
(unsigned __int32)__qwTotalSize);
}
}#define VIRTUAL_RESET
UTL_DecommitMemory(__pBaseAddress,
(unsigned __int32)__qwTotalSize);#endif // #if !defined(__CALLOCINFLABLE_H__)
CallocInflable.cpp
#define WIN32_LEAN_AND_MEAN
#include “CallocInflable.h”__int32 UTL_CommitMemory(LPEXCEPTION_POINTERS ep,
void * pBaseAddress,
void * pLastAddress,
unsigned __int32 dwElementSize)
{
PVOID pVirtualAddress =
(PVOID)(ep->ExceptionRecord->ExceptionInformation[1]);if ( pVirtualAddress < pBaseAddress ||
pVirtualAddress >= pLastAddress) {
// well, access violation is not within the array bounds –
// don’t mess up with it
return EXCEPTION_CONTINUE_SEARCH;
}// we must figure out where the element starts and where it ends
// otherwise we may get in heavy trouble if first accessing
// the non-first byte of the last element
// this is obvious when the element size is large, but it is also
// dangerous for small sizes// figure out what to allocate
void * pBaseAddressOfAccessedElement =
(char*)pBaseAddress +
(((char*)pVirtualAddress –
(char*)pBaseAddress) / dwElementSize) * dwElementSize;
// Memory allocated by VirtualAlloc is automatically initialized
// to zero, unless MEM_RESET is specified
if ( ::VirtualAlloc(pBaseAddressOfAccessedElement,
dwElementSize,
MEM_COMMIT,
PAGE_READWRITE) == NULL ) {
return EXCEPTION_CONTINUE_SEARCH;
} else {
return EXCEPTION_CONTINUE_EXECUTION;
}
}void UTL_DecommitMemory(void * pBaseAddress,
unsigned __int32 dwTotalSize)
{
if ( pBaseAddress != NULL ) {
VirtualFree(pBaseAddress, dwTotalSize, MEM_DECOMMIT);
}
}void UTL_ReleaseMemory(void * pBaseAddress,
unsigned __int32 dwTotalSize)
{
if ( pBaseAddress != NULL ) {
UTL_DecommitMemory(pBaseAddress, dwTotalSize);
VirtualFree(pBaseAddress, 0, MEM_RELEASE);
}
}void test()
{
DWORD * x;VIRTUAL_CALLOC(x, 300000000); // 1.2G
*x = 42;
x[1000] = 42;
x[999999] = 42;
x[9999999] = 42;
x[99999999] = 42;
x[29999999] = 42;VIRTUAL_FREE
}
The only limitation is that because the inflatable array uses structured exception handling, it is not possible to have C++ exceptions or class objects with non-trivial constructors and destructors in the function where the array is used. In most cases, this can easily be solved by separating the inflatable array and the class objects in different functions.