Code: An auto expanding array (or how to use gets() safely).

This is a discussion on Code: An auto expanding array (or how to use gets() safely). within the Windows Programming forums, part of the Platform Specific Boards category; This code shows how to create an auto expanding array. The array will automatically expand as it is written to ...

  1. #1
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544

    Code: An auto expanding array (or how to use gets() safely).

    This code shows how to create an auto expanding array. The array will automatically expand as it is written to or read from. The code is for Windows XP only and will probably only compile with MSVC.

    Sample
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    {
    	xInitializeAutoArrays();
    
    /* gets() sample with auto sizing array. */
    
    	/* Create an auto expanding array with a maximum size of 50MB. */
    	char* strInput = (char*) xCreateAutoArray(50000000);
    
    	try
    	{
    		gets(strInput); /* Reasonably safe use of gets()! */
    	}
    	catch(...)
    	{
    		printf("Greedy gets wanted more than 50 megabytes! (or ran out of memory)\n");
    		exit(-1);
    	}
    	
    	printf("\nstrlen is %d, auto array size is %d\n\n\n", strlen(strInput), xGetAutoArraySize(strInput));
    
    	xFreeAutoArray(strInput);
    
    /* int array sample with auto expanding array. */
    
    	/* Create an auto array with a maximum size of 4 million ints. */
    	int* lpMem = (int*) xCreateAutoArray(4000000 * sizeof(int));
    
    	try
    	{
    		/* Write into the auto expanding array. */
    		for (int i = 0;i < 4000000;i++)
    		{
    			lpMem[i] = i;
    			if (i % 100000 == 0) printf("%d, ", i);
    		}
    
    		puts("\n\n\n");
    
    		/* Read back from the array. Intentionally overrun the maximum size of the auto array. */
    		for (int j = 0;j < 4100000;j++)
    		{
    			int x = lpMem[j];
    			if (j % 100000 == 0) printf("%d, ", j);
    		}
    	}
    	catch(...)
    	{
    		printf("\n\nRan past maximum size of auto array! (or ran out of memory)");
    	}
    
    	printf("\n\nSize is %d\n", xGetAutoArraySize(lpMem));
    	
    	xFreeAutoArray(lpMem);
    
    	getchar();
    	return 0;
    }

    Implementation
    Code:
    #define _WIN32_WINNT 0x500
    #include <windows.h>
    
    static DWORD g_dwPageSize;
    static const DWORD PROTECTION_PAGES = 250;
    
    /*
     * Callback that windows calls when an exception occurs.
     * We check the details and commit the page that caused the fault.
     */
    static LONG WINAPI VectoredHandlerAutoArray(
      PEXCEPTION_POINTERS ExceptionInfo
    )
    {
    	MEMORY_BASIC_INFORMATION mbi;
    	LPVOID                   lpMem;
    
    	if (ExceptionInfo->ExceptionRecord->ExceptionCode != EXCEPTION_ACCESS_VIOLATION ||
    	    ExceptionInfo->ExceptionRecord->NumberParameters < 2)
    	{
    		return EXCEPTION_CONTINUE_SEARCH;
    	}
    
    	lpMem = (LPVOID) ExceptionInfo->ExceptionRecord->ExceptionInformation[1];
    
    	if (VirtualQuery(lpMem, &mbi, sizeof(mbi)) < sizeof(mbi) ||
    	    mbi.State   != MEM_RESERVE ||
    	    mbi.Type    != MEM_PRIVATE ||
    	    mbi.RegionSize <= (PROTECTION_PAGES * g_dwPageSize))
    	{
    		return EXCEPTION_CONTINUE_SEARCH;
    	}
    
    	if (!VirtualAlloc(mbi.AllocationBase,                    // Base address
    	     ((LPBYTE) lpMem - (LPBYTE) mbi.AllocationBase) + 1, // Number of bytes
    	     MEM_COMMIT,                                         // Commit memory
    	     PAGE_READWRITE))                                    // Allow read/write access
    	{
    		return EXCEPTION_CONTINUE_SEARCH;
    	}
    
    	return EXCEPTION_CONTINUE_EXECUTION;
    }
    
    /*
     * Initialize values so that auto arrays can be used.
     * Required once per process.
     */
    BOOL xInitializeAutoArrays(void)
    {
    	SYSTEM_INFO si;
    
    	/* Get the system page size. */
    	GetSystemInfo(&si);
    	g_dwPageSize = si.dwPageSize;
    
    	/* Add our exception callback. */
    	return (NULL != AddVectoredExceptionHandler(TRUE, VectoredHandlerAutoArray));
    }
    
    /*
     * Create an auto sizing array.
     * The maximum size is rounded up to the nearest page (typically a page is 4096 bytes).
     * This auto array must be released with xFreeAutoArray().
     */
    void* xCreateAutoArray(size_t maximum_size)
    {
    	/* Add pages for protection at the end of the auto array. */
    	size_t cbRequired = maximum_size + (PROTECTION_PAGES * g_dwPageSize);
    
    	/* Check for unlikely size_t overflow. If overflowed, use SIZE_T_MAX. */
    	if (cbRequired < maximum_size) cbRequired = ((size_t) -1);
    
    	/* Has xInitializeAutoArrays() been called yet? */
    	if (0 == g_dwPageSize) return NULL;
    
    	/* Reserve the required memory. */
    	return VirtualAlloc(NULL, cbRequired, MEM_RESERVE, PAGE_NOACCESS);
    }
    
    /*
     * Release the auto array.
     */
    void xFreeAutoArray(void* ptr_auto_array)
    {
    	VirtualFree(ptr_auto_array, 0, MEM_RELEASE);
    }
    
    /*
     * Returns the size of the auto array that has been used.
     * This value is rounded up to the nearest page (typically a page is 4096 bytes).
     * Returns 0 on failure.
     */
    size_t xGetAutoArraySize(void* ptr_auto_array)
    {
    	MEMORY_BASIC_INFORMATION mbi;
    
    	if (VirtualQuery(ptr_auto_array, &mbi, sizeof(mbi)) < sizeof(mbi) ||
    	    mbi.State   != MEM_COMMIT ||
    	    mbi.Protect != PAGE_READWRITE)
    	{
    		return 0;
    	}
    
    	return mbi.RegionSize;
    }
    How it works

    The auto expanding array implementation takes advantage of OS exceptions. The xInitializeAutoArrays function registers a vectored exception handler. Vectored exception handler callbacks, a new feature in Windows XP, receive an OS exception and can choose to deal with it before frame based exception handlers. If the exception is corrected by the vectored exception handler, it can return EXCEPTION_CONTINUE_EXECUTION and program execution will continue from where the exception occurred. If the vectored exception handler can not deal with the problem, it can return EXCEPTION_CONTINUE_SEARCH. This will cause the OS to look for higher level exception handlers such as a C++ catch(...) or terminate the program.

    The xCreateAutoArray function reserves address space and protects it with PAGE_NOACCESS. This means, that when the memory is read from or written to, the OS will trigger an EXCEPTION_ACCESS_VIOLATION exception. This causes the OS to call our exception callback where we can commit a page of memory and tell windows to continue execution. Committing memory, unlike reserving address space, means that actual physical storage is allocated, either in RAM or in a page file.

    Conclusion

    Some system functions, such as ReadFile, catch their own exceptions and therefore auto arrays will not work with these functions(even when used indirectly, such as through fread). This fact limits auto arrays to more of a curiosity than a practical tool. While I have used XP-only vectored exception handlers to provide better encapsulation, you can find a sample with similar functionality that uses __try/__except and will work on more platforms.
    Attached Files Attached Files

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Noob question! Code completion - Array challenge
    By theleprechaun in forum C++ Programming
    Replies: 6
    Last Post: 08-22-2008, 09:58 PM
  2. Replies: 2
    Last Post: 07-11-2008, 08:39 AM
  3. Trying to make this code faster & Cramer
    By just2peachy in forum C++ Programming
    Replies: 3
    Last Post: 12-03-2004, 10:54 AM
  4. code doesnt flip array
    By noob2c in forum C Programming
    Replies: 3
    Last Post: 03-29-2003, 09:54 AM
  5. auto <cringe> generated <cringe> code <cringe>
    By RobS in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 08-22-2001, 05:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21