Re: Calculating Virtual Memory Fragmentation

Q: When does an allocation fail because of an fragmentation pattern
A: Ite depends of the kind of allocation.
For heap allocations greater then 0xFFFE * sizeof(HEAP_ENTRY),
the limiting fector is virtual-address space fragmentation, since those
allocations
get satisfied on the address space itself.
For heap allocations smaller then the number above,
the problem is more complex.
If the heap has the lookaside front-end, then a set of same-size
allocations interspreased with different size allocations can cause the
heap to be unable to coalesce free segments, causing inability to use the
space.
You can define this problem as internal fragmentation, and you can quantify
the fragmentation as (largest contiguous heap block) / (sum of bytes of free
blocks).
This pattern is partially mitigated by the Low-Frag Front-end, that
works by clustering same-size allocations in sub-segments.
One other problem is the double-up reallocation strategy alternated
by small-block-allocations. Thica can cause the half-size blocks to be
non coalesce-able, and, it can lead to internal fragmentation.
One other kind of heap fragmentation is caused by the inability to create
a new heap segment, and, this is normally
caused by address space fragmentation.
Heap segments are also limited (before Vista, at least) and they can run-out
in certain worst case allocation pattern.

In typical large heap-abuser applications, the maximum heap usage is about
1.3 to 1.7 Gig out of a 2 Gig address space.
Certain pathological cases may top-out at 0.7 Gig.

To calculate the largest available virtual-address,
you can use `!address -summary`, in KD.
For heap fragmentation, `!heap -s` and `!heap -stat -h <handle>`
are your friends.

You can google other posting I wrote in the past in
the debugger newsgroup for further details on the subject.

--
--
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


"ravenous_wolves" <ravenous.wolves@xxxxxxxxx> wrote in message
news:1169580200.444802.289590@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
When does an allocation fail because of an fragmentation pattern?
a.) There is no contiguous virtual memory space large enough for the
allocation request?
b.) There is no contiguous space within a heap large enough for the
allocation request?

Either? Which one is more likely to occur first in a typical,
frequent-allocation, poorly-designed, fragmentation-inducing system?

A highly fragmented heap can simply grow in terms of pages and service
allocation requests, right? In this case, if there's tons of physical
memory, allocation would eventually fail when the heap is huge and
there is no remaining either virtual or physical/pagefile space and
another page can't be added. Within the heap, memory load reported for
the application could remain constant as fragmentation increases and
corresponding ineffeciency and actual amount of memory being FUBAR'ed
by the application increases?

What formula/algorithm can I use to calculate largest free VM block and
fragmentation percentage given the data that VirtualQuery gives me.
Early in the application life I get 270 blocks, 50MB committed, 20MB
free, 10MB reserved. Since VirtualQuery returns the whole range of
pages with the same protection & state, is it enough to just look at
every free block and remember the biggest one? What would this report
of VM frag represent if the total VM usage is only 80MB, and thus there
are still 2048-80 = 1968MB of VM pages still available to pull in? Is
fragmentation simply the existence of free VM blocks in the VM space,
as in, they shouldn't be in there at all in a theoretically perfect
world? Does VM fragmentation not really matter until
VMCommit+VMFree+VMReserve gets close to 2GB (VM non-kernel address
space w/o the /3GB switch)?

Thanks for everything,
-ken

Skywing [MVP] wrote:
1. The entire region of pages returned has the same protection and state
attributes, so you can skip ahead the size of the region for the next
query.
2. The heap takes up 4k (or larger) regions and subdivides them into
smaller, more managable blocks. So even thought an entire heap segment
might be `committed` at the OS/VM-level, only the parts that the heap
manager has handed out to applications are truly `in-use.

BTW, check out the `!address -v' command in WinDbg; it has useful
facilities
for diagnosing address space consumption (including reservations vs
commits).

--
Ken Johnson (Skywing)
Windows SDK MVP
http://www.nynaeve.net
"ravenous_wolves" <ravenous.wolves@xxxxxxxxx> wrote in message
news:1169505296.539000.205210@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I'm seeing a problem in an long runtime application that I'm working
which which I believe to be virtual memory fragmentation. A change was
made which greatly increased the # of fast alloc/release cycles and the
system MTBF dropped significantly and the failure profile was unable to
allocate memory despite physical memory still being available.

SO, I'm trying to quantify this effect and give some type of # which
can report how fragmented the virtual address space of our process is.
I've used a MS tool (DebugDiag) which actually reports this, but MS is
unable to get this tool to work on our application (generating a dump
locks the OS).

I've got two ideas, but I'm stuck in terms of mapping my
programmer-level concept of virtual memory to the real low-level
implementation details of Windows.
1. Use VirtualQueryEx, and start at address 0x0 and work my way up to
0x80000000, and keep notes on the sizes of free blocks and the sizes of
committed blocks. One question is, if VirtualQueryEx returns and says a
"range of pages" from N to N + 2MB is committed, does that mean that a
2MB region is completely committed and 100% unfragmented, or does that
mean that the set of pages is all committed, and each page has it's own
fragmentation characteristics?

2. DebugDiag reports virtual memory fragmentation on a per-heap basis.
I understand how to enumerate all the heaps in my process with
GetProcessHeaps and HeapWalk. This seems right in terms of per-heap
fragmentation, but I don't understand virtual memory fragmentation to
be a per-heap concept, but rather a per-process concept. Furthermore,
the Region field of PROCESS_HEAP_ENTRY indicates that part of the block
is committed and part is uncommitted, which makes me confused as to
what is being enumerated.

Sorry if that doesn't make much sense, if anyone has some brief
guidance on what kind of API calls and calculation would need to be
done to quantify virtual memory fragmentation that would be great....

Thanks,
-ken




.

Relevant Pages

  • 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: HeapAlloc heap fragmentation.
    ... The problem is not simple heap fragmentation. ... > and allocation policy from Mm varies, but, that is normally in the order ... >>> VirtualAllocdBlocks @ c0090 ...
    (microsoft.public.win32.programmer.kernel)
  • 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: Whats the difference between the heap and the freestore?
    ... >> In general, when discussing dynamically allocated memory, I hear people ... As of a couple of days ago, I though the heap ... > When you use the term heap in the context of memory allocation it annoys ... > without saying that they have to be allocated on a stack or anything else. ...
    (comp.lang.cpp)