Re: HeapAlloc heap fragmentation.

The problem is not simple heap fragmentation. The LowFragHeap does not
help. The main issue is that we end up with nearly all virtual memory
(nearly 2gb) reserved in the Heap making it impossible to allocate any
blocks of size > 0x7f000 even when the heap itself has plenty of free space
including blocks of memory larger then 0x7f000 bytes that it will not
allocate from because of the block size limit.

We have implemented our own small block heap quite similar to the Low
Fragmentation Heap that helps to reduce fragmentation but is not the issue
here.


"Ivan Brugiolo [MSFT]" <Ivan.Brugiolo@xxxxxxxxxxxxxxxxxxxx> wrote in message
news:umNprmI5FHA.724@xxxxxxxxxxxxxxxxxxxxxxx
>I got wrong the the comparison term.
> Sorry about that.
> In that case, the behavior is expected, with the following caveats:
> Blocks below that threashold are allocated out of a heap-segment,
> that is a contiguous address space region whose size
> and allocation policy from Mm varies, but, that is normally in the order
> of several Megabytes.
> Smaller blocks are returned to the free-pool within the segment,
> but, the address space is reserved in a whole block,
> and committed on demand.
>
> There are a couple of techniques to prevent fragmentation:
> - Use LowFragHeap
> - Disable the LookAside Frontend, that, as a side effect,
> improves the ability to coalesce.
>
> Allocation patterns that tend to exacerbate fragmentation are:
> - std::vector::push_back() growing strategy (and other hash-tables
> that grows in the same patter)
> - mismatched order of allocations and free, with regard location
> in the address space.
>
> side-notes:
> HeapCompact does not do what most think it will do.
> HeapValidate, as a side effect,
> will do what most think HeapCompact is supposed to do.
>
> --
> This posting is provided "AS IS" with no warranties, and confers no
> rights.
> Use of any included script samples are subject to the terms specified at
> http://www.microsoft.com/info/cpyright.htm
>
> "Philip Borghesani" <PhilBorg@xxxxxxxxxxxxxxxx> wrote in message
> news:OImKKhH5FHA.3388@xxxxxxxxxxxxxxxxxxxxxxx
>>I think you missed the point. You allocated blocks of size 0x7FFF0 which
>>were allocated individually using VirtualAlloc by HeapAlloc and are
>>completely released by HeapFree. The problem is with blocks that are
>>smaller then 7F000 bytes which are allocated directly from the heap and
>>cause it to grow. After the heap has grown it never releases virtual
>>address space preventing large allocations.
>>
>> Output from a run of the code I posted:
>> S:\test\TestHeapAlloc> release\TestHeapAlloc.exe
>> // first run successfully allocates a large number of large blocks
>> Allocation 3628 failed
>> Allocated 3628 items of size 524280 for a total of 1902087840 bytes
>> Allocated 536870912 bytes // after freeing can still allocate a single
>> large block
>>
>>
>> // now allocate a slightly smaller size any size less then some cutoff
>> would do but more allocations would be needed
>> Allocation 4108 failed
>> Allocated 4108 items of size 516280 for a total of 2120878240 bytes
>>
>> // note return from HeapCompact
>> HeapCompact erroneously reports a large max block size of 536866816
>>
>> // now we can not allocate anything larger then 0x7FFF0 bytes
>> Failed to allocate 268433408 bytes
>> Allocation 0 failed
>> Allocated 0 items of size 524280 for a total of 0 bytes
>>
>>
>>
>> "Ivan Brugiolo [MSFT]" <Ivan.Brugiolo@xxxxxxxxxxxxxxxxxxxx> wrote in
>> message news:eIO1jSD5FHA.2636@xxxxxxxxxxxxxxxxxxxxxxx
>>> This is contrary to evidence and implementation (see code and debugger
>>> evidence)
>>> What are you using to conclude that blocks are never released ?
>>>
>>> Given the following fragment:
>>>
>>> #define MAX_ALLOC 256
>>> #define HEAP_GRANULARITY (2*sizeof(ULONG_PTR))
>>> #define HEAP_ENTRY_MAX 0xFFFE
>>>
>>> int __cdecl
>>> wmain(int argc, WCHAR * argv[])
>>> /*++
>>>
>>> --*/
>>> {
>>>
>>> PVOID Array[MAX_ALLOC];
>>>
>>> for (ULONG Iter = 0; Iter < MAX_ALLOC; Iter++){
>>> Array[Iter] = HeapAlloc(GetProcessHeap(),0,HEAP_GRANULARITY *
>>> HEAP_ENTRY_MAX) ;
>>> }
>>>
>>> DbgBreakPoint();
>>>
>>> for (ULONG Iter = 0; Iter < MAX_ALLOC; Iter++){
>>> HeapFree(GetProcessHeap(),0,Array[Iter]) ;
>>> }
>>>
>>> DbgBreakPoint();
>>>
>>> return 0;
>>> }
>>>
>>>
>>> At the first breakpoint:
>>>
>>> 0:000> !heap -p -all
>>> _HEAP @ c0000
>>> _HEAP_LOOKASIDE @ c0cd0
>>> _HEAP_SEGMENT @ c0c50
>>> CommittedRange @ c0cc0
>>> HEAP_ENTRY: Size : Prev Flags - UserPtr UserSize - state
>>> // snip
>>> VirtualAllocdBlocks @ c0090
>>> 2b0030: fffe : N/A [N/A] - 2b0040 (fffe0) - (busy VirtualAlloc)
>>> // other 255 blocks similar to the previous one
>>>
>>> At the second breakpoint
>>>
>>> 0:000> !heap -p -all
>>> _HEAP @ c0000
>>> _HEAP_LOOKASIDE @ c0cd0
>>> _HEAP_SEGMENT @ c0c50
>>> CommittedRange @ c0cc0
>>> HEAP_ENTRY: Size : Prev Flags - UserPtr UserSize - state
>>> // snip
>>> VirtualAllocdBlocks @ c0090
>>> // no blocks, meaning they have been free-ed
>>>
>>> --
>>> This posting is provided "AS IS" with no warranties, and confers no
>>> rights.
>>> Use of any included script samples are subject to the terms specified at
>>> http://www.microsoft.com/info/cpyright.htm
>>>
>>>
>>> "Philip Borghesani" <PhilBorg@xxxxxxxxxxxxxxxx> wrote in message
>>> news:eoMCG9%234FHA.1184@xxxxxxxxxxxxxxxxxxxxxxx
>>>> Our application has bumped into what seems to be a limitation of the
>>>> HeapAlloc system on Win32.
>>>>
>>>>
>>>>
>>>> It appears that if an application allocate a large portion of the
>>>> available address space in object of size less then 0x7FFF8 bytes and
>>>> then releases this memory there is no way to reclaim the address space
>>>> for allocations of size greater then 7FFF8 bytes.
>>>>
>>>>
>>>>
>>>> Using the low fragmentation heap does not seem to help.
>>>>
>>>>
>>>>
>>>> Are there any known work a-rounds for this issue other then replacing
>>>> HeapAlloc (actually standard c++ allocators in Visual C 7)?
>>>>
>>>>
>>>>
>>>> Example code:
>>>>
>>>>
>>>>
>>>> // TestHeapAlloc.cpp This program will cause a machine with less then
>>>> 2gb ram to thrash badly
>>>>
>>>> // do no run with less then 1gb ram.
>>>>
>>>> // if this program is run on a machine with the -3gb boot switch
>>>> (or win64) then the sizes
>>>>
>>>> // may need to be modified to produce a failure
>>>>
>>>>
>>>>
>>>> #include "stdafx.h"
>>>>
>>>> #include "windows.h"
>>>>
>>>>
>>>>
>>>> HANDLE heap=NULL;
>>>>
>>>>
>>>>
>>>> void TestLargeBlock(size_t size)
>>>>
>>>> {
>>>>
>>>> void *ptr=HeapAlloc(heap,0,size); // 500 mb
>>>>
>>>> if (ptr!=NULL) {
>>>>
>>>> printf("Allocated %Id bytes\n",HeapSize(heap,0,ptr));
>>>>
>>>> } else {
>>>>
>>>> printf("Failed to allocate %Id bytes\n",size);
>>>>
>>>> }
>>>>
>>>> HeapFree(heap,0,ptr);
>>>>
>>>> }
>>>>
>>>>
>>>>
>>>> size_t const MaxPointers=10000;
>>>>
>>>>
>>>>
>>>> void TestSmallBlocks(int NumPointers,size_t size)
>>>>
>>>> {
>>>>
>>>> void *pointers[MaxPointers];
>>>>
>>>> int count=0;
>>>>
>>>> memset(pointers,0,sizeof(pointers));
>>>>
>>>> for (int i=0; i< NumPointers; i++)
>>>>
>>>> {
>>>>
>>>> pointers[i]=HeapAlloc(heap,0,size);
>>>>
>>>> if (pointers[i]==NULL) {
>>>>
>>>> break;
>>>>
>>>> } else {
>>>>
>>>> count++;
>>>>
>>>> }
>>>>
>>>> }
>>>>
>>>> printf("Allocated %d items of size %Id for a total of %Iu
>>>> bytes\n",count,size,count*size);
>>>>
>>>> // now free the memory
>>>>
>>>> for (int i=0; i< count; i++)
>>>>
>>>> {
>>>>
>>>> HeapFree(heap,0,pointers[i]);
>>>>
>>>> }
>>>>
>>>> }
>>>>
>>>>
>>>>
>>>> int _tmain(int argc, _TCHAR* argv[])
>>>>
>>>> {
>>>>
>>>> heap=GetProcessHeap(); // initialize program global heap
>>>>
>>>> size_t const AllocCutoff=0x7FFF8;
>>>>
>>>> size_t const SmallAlloc=AllocCutoff-8000;
>>>>
>>>> size_t const BiggerAlloc=AllocCutoff;
>>>>
>>>>
>>>>
>>>> // prove can access and free large memory blocks
>>>>
>>>> TestSmallBlocks(MaxPointers,BiggerAlloc);
>>>>
>>>> TestLargeBlock(0x20000000); // 500 mb
>>>>
>>>>
>>>>
>>>> /// Grow the heap
>>>>
>>>> TestSmallBlocks(MaxPointers,SmallAlloc);
>>>>
>>>>
>>>>
>>>> // check heap info
>>>>
>>>>
>>>>
>>>> size_t maxblock=HeapCompact(heap,0);
>>>>
>>>> printf("HeapCompact erroneously reports a large max block size of
>>>> %Id\n",maxblock);
>>>>
>>>>
>>>>
>>>> // try to allocate a large block
>>>>
>>>>
>>>>
>>>> TestLargeBlock(maxblock/2); // can't even allocate ½ reported size
>>>>
>>>>
>>>>
>>>> // try to allocate slightly bigger small blocks this is the most
>>>> painful example
>>>>
>>>> // possibly not even one allocation will happen
>>>>
>>>> TestSmallBlocks(MaxPointers,BiggerAlloc);
>>>>
>>>> }
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>


.

Relevant Pages

  • Re: Calculating Virtual Memory Fragmentation
    ... When does an allocation fail because of an fragmentation pattern ... Ite depends of the kind of allocation. ... For heap allocations greater then 0xFFFE * sizeof, ... To calculate the largest available virtual-address, ...
    (microsoft.public.win32.programmer.kernel)
  • Re: stackalloc vs. new byte?
    ... Even though using the stack prevents fragmentation, it doesn't necessarily get around other memory space limitations. ... In particular, either the stack has a fixed limit in size, in which case putting large things on it isn't a good idea, or the stack has a dynamic limit in size, affected by what else is in the virtual address space in your process. ... In this latter case, allocations in the heap and especially fragmentation in the heap, can still easily affect how large your stack can get. ... Now, let's assume that having failed the allocation, you have the ability to go through and do some cleanup. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Memory problems (possibly very easy question)
    ... allocation pattern including those from deep inside Windows itself? ... I've spent days tracking down fragmentation problems. ... could be user interactions in between (e.g., the message pump). ... You have to actually examine the heap in detail to tell. ...
    (microsoft.public.vc.mfc)
  • Re: HeapAlloc heap fragmentation.
    ... - address space fragmentation ... - internal heap fragmentation ... >> and allocation policy from Mm varies, but, that is normally in the order ... >> will do what most think HeapCompact is supposed to do. ...
    (microsoft.public.win32.programmer.kernel)
  • Re: HeapAlloc heap fragmentation.
    ... Allocation patterns that tend to exacerbate fragmentation are: ... HeapCompact does not do what most think it will do. ... >> VirtualAllocdBlocks @ c0090 ...
    (microsoft.public.win32.programmer.kernel)
Loading