554191 - Fragmentation caused by Large Heap blocks not being correctly created and released

Status: VERIFIED FIXED

(Tamarin Graveyard :: Garbage Collection (mmGC), defect, P2)

Description

[Gavin]

User-Agent:       Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_2; en-us) AppleWebKit/531.22.7 (KHTML, like Gecko) Version/4.0.5 Safari/531.22.7
Build Identifier: 

Existing logic tries to allocate large blocks in their own region and then release that region as soon as they  are freed. But some flaws in this logic cause other blocks to be allocated in these regions so they cannot be released. When the blocks are then added to the free list, they quickly get fragmented and more memory is needed from the OS for future large block allocations. This leads to an unneeded demand on the host OS memory. The logic can be fixed by either allocating large blocks in a different way, or fixing the existing logic. Bugs I found were:
1) round up of block size causes extra free space to be allocated in top of region
2) block table expansion uses extra memory at bottom of region.
These two issues prevent the block from being allocated on its own and released.
Also, combinations of other blocks/regions can sometimes satisfy large block requests, but since those requests are not in their own region, they won't be released to the OS. It is probably better to always allocate large blocks (over a certain size) in their own region even if the heap could satisfy the request.

Reproducible: Always

Steps to Reproduce:
1. run countrysideBlur tests attached to watson 2578286
2. observe dela in memory usage
3. 
Actual Results:  
Large memory allocations stack up and remain long after referenced

Expected Results:  
Large memory block allocations released back to OS when no longer used

I have a patch for this that works for many cases. There are probably better ways to do this.

==== //depot/users/gpeacock/argo/code/third_party/avmplus/MMgc/GCHeap.cpp#7 - /Users/gpeacock/dev/argo/gpeacock/third_party/avmplus/MMgc/GCHeap.cpp ====
@@ -88,6 +88,9 @@
 #ifdef MMGC_MEMORY_PROFILER
 	MemoryProfiler* GCHeap::profiler = (MemoryProfiler*)-1;
 #endif
+	
+#define kLargeBlockThreshold 64 // any allocation larger than this should try to use its own region (move to header)
+	
 
 	GCHeapConfig::GCHeapConfig() : 
 		initialSize(512), 
