Inflable Arrays in Win32

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.



Comments

  • problems with __int64

    Posted by Legacy on 06/25/2003 12:00am

    Originally posted by: Petko Popov

    I received e-mail from at least two people who could not compile the header file because the their compiler did not recognize the __int64 type. I have never experienced this problem and don't know what to do to simulate it.

    A brief Yahoo search yielded some advice on the topic. Only if you have the problem, why don't you try to add a line

    #define __int64 long long

    before you include the header file?

    In the worst case, you can write your own class that implements the 64-bit integer operations. This should not be too hard if you like the exercise.

    If someone has had the same problem and solved it, please post how you did it. Thank you!

    Reply
  • Class scope

    Posted by Legacy on 09/10/2002 12:00am

    Originally posted by: Zorro

    Good code :) But it works only in function scope. Do it working in class scope or incapsulate in external class or template. Good luck ;)

    class Test{
    DWORD *x;
    Callocator cal;
    Test(){
    cal.Alloc(x, 300000000);
    }
    `Test(){
    cal.Free(x);
    }
    }

    Reply
  • Err...

    Posted by Legacy on 09/28/2001 12:00am

    Originally posted by: pouzzler

    This is a wonderful piece of code -and I wouldn't dream of even making something that complicated;

    Still is is not just why <vector>, <deque>, <list>, ... were devised?

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • "Security" is the number one issue holding business leaders back from the cloud. But does the reality match the perception? Keeping data close to home, on premises, makes business and IT leaders feel inherently more secure. But the truth is, cloud solutions can offer companies real, tangible security advantages. Before you assume that on-site is the only way to keep data safe, it's worth taking a comprehensive approach to evaluating risks. Doing so can lead to big benefits.

  • Live Event Date: August 14, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT Data protection has long been considered "overhead" by many organizations in the past, many chalking it up to an insurance policy or an extended warranty you may never use. The realities of today make data protection a must-have, as we live in a data driven society. The digital assets we create, share, and collaborate with others on must be managed and protected for many purposes. Check out this upcoming eSeminar and join eVault Chief Technology …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds