bmalloc: Pathological madvise churn on the free(malloc(x)) benchmark
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 28 Feb 2015 00:29:22 +0000 (00:29 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 28 Feb 2015 00:29:22 +0000 (00:29 +0000)
commitb0587e62b0b1c97f62f5429edd05a362ac86f581
treed5b5d0a583e1a3e74e4ac650cca7e11a8db12ad9
parenta2ef469624df8d3faeb8910aadd785904b9a5a53
bmalloc: Pathological madvise churn on the free(malloc(x)) benchmark
https://bugs.webkit.org/show_bug.cgi?id=142058

Reviewed by Andreas Kling.

The churn was caused by repeatedly splitting an object with physical
pages from an object without, and then merging them back together again.
The merge would conservatively forget that we had physical pages, forcing
a new call to madvise on the next allocation.

This patch more strictly segregates objects in the heap from objects in
the VM heap, with these changes:

(1) Objects in the heap are not allowed to merge with objects in the VM
heap, and vice versa -- since that would erase our precise knowledge of
which physical pages had been allocated.

(2) The VM heap is exclusively responsible for allocating and deallocating
physical pages.

(3) The heap free list must consider entries for objects that are in the
VM heap to be invalid, and vice versa. (This condition can arise
because the free list does not eagerly remove items.)

With these changes, we can know that any valid object in the heap's free
list already has physical pages, and does not need to call madvise.

Note that the VM heap -- as before -- might sometimes contain ranges
or pieces of ranges that have physical pages, since we allow splitting
of ranges at granularities smaller than the VM page size. These ranges
can eventually merge with ranges in the heap during scavenging.

* bmalloc.xcodeproj/project.pbxproj:

* bmalloc/BoundaryTag.h:
(bmalloc::BoundaryTag::owner):
(bmalloc::BoundaryTag::setOwner):
(bmalloc::BoundaryTag::initSentinel):
(bmalloc::BoundaryTag::hasPhysicalPages): Deleted.
(bmalloc::BoundaryTag::setHasPhysicalPages): Deleted. Replaced the concept
of "has physical pages" with a bit indicating which heap owns the large
object. This is a more precise concept, since the old bit was really a
Yes / Maybe bit.

* bmalloc/Deallocator.cpp:

* bmalloc/FreeList.cpp: Adopt
(bmalloc::FreeList::takeGreedy):
(bmalloc::FreeList::take):
(bmalloc::FreeList::removeInvalidAndDuplicateEntries):
* bmalloc/FreeList.h:
(bmalloc::FreeList::push): Added API for considering the owner when
deciding if a free list entry is valid.

* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap): Adopt new API.

(bmalloc::Heap::scavengeLargeRanges): Scavenge all ranges with no minimum,
since some ranges might be able to merge with ranges in the VM heap, and
they won't be allowed to until we scavenge them.

(bmalloc::Heap::allocateSmallPage):
(bmalloc::Heap::allocateMediumPage):
(bmalloc::Heap::allocateLarge): New VM heap API makes this function
simpler, since we always get back physical pages now.

* bmalloc/Heap.h:
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::end):
(bmalloc::LargeObject::owner):
(bmalloc::LargeObject::setOwner):
(bmalloc::LargeObject::isValidAndFree):
(bmalloc::LargeObject::merge): Do not merge objects across heaps since
that causes madvise churn.
(bmalloc::LargeObject::validateSelf):
(bmalloc::LargeObject::init):
(bmalloc::LargeObject::hasPhysicalPages): Deleted.
(bmalloc::LargeObject::setHasPhysicalPages): Deleted. Propogate the Owner API.

* bmalloc/Owner.h: Added.

* bmalloc/SegregatedFreeList.cpp:
(bmalloc::SegregatedFreeList::SegregatedFreeList):
(bmalloc::SegregatedFreeList::insert):
(bmalloc::SegregatedFreeList::takeGreedy):
(bmalloc::SegregatedFreeList::take):
* bmalloc/SegregatedFreeList.h: Propogate the owner API.

* bmalloc/VMAllocate.h:
(bmalloc::vmDeallocatePhysicalPagesSloppy):
(bmalloc::vmAllocatePhysicalPagesSloppy): Clarified these functions and
removed an edge case.

* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::VMHeap):
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateSmallPage):
(bmalloc::VMHeap::allocateMediumPage):
(bmalloc::VMHeap::allocateLargeObject):
(bmalloc::VMHeap::deallocateLargeObject): Be sure to give each object
a new chance to merge, since it might have been prohibited from merging
before by virtue of not being in the VM heap.

(bmalloc::VMHeap::allocateLargeRange): Deleted.
(bmalloc::VMHeap::deallocateLargeRange): Deleted.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@180797 268f45cc-cd09-0410-ab3c-d52691b4dbfc
15 files changed:
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/BoundaryTag.h
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/FreeList.cpp
Source/bmalloc/bmalloc/FreeList.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/LargeObject.h
Source/bmalloc/bmalloc/Owner.h [new file with mode: 0644]
Source/bmalloc/bmalloc/SegregatedFreeList.cpp
Source/bmalloc/bmalloc/SegregatedFreeList.h
Source/bmalloc/bmalloc/VMAllocate.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h