@@ -997,7 +1000,7 @@
 				{
 					// if the block isn't committed see if this request can be met with by committing
 					// it and combining it with its neighbors
-					if(!block->committed && !decommittedSuitableBlock)
+					if(!block->committed && !decommittedSuitableBlock && size < kLargeBlockThreshold)
 					{
 						size_t totalSize = block->size;
 						
@@ -1458,7 +1461,8 @@
 		size_t commitAvail = 0;
 
 		// Round up to the nearest kMinHeapIncrement
-		size = roundUp(size, kMinHeapIncrement);
+		if (size < kLargeBlockThreshold)
+			size = roundUp(size, kMinHeapIncrement);
 
 		// when we allocate a new region the space needed for the HeapBlocks, if it won't fit 
 		// in existing space it must fit in new space so we may need to increase the new space
@@ -1475,6 +1479,19 @@
 			size_t curHeapBlocksSize = blocks ? AddrToBlock(blocks)->size : 0;
 			size_t newHeapBlocksSize = numHeapBlocksToNumBlocks(blocksLen + size + extraBlocks);
 
+#if 1		
+			if (newHeapBlocksSize > curHeapBlocksSize) 
+			{
+				bool zero = false;
+				HeapBlock *temp = AllocBlock(newHeapBlocksSize, zero);
+				if (temp) {
+					newBlocks = (HeapBlock*)temp->baseAddr;
+					numAlloc += newHeapBlocksSize;
+					curHeapBlocksSize = newHeapBlocksSize;
+				}
+			}
+#endif
+			// if we could not allocate blocks from the heap, make space in our new allocation for them
 			// size is based on newSize and vice versa, loop to settle (typically one loop, sometimes two)
 			while(newHeapBlocksSize > curHeapBlocksSize) 
 			{
@@ -1493,7 +1510,7 @@
 		if(config.useVirtualMemory)
 		{
 			Region *region = lastRegion;
-			if (region != NULL)
+			if (region != NULL  && size <= kLargeBlockThreshold)
 			{
 				commitAvail = (int)((region->reserveTop - region->commitTop) / kBlockSize);

Comment 1

[Tommy Reilly]

Attachment: potential fix, not fully tested/vetted

Comment 2

[Tommy Reilly]

The main issue with this patch is that it uses VMPI_size on memory returned from VMPI_allocateAlignedMemory which works on mac but isn't valid.  Need to introduce a VMPI_alignedMemorySize.

Comment 3

[Lars T Hansen]

(In reply to comment #2)
> The main issue with this patch is that it uses VMPI_size on memory returned
> from VMPI_allocateAlignedMemory which works on mac but isn't valid.  Need to
> introduce a VMPI_alignedMemorySize.

I don't know that you can have that, portably.

Comment 4

[Tommy Reilly]

IsAddressInHeap will need updating to, we might just have to burn a GCRegion for each large alloc in order to track size portably and handle IsAddressInHeap

Comment 5

[Tommy Reilly]

Attachment: cleaned up for review

Comment 6

[Lars T Hansen]

(Some early remarks, will examine again tomorrow.)

VMPI_allocateAlignedMemory does not guarantee zeroing yet this patch sets the zero flag to 'false' after calling it.

Indeed the documentation for VMPI_allocateAlignedMemory does not require the function to be implemented as anything than a stub, so that needs to be cleaned up too.

Looks like the change to FixedMalloc::LargeSize is an unrelated bug fix; ideally file separately.

I like what you've done to GCHeap::Alloc / AllocHelper but this too looks like mostly unrelated bug fixes (apart from the cutoff case of course).

VMPI_allocateAlignedMemory aligns to the system page size, not to GCHeap's block size necessarily, but I don't see that as a huge problem necessarily.  Still, are there consequences for accounting?

(BTW the documentation for VMPI_size is wrong, not the fault of this patch though.)

Why did you choose to use VMPI_allocateAlignedMemory instead of the VM primitives?  Poor API fit, ease of implementation?  I ask since the underlying implementation of VMPI_allocateAlignedMemory - which could just be a call to malloc with some rounding - may thwart our attempts at returning memory to the OS reliably.

Comment 7

[Tommy Reilly]

+1 on zeroing bug

FixedMalloc::LargeSize was calling size with ptr+8 in debug builds, which crashed the first version of this patch

> Why did you choose to use VMPI_allocateAlignedMemory instead of the VM primitives?  

Mostly API fix but I considered using VM API's directly but thought that if the host/browser/libc could meet this request let them try although on many systems ports VMPI_allocateAlignedMemory will go right to VM anyway and even valloc systems will usually forward large allocations to the OS.   My recollection is that other allocators work like ours, they always try to satisify a request with existing memory and only go to the OS when they have to.   

To me this bug isn't so much about returning memory to the OS as it is about the heap growing out of control due to fragmentation from large allocations.

Comment 8

[Brent Getlin]

A couple of comments on the patch:

(1)  FixedMalloc.cpp : LN 284. 
Isn't this change redundant since m_heap->Size() gets the size of the block and theoretically the "item" and the "realpointer" are always in the same block.

(2) Directly allocating the newRegion in LargeAlloc bypasses a ton of logic inside ExpandHeap.  One thing I know we need to do is perform the heaplimit lookaheads before doing this:

if ( (HardLimitExceeded(askSize) || SoftLimitExceeded(askSize)))
		{
			SendFreeMemorySignal(askSize);
		}

Are you sure we're not missing anything else here?  What about setting maxTotalHeapSize?

Comment 9

[Tommy Reilly]

The docs for GCHeap::Size don't say to can pass an interior pointer, correctness mandates a GetRealPointer call there.

Correct on the Region, we need to ensure a free region exists before calling NewRegion

Also the size stats need to be kept up to date, new patch coming.

Comment 10

[Tommy Reilly]

Attachment: v2: address Brent and Lar's feedback

-addressed zero issue
-updated GetTotalHeapSize and made sure max was updated
-made sure SendFreeMemoryCalls still happen
-made sure a free Region exists when we need it

Comment 11

[Brent Getlin]

I was hoping you'd choose NOT to have AllocHelper bypass the normal ExpandHeap logic rather than bring over bits of that logic over here.  It seems risky to pull this out, and I'm not sure what's gained?

On quick glance, here's something else important that was missed in this refactoring:

		if (HardLimitExceeded(asksize))
			return false;

Comment 12

[Tommy Reilly]

ExpandHeap is a private method only called from 3 places, ctor, AllocHelper and EnsureFreeRegion.    

The ctor shouldn't be subjected to heap limit checks, its really a bug that you can set the heap limits to below the initial heap size.

The AllocHelper is the main growth path and having all the checks here in one place is a good thing I think.

The ExpandHeap(1) call in EnsureFreeRegion is unfortunate but necessary with the current design and represents a rare edge case.    EnsureFreeRegion needs some re-thinking....

Okay I got it, when called from Decommit->RemoveBlock EnsureFreeRegion could call ExpandHeap and that would be bad (being in the guts of Decommit and letting the mutator operator at the same time probably has pitfalls).   Instead of doing that I think Decommit should call EnsureFreeRegion at the top of each loop and shouldn't ever ExpandHeap (ie terminate Decommit if we can't ensure a free region), this shouldn't happen as we know we have free memory or we wouldn't be Decommitting in the first place.   In the LargeAlloc case we should probably just call AllocHelper if we need a free region.    I'll post a new patch that cleans this up.

Comment 13

[Tommy Reilly]

Attachment: v3: clean up edges cases around EnsureFreeRegion

Updated to address concerns.   Not asking for reviews yet, need to dig into Gavin's crash report.

Comment 14

[Tommy Reilly]

patch doesn't update IsAddressInHeap

Comment 15

[Tommy Reilly]

Attachment: v4: fixes AddressInHeap and SafeSize

Comment 16

[Tommy Reilly]

Attachment: v5: fix assert w/ AddressInHeap calling SafeSize w/o prepping arg

Comment 17

[Tommy Reilly]

Attachment: v6: fix AddressInHeap for 64bit

Comment 18

[Tommy Reilly]

this is causing problems in 64 bit linux b/c VMPI_allocateAlignedMemory is giving us memory from low 32 bit addresses and mmap is giving us addresses from 0x7fxxxxxxxxxxxxxx so we need a 4 GB page map.    Will try switching from VMPI_allocateAlignedMemory to VMPI_reserveMemoryRegion/VMPI_commitMemory

Comment 19

[Tommy Reilly]

Attachment: v7: fix linux64 bit issues

Comment 20

[Tommy Reilly]

Attachment: what's new in v7 difff

Comment 21

[Lars T Hansen]

(In reply to comment #18)
> this is causing problems in 64 bit linux b/c VMPI_allocateAlignedMemory is
> giving us memory from low 32 bit addresses and mmap is giving us addresses from
> 0x7fxxxxxxxxxxxxxx so we need a 4 GB page map.    Will try switching from
> VMPI_allocateAlignedMemory to VMPI_reserveMemoryRegion/VMPI_commitMemory

General problem tracked in bug #445780.

Comment 22

[Lars T Hansen]

Style etc,

 - CheckForNewMaxTotalHeapSize() must be documented

 - CheckForNewMaxTotalHeapSize() in fact appears to do no such thing,
   elsewhere Check*() functions have side effects if their checks do
   not pass, but not so here.

 - EnsureFreeRegion() and HaveFreeRegion() must be documented, the current
   documentation is inadequate

 - Separate patch really ought to be created for drive-by fixes in
   FixedMalloc.cpp


Nits:

 - GCHeap::AllocHelper uses all four major brace styles - probably a new 
   record, it seems a shame to clean it up but it might be a good idea

Comment 23

[Lars T Hansen]

Comment on attachment 435988 [details] [diff] [review]
v7: fix linux64 bit issues

SR+ with reservations as outlined in previous comment, a follow-up patch addressing those issues would be appreciated.

Comment 24

[Tommy Reilly]

Attachment: one more tweak

Comment 25

[Tommy Reilly]

Attachment: v8 complete patch

Comment 26

[Tommy Reilly]

Attachment: v9: rebase to tip, LargeAlloc handles alignment now

Comment 27

[Tommy Reilly]

Attachment: v8/v9 change: just the new LargeAlloc w/ alignment code

Comment 28

[Tommy Reilly]

v7 was approved need sign off on v8 (attachment 2 [details] [diff] [review]) and v9 (attachment 4 [details] [diff] [review])

Comment 29

[Tommy Reilly]

make that attachment 436104 [details] [diff] [review] and attachment 436234 [details] [diff] [review]

Comment 30

[Lars T Hansen]

Comment on attachment 436234 [details] [diff] [review]
v8/v9 change: just the new LargeAlloc w/ alignment code

You can use (alignment - 1) * kBlockSize I think.

Comment 31

[Lars T Hansen]

Comment on attachment 436104 [details] [diff] [review]
one more tweak 

Credible.

Comment 32

[Tommy Reilly]

tamarin-redux-argo: 3900:aff79174812a
leaving open, needs some self tests

Comment 33

[Tommy Reilly]

selftest: http://hg.mozilla.org/tamarin-redux/rev/c5fe34afe5cb
tamarin-redux: http://hg.mozilla.org/tamarin-redux/rev/aff79174812a

Comment 34

[Brent Baker]

Selftest was added and is running, marking this bug as verified. There is however a separate bug that is tracking the selftest causing an OOM error on some platforms, bug #557212.

Comment 35

[Lars T Hansen]

NOTE, the v8/v9 diff does not contain all the changes in the v9 changeset, note the change of kDecommitThresholdPercentage which appears to be spurious, see WE 2607898.