Allocating too much memory and holding it for too long can obviously move you into a low memory state. A less obvious but equally insidious way to run out of memory is to make a lot of small allocations that cause fragmentation of the heap. Basically, here's how fragmentation develops.
Your application has default heap space that is allocated by VirtualAlloc(). Initially, only one page of the heap is committed, but of course, more is reserved. When you make an allocation request, the system looks for a single, contiguous, free region in the committed page(s) of your application's heap. If it finds one, it returns a pointer (or handle) to your block. If it can't find one, it commits enough pages to satisfy the request.
Obviously, a physical page in the heap may contain memory blocks from dozens of different allocation requests. The system simply fits them into a page wherever there is space for them. None of these pages can be decommitted and returned to the allocation pool until all of the individual allocations in the page are freed.
When an allocation request grows the heap, it may not necessarily use all of the space in the newly committed pages. If subsequent small allocations are satisfied using "leftover" space in the newly committed pages, these pages can't be freed when the "big" allocation is freed. Also, if the "little" allocations are in the middle of the page, they dramatically reduce the size of the largest contiguous free block that can be allocated.
In a nutshell, heap fragmentation arises from these two things:
- A page can only be freed if it is completely empty of allocations.
- Allocation requests must be satisfied with blocks of contiguous free memory.
It's quite possible that you could have far more than the number of bytes available in the local heap to satisfy an allocation request, and still have to commit a new page to actually get a contiguous block of memory.
In this case, the problem is not so much that we needed to make a few big, temporary allocations of memory—it is that the big allocations are interspersed with smaller allocations that had a different lifespan.
Document processing is a good example of a situation like this: First you load data and structures, then after that you make frequent, small allocations for string buffers and the like. If you make many small allocations that share a predictable lifespan, you can conserve memory by creating a separate application-specific heap. By using this strategy, you can prevent your application's local heap from unnecessary growth and subsequent fragmentation.
Porting Tip: If you make many small allocations that share a predictable lifespan, you can conserve memory and prevent local heap fragmentation by creating a private, application-specific heap and using it for small frequent allocations.
There are five functions used to create and manage a private heap:
HANDLE HeapCreate(DWORD flOptions, DWORD dwInitialSize, DWORD dwMaximumSize); LPVOID HeapAlloc(HANDLE hHeap, DWORD dwFlags, DWORD dwBytes); LPVOID HeapReAlloc(HANDLE hHeap, DWORD dwFlags, LPVOID lpMem, DWORD dwBytes); BOOL HeapFree(HANDLE hHeap, DWORD dwFlags, LPVOID lpMem); BOOL HeapDestroy(HANDLE hHeap);
Under CE, HeapCreate() basically acts as a statement that you plan to use a private, application specific heap. It doesn't reserve or commit any heap space, and the parameters, though consistent with the appearance of the Win32 version of the function, are actually ignored. However, as a matter of defensive programming, you should supply valid values for them.
The private heap grows itself transparently, by committing pages when HeapAlloc() allocation requests are made. A private heap needs to keep track of some status information to manage itself (as does any heap), and this space is located in the private heap's own memory. For this reason, the actual amount of space available for allocation is less than the total size of the private heap.
HeapAlloc(), HeapReAlloc(), and HeapFree() work in much the same way as the more familiar LocalAlloc() family: They allocate, reallocate, and free individual blocks, respectively. HeapDestroy() frees the pages committed to the private heap and returns them to the allocation pool, whether or not individual allocations within the heap have been freed with HeapFree().
Using the Local Heap
A lot of Win32 applications allocate memory exclusively from the local heap, using LocalAlloc(), LocalReAlloc, and LocalFree(). The local heap is created when your process is loaded. Because the local heap is created as part of the program start-up sequence, you can count on at least some memory being available there initially. It is by far the easiest memory allocation scheme to use, so choose it if it makes sense, given your application's memory allocation patterns.
PortingTip: The LocalAlloc() family of memory allocation APIs is easy to use. Choose this approach if it is compatible with your application's memory allocation needs.
If you read through your sources and find only the LocalAlloc() family of functions is used for memory allocation, chances are that you are in pretty good shape. There are a few things to bear in mind when porting code that allocates from the local heap:
- On CE, LocalAlloc() supports only the flags LMEM_FIXED, LPTR, and LMEM_ZEROINIT.
- Use the local heap to allocate moderate or small blocks, that have various and indeterminate life spans.
- LocalFree() returns space within your heap, but doesn't necessarily cause pages to be returned to the allocation pool.
The goal in using the local heap is to keep its size fairly consistent. Use other allocation methods for objects that would cause it to grow dramatically or to become fragmented.
Re-Engineering Temp Files
On the desktop, temporary files truly do provide a "one size fits all" kind of runtime data management strategy. Many document processing applications make use of temporary files to buffer data and to support undo/redo behaviors. It may seem tempting to stick with this approach, because it offers so many advantages and conveniences, and definitely provides a simpler programming model than concocting a variety of memory allocations schemes. The concept breaks down on CE, though. Using temporary files essentially doubles the size of your data at runtime, and this is a luxury we can ill afford.
If you use temp files, try the following CE approaches instead:
- Save document state information in compressed format in runtime data structures.
- Limit the scope of undo/redo behaviors.
- Frequently write changes back to the document, but as deltas at the end of the file.
Porting Tip: Temporary files are "memory hungry." Try to devise other, more compact state management strategies.
Stack-Based DataEverybody's favorite place to put data is the stack—and why not?—it is effortless. Under CE, if the following three things are true, a datum belongs on the stack, period.
- The datum only exists for the scope of the function in which it is declared.
- You know its exact size, and its fairly small.
- It is not a constant value.
By default, your program starts up with 1K of stack space committed with the potential to grow the stack to a maximum size of 58K. Obviously, this hard limit means that you don't want huge objects on the stack—trying to grow the stack beyond the maximum size will cause an immediate program (and possibly system) crash. On the other hand, the stack is probably the most efficiently used memory on the system—it's fragmentation proof.
In our next installment, we'll look at how to optimize a CE application's use of data segments.
About the Author
Nancy Nicolaisen is a software engineer who has designed and implemented highly modular Windows CE products that include features such as full remote diagnostics, CE-side data compression, dynamically constructed user interface, automatic screen size detection, and entry time data validation.
In addition to writing for Developer.com, she has written several books, including Making Win 32 Applications Mobile.