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

  • On-demand Event Event Date: September 10, 2014 Modern mobile applications connect systems-of-engagement (mobile apps) with systems-of-record (traditional IT) to deliver new and innovative business value. But the lifecycle for development of mobile apps is also new and different. Emerging trends in mobile development call for faster delivery of incremental features, coupled with feedback from the users of the app "in the wild." This loop of continuous delivery and continuous feedback is how the best mobile …

  • QA teams don't have time to test everything yet they can't afford to ship buggy code. Learn how Coverity can help organizations shrink their testing cycles and reduce regression risk by focusing their manual and automated testing based on the impact of change.

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds