Re: HeapAlloc heap fragmentation.

Let me try agian; I want you to understand not because I expect a solution
but because I want people at Microsoft to be aware of the problem because
until our customers upgrade to 64 bit computing they will suffer frequent
out of memoy errors that they do not understand. Just google "matlab out
memory" or search comp.softsys.matlab for the scale of the problem.

The problem is not one of fragmentation but one of not haveing any virtual
addres space avalible, even when there is a huge amount of space avalible in
the standard heap. .

Because address space only goes into the heap any applictaion that allocates
1-2gb of small objects, frees ALL of them and tries to allocate large
(>0x7f000) objects will fail due to out of memory. Worse yet, task manager
shows little memory use becase it shows private bytes and HeapFree has
de-commited the memory.

What is needed is a function to tell the heap to release unused virtual
addres space to make it avalible to VirtualAlloc. The only way I know of to
do this is to call HeapDestroy and it is difficult to guarentee that all
objects in a Heap will be freed so that doing this is posible.

The code I originaly posted shows this. Here is the main portion of the
code with more comments:

int _tmain(int argc, _TCHAR* argv[]){
size_t const SmallAlloc=0x7eff0;
size_t const BiggerAlloc=0x7fff0;

// prove can access and free large memory blocks this runs repeatedly
TestSmallBlocks(MaxPointers,BiggerAlloc);
TestLargeBlock(0x20000000); // 500 mb

/// Grow the heap HERE IS THE PROBLEM
TestSmallBlocks(MaxPointers,SmallAlloc);

// The heap now owns all virtual addres space an will not give it up.
// 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);
}


"Ivan Brugiolo [MSFT]" <Ivan.Brugiolo@xxxxxxxxxxxxxxxxxxxx> wrote in message
news:%23g293OJ5FHA.1000@xxxxxxxxxxxxxxxxxxxxxxx
> At this point, without the (very verbose) output of `!heap -p -all`
> and `!address` is very hard to say anything meaningful,
> besides correcting my initial understanding of the problem,
> and giving very generic recomendations.
> At this point is not even clear if you suffer of:
> - address space fragmentation
> - internal heap fragmentation
> - external heap fragmentation
>
> --
> 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:eDsGn2I5FHA.2816@xxxxxxxxxxxxxxxxxxxxxxx
>> 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: Huge pages and small pages. . .
    ... Since the CPU uses virtual memory always, ... them, you need to have them cached in the TLB; if the TLB runs out of room, you invalidate entries; then when you hit entries not in the TLB, the TLB has to searhc for the page mapping in the PTE chain. ... When you allocate memory, the kernel just marks a promised ... They will stay forever allocated until the highest pages of the heap are unused by the program, in which case the heap manager brks down the heap and frees them to the system. ...
    (Linux-Kernel)
  • Heap fragmentation (2nd attempt)
    ... But this heap does not fragment, ant the time to allocate memory does not ...
    (comp.arch.embedded)
  • Re: How to release heap memory that is marked as free
    ... fragmentation and you don't control the code then you can do little ... You could use a memory mapped file to ... I removed the heap walker calls and put in a heapstat function ... using, but I don't have much control over ZipArchive, and I have ...
    (microsoft.public.vc.mfc)
  • Re: Heap fragmentation
    ... in University I learnt about heap fragmentation, ... What I do is allocate 500 000 chunks of memory all randomly sized between ... Chances are good that the same memory us used each time. ...
    (comp.realtime)
  • Re: Huge pages and small pages. . .
    ... >> what looks like contiguous memory and away you go. ... you need to have them cached in the TLB; if the TLB runs out of ... > low end of the heap, until someone figures out a way to tell the system ... When you allocate memory, the kernel just marks a promised ...
    (Linux-Kernel)
Quantcast