bmalloc: Unify VMHeap and Heap LargeObjects free lists to reduce fragmentation
authormsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 19 Feb 2016 23:27:40 +0000 (23:27 +0000)
committermsaboff@apple.com <msaboff@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 19 Feb 2016 23:27:40 +0000 (23:27 +0000)
https://bugs.webkit.org/show_bug.cgi?id=154192

Reviewed by Geoffrey Garen.

Change the operation of Heap and VMHeap LargeObject free lists.
Renamed Owner to VMState to track the state of each LargeObject.
    Physical - The pages have been allocated.
    Virtual - The pages have not been allocated.
    Mixed - The object contains a mixture of Physical and Virtual pages.
VMState uses one bit each for Physical and Virtual to simplify merging states
when merging two adjacent blocks.  This change enforces the rule that objects in
the Heap free list must have have the Physical bit set in their VMState while objects
in the VMHeap free list must have the Physical bit clear.  Thie means that the Heap
can have LargeObjects in Physical or Mixed VMState, but the VMHeap's free list can
only contain Virtual LargeObjects.

In both Heap::allocateLarge(), we now allocate physical pages if the LargeObject we
pull from the free list has any Virtual pages before we possilby split the
object.  When we merge objects, the result might be made up of Mixed page allocations.
When allocating a Mixed LargeObject, we need to allocate memory for them as well.
The scavenger deallocates both Physical and Mixed LargeObjects, placing them back into
the VMHeap's free list.

When we allocate or deallocate Mixed LargeObjects, there are pages that within these
objects that will be redundantly modified.  It would require additional metadata to
eliminate this redundancy.

* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/BoundaryTag.h:
(bmalloc::BoundaryTag::vmState): New helper.
(bmalloc::BoundaryTag::setVMState): New helper.
(bmalloc::BoundaryTag::owner): Deleted.
(bmalloc::BoundaryTag::setOwner): Deleted.
* bmalloc/Heap.h:
(bmalloc::Heap::splitAndAllocate): New helpers.
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::vmState): New helper.
(bmalloc::LargeObject::setVMState): New helper.

* bmalloc/Heap.cpp:
(bmalloc::Heap::splitAndAllocate): New helpers.
(bmalloc::Heap::allocateLarge):
(bmalloc::Heap::deallocatePhysicalPages): Refactored from VMHeap::deallocateLargeObjectMemory.

* bmalloc/FreeList.cpp:
(bmalloc::FreeList::takeGreedy):
(bmalloc::FreeList::take):
(bmalloc::FreeList::removeInvalidAndDuplicateEntries):
* bmalloc/FreeList.h:
(bmalloc::FreeList::FreeList):
(bmalloc::FreeList::push):
* bmalloc/Heap.cpp:
(bmalloc::Heap::Heap):
(bmalloc::Heap::scavengeLargeObjects):
* bmalloc/LargeObject.h:
(bmalloc::LargeObject::isValidAndFree):
(bmalloc::LargeObject::validateSelf):
* bmalloc/SegregatedFreeList.cpp:
(bmalloc::SegregatedFreeList::SegregatedFreeList): Changed to initialize our required Physical state.
* bmalloc/SegregatedFreeList.h:
(bmalloc::SegregatedFreeList::SegregatedFreeList):
(bmalloc::SegregatedFreeList::insert):
(bmalloc::SegregatedFreeList::takeGreedy):
(bmalloc::SegregatedFreeList::take):
Replaced Owner parameters and checks with VMState::HasPhysical.

* bmalloc/LargeObject.h:
(bmalloc::LargeObject::prevCanMerge): Removed owner from tests.
(bmalloc::LargeObject::nextCanMerge): Removed owner from tests.
(bmalloc::LargeObject::merge): Removed owner from tests.  Updated to merge VMStates andset the
VMState after the merge.

* bmalloc/LargeObject.h:
(bmalloc::LargeObject::owner): Deleted.
(bmalloc::LargeObject::setOwner): Deleted.

* bmalloc/Owner.h: Removed.

* bmalloc/VMAllocate.h:
(bmalloc::vmAllocatePhysicalPagesSloppy): Changed to round begin down to eliminate the left to right
allocation constraint.

* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::grow): Large space managed like small or medium as a vector of LargeChunks.
(bmalloc::VMHeap::VMHeap): Changed to initialize our required Physical state.

* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateLargeObject): These no longer allocate memory.
(bmalloc::VMHeap::deallocateLargeObject): Removed setOwner.  Now we set the VMState after any merges.

* bmalloc/VMState.h: Copied from Source/bmalloc/bmalloc/Owner.h.
(bmalloc::VMState::VMState):
(bmalloc::VMState::hasPhysical):
(bmalloc::VMState::hasVirtual):
(bmalloc::VMState::merge):
(bmalloc::VMState::operator ==):
(bmalloc::VMState::operator unsigned):
New class with various helpers.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@196840 268f45cc-cd09-0410-ab3c-d52691b4dbfc

14 files changed:
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/BoundaryTag.h
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/SegregatedFreeList.cpp
Source/bmalloc/bmalloc/SegregatedFreeList.h
Source/bmalloc/bmalloc/VMAllocate.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h
Source/bmalloc/bmalloc/VMState.h [moved from Source/bmalloc/bmalloc/Owner.h with 57% similarity]

index 44419cc..5cc351c 100644 (file)
@@ -1,3 +1,105 @@
+2016-02-19  Michael Saboff  <msaboff@apple.com>
+
+        bmalloc: Unify VMHeap and Heap LargeObjects free lists to reduce fragmentation
+        https://bugs.webkit.org/show_bug.cgi?id=154192
+
+        Reviewed by Geoffrey Garen.
+
+        Change the operation of Heap and VMHeap LargeObject free lists.
+        Renamed Owner to VMState to track the state of each LargeObject.
+            Physical - The pages have been allocated.
+            Virtual - The pages have not been allocated.
+            Mixed - The object contains a mixture of Physical and Virtual pages.
+        VMState uses one bit each for Physical and Virtual to simplify merging states
+        when merging two adjacent blocks.  This change enforces the rule that objects in
+        the Heap free list must have have the Physical bit set in their VMState while objects
+        in the VMHeap free list must have the Physical bit clear.  Thie means that the Heap
+        can have LargeObjects in Physical or Mixed VMState, but the VMHeap's free list can
+        only contain Virtual LargeObjects.
+        
+        In both Heap::allocateLarge(), we now allocate physical pages if the LargeObject we
+        pull from the free list has any Virtual pages before we possilby split the 
+        object.  When we merge objects, the result might be made up of Mixed page allocations.
+        When allocating a Mixed LargeObject, we need to allocate memory for them as well.
+        The scavenger deallocates both Physical and Mixed LargeObjects, placing them back into
+        the VMHeap's free list.
+
+        When we allocate or deallocate Mixed LargeObjects, there are pages that within these
+        objects that will be redundantly modified.  It would require additional metadata to
+        eliminate this redundancy.
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/BoundaryTag.h:
+        (bmalloc::BoundaryTag::vmState): New helper.
+        (bmalloc::BoundaryTag::setVMState): New helper.
+        (bmalloc::BoundaryTag::owner): Deleted.
+        (bmalloc::BoundaryTag::setOwner): Deleted.
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::splitAndAllocate): New helpers.
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::vmState): New helper.
+        (bmalloc::LargeObject::setVMState): New helper.
+
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::splitAndAllocate): New helpers.
+        (bmalloc::Heap::allocateLarge): 
+        (bmalloc::Heap::deallocatePhysicalPages): Refactored from VMHeap::deallocateLargeObjectMemory.
+
+        * bmalloc/FreeList.cpp:
+        (bmalloc::FreeList::takeGreedy):
+        (bmalloc::FreeList::take):
+        (bmalloc::FreeList::removeInvalidAndDuplicateEntries):
+        * bmalloc/FreeList.h:
+        (bmalloc::FreeList::FreeList):
+        (bmalloc::FreeList::push):
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::Heap):
+        (bmalloc::Heap::scavengeLargeObjects):
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::isValidAndFree):
+        (bmalloc::LargeObject::validateSelf):
+        * bmalloc/SegregatedFreeList.cpp:
+        (bmalloc::SegregatedFreeList::SegregatedFreeList): Changed to initialize our required Physical state.
+        * bmalloc/SegregatedFreeList.h:
+        (bmalloc::SegregatedFreeList::SegregatedFreeList):
+        (bmalloc::SegregatedFreeList::insert):
+        (bmalloc::SegregatedFreeList::takeGreedy):
+        (bmalloc::SegregatedFreeList::take):
+        Replaced Owner parameters and checks with VMState::HasPhysical.
+
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::prevCanMerge): Removed owner from tests.
+        (bmalloc::LargeObject::nextCanMerge): Removed owner from tests.
+        (bmalloc::LargeObject::merge): Removed owner from tests.  Updated to merge VMStates andset the
+        VMState after the merge.
+
+        * bmalloc/LargeObject.h:
+        (bmalloc::LargeObject::owner): Deleted.
+        (bmalloc::LargeObject::setOwner): Deleted.
+
+        * bmalloc/Owner.h: Removed.
+
+        * bmalloc/VMAllocate.h:
+        (bmalloc::vmAllocatePhysicalPagesSloppy): Changed to round begin down to eliminate the left to right
+        allocation constraint.
+
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::grow): Large space managed like small or medium as a vector of LargeChunks.
+        (bmalloc::VMHeap::VMHeap): Changed to initialize our required Physical state.
+
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateLargeObject): These no longer allocate memory.
+        (bmalloc::VMHeap::deallocateLargeObject): Removed setOwner.  Now we set the VMState after any merges.
+
+        * bmalloc/VMState.h: Copied from Source/bmalloc/bmalloc/Owner.h.
+        (bmalloc::VMState::VMState):
+        (bmalloc::VMState::hasPhysical):
+        (bmalloc::VMState::hasVirtual):
+        (bmalloc::VMState::merge):
+        (bmalloc::VMState::operator ==):
+        (bmalloc::VMState::operator unsigned):
+        New class with various helpers.
+
 2016-02-12  Michael Saboff  <msaboff@apple.com>
 
         BASSERTs added in r196421 are causing debug test failures
index d9fc506..3574186 100644 (file)
@@ -26,7 +26,7 @@
                14C6216F1A9A9A6200E72293 /* LargeObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C6216E1A9A9A6200E72293 /* LargeObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C919C818FCC59F0028DB43 /* BPlatform.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14CC394C18EA8858004AFE34 /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14F271BE18EA3963008C152F /* libbmalloc.a */; };
-               14D2CD9B1AA12CFB00770440 /* Owner.h in Headers */ = {isa = PBXBuildFile; fileRef = 14D2CD9A1AA12CFB00770440 /* Owner.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */ = {isa = PBXBuildFile; fileRef = 14D2CD9A1AA12CFB00770440 /* VMState.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD788C18F48CAE00950702 /* LargeChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA8818CD17CE002201E4 /* LargeChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD788D18F48CC600950702 /* BeginTag.h in Headers */ = {isa = PBXBuildFile; fileRef = 1417F64518B54A700076FA3F /* BeginTag.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */ = {isa = PBXBuildFile; fileRef = 1485655E18A43AF900ED6942 /* BoundaryTag.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14C6216E1A9A9A6200E72293 /* LargeObject.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = LargeObject.h; path = bmalloc/LargeObject.h; sourceTree = "<group>"; };
                14C919C818FCC59F0028DB43 /* BPlatform.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BPlatform.h; path = bmalloc/BPlatform.h; sourceTree = "<group>"; };
                14CC394418EA8743004AFE34 /* libmbmalloc.dylib */ = {isa = PBXFileReference; explicitFileType = "compiled.mach-o.dylib"; includeInIndex = 0; path = libmbmalloc.dylib; sourceTree = BUILT_PRODUCTS_DIR; };
-               14D2CD9A1AA12CFB00770440 /* Owner.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Owner.h; path = bmalloc/Owner.h; sourceTree = "<group>"; };
+               14D2CD9A1AA12CFB00770440 /* VMState.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = VMState.h; path = bmalloc/VMState.h; sourceTree = "<group>"; };
                14D9DB4517F2447100EAAB79 /* FixedVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = FixedVector.h; path = bmalloc/FixedVector.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                14DA32071885F9E6007269E0 /* Line.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = Line.h; path = bmalloc/Line.h; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.objcpp; };
                14DA320C18875B09007269E0 /* Heap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Heap.h; path = bmalloc/Heap.h; sourceTree = "<group>"; };
                                143EF9AE1A9FABF6004F5C77 /* FreeList.h */,
                                147AAA8818CD17CE002201E4 /* LargeChunk.h */,
                                14C6216E1A9A9A6200E72293 /* LargeObject.h */,
-                               14D2CD9A1AA12CFB00770440 /* Owner.h */,
                                146BEE2118C845AE0002D5A2 /* SegregatedFreeList.cpp */,
                                146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */,
+                               14D2CD9A1AA12CFB00770440 /* VMState.h */,
                        );
                        name = "heap: large | xlarge";
                        sourceTree = "<group>";
                                14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
                                14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
                                14DD78B718F48D6B00950702 /* MediumLine.h in Headers */,
-                               14D2CD9B1AA12CFB00770440 /* Owner.h in Headers */,
+                               14D2CD9B1AA12CFB00770440 /* VMState.h in Headers */,
                                14DD78B618F48D6B00950702 /* MediumChunk.h in Headers */,
                                14DD78BC18F48D6B00950702 /* SmallLine.h in Headers */,
                                14DD789818F48D4A00950702 /* Allocator.h in Headers */,
index 2fcc5a4..6c1b4a7 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,9 +27,9 @@
 #define BoundaryTag_h
 
 #include "BAssert.h"
-#include "Owner.h"
 #include "Range.h"
 #include "Sizes.h"
+#include "VMState.h"
 #include <cstring>
 
 namespace bmalloc {
@@ -50,9 +50,9 @@ public:
     bool isEnd() { return m_isEnd; }
     void setEnd(bool isEnd) { m_isEnd = isEnd; }
 
-    Owner owner() { return static_cast<Owner>(m_owner); }
-    void setOwner(Owner owner) { m_owner = static_cast<unsigned>(owner); }
-    
+    VMState vmState() { return VMState(m_vmState); }
+    void setVMState(VMState vmState) { m_vmState = static_cast<unsigned>(vmState); }
+
     bool isMarked() { return m_isMarked; }
     void setMarked(bool isMarked) { m_isMarked = isMarked; }
 
@@ -71,7 +71,7 @@ public:
     BeginTag* next();
 
 private:
-    static const size_t flagBits = 4;
+    static const size_t flagBits = 5;
     static const size_t compactBeginBits = 4;
     static const size_t sizeBits = bitCount<unsigned>() - flagBits - compactBeginBits;
 
@@ -85,7 +85,7 @@ private:
 
     bool m_isFree: 1;
     bool m_isEnd: 1;
-    unsigned m_owner: 1;
+    unsigned m_vmState: 2;
     bool m_isMarked: 1;
     unsigned m_compactBegin: compactBeginBits;
     unsigned m_size: sizeBits;
@@ -122,7 +122,7 @@ inline void BoundaryTag::initSentinel()
 {
     setRange(Range(nullptr, largeMin));
     setFree(false);
-    setOwner(Owner::VMHeap);
+    setVMState(VMState::Virtual);
 }
 
 } // namespace bmalloc
index 5fbb6bc..d6094fe 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -37,11 +37,11 @@ namespace bmalloc {
 // invalid entries as we discover them during allocation, and we also garbage
 // collect the free list as it grows.
 
-LargeObject FreeList::takeGreedy(Owner owner)
+LargeObject FreeList::takeGreedy(VMState::HasPhysical hasPhysical)
 {
     for (size_t i = 0; i < m_vector.size(); ++i) {
         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
-        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
+        if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
             m_vector.pop(i--);
             continue;
         }
@@ -53,14 +53,14 @@ LargeObject FreeList::takeGreedy(Owner owner)
     return LargeObject();
 }
 
-LargeObject FreeList::take(Owner owner, size_t size)
+LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t size)
 {
     LargeObject candidate;
     size_t candidateIndex;
     size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
     for (size_t i = begin; i < m_vector.size(); ++i) {
         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
-        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
+        if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
             m_vector.pop(i--);
             continue;
         }
@@ -80,7 +80,7 @@ LargeObject FreeList::take(Owner owner, size_t size)
     return candidate;
 }
 
-LargeObject FreeList::take(Owner owner, size_t alignment, size_t size, size_t unalignedSize)
+LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t alignment, size_t size, size_t unalignedSize)
 {
     BASSERT(isPowerOfTwo(alignment));
     size_t alignmentMask = alignment - 1;
@@ -90,7 +90,7 @@ LargeObject FreeList::take(Owner owner, size_t alignment, size_t size, size_t un
     size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
     for (size_t i = begin; i < m_vector.size(); ++i) {
         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
-        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
+        if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
             m_vector.pop(i--);
             continue;
         }
@@ -113,11 +113,11 @@ LargeObject FreeList::take(Owner owner, size_t alignment, size_t size, size_t un
     return candidate;
 }
 
-void FreeList::removeInvalidAndDuplicateEntries(Owner owner)
+void FreeList::removeInvalidAndDuplicateEntries(VMState::HasPhysical hasPhysical)
 {
     for (size_t i = 0; i < m_vector.size(); ++i) {
         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
-        if (!largeObject.isValidAndFree(owner, m_vector[i].size())) {
+        if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
             m_vector.pop(i--);
             continue;
         }
index 742d544..0929f14 100644 (file)
@@ -37,15 +37,15 @@ class FreeList {
 public:
     FreeList();
 
-    void push(Owner, const LargeObject&);
+    void push(VMState::HasPhysical, const LargeObject&);
 
-    LargeObject take(Owner, size_t);
-    LargeObject take(Owner, size_t alignment, size_t, size_t unalignedSize);
-    
-    LargeObject takeGreedy(Owner);
+    LargeObject take(VMState::HasPhysical, size_t);
+    LargeObject take(VMState::HasPhysical, size_t alignment, size_t, size_t unalignedSize);
+
+    LargeObject takeGreedy(VMState::HasPhysical);
+
+    void removeInvalidAndDuplicateEntries(VMState::HasPhysical);
 
-    void removeInvalidAndDuplicateEntries(Owner);
-    
 private:
     Vector<Range> m_vector;
     size_t m_limit;
@@ -57,13 +57,14 @@ inline FreeList::FreeList()
 {
 }
 
-inline void FreeList::push(Owner owner, const LargeObject& largeObject)
+inline void FreeList::push(VMState::HasPhysical hasPhysical, const LargeObject& largeObject)
 {
     BASSERT(largeObject.isFree());
+    BASSERT(largeObject.vmState().hasPhysical() == static_cast<bool>(hasPhysical));
     BASSERT(!largeObject.prevCanMerge());
     BASSERT(!largeObject.nextCanMerge());
     if (m_vector.size() == m_limit) {
-        removeInvalidAndDuplicateEntries(owner);
+        removeInvalidAndDuplicateEntries(hasPhysical);
         m_limit = std::max(m_vector.size() * freeListGrowFactor, freeListSearchDepth);
     }
     m_vector.push(largeObject.range());
index d4511f5..bcd5310 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -37,7 +37,7 @@
 namespace bmalloc {
 
 Heap::Heap(std::lock_guard<StaticMutex>&)
-    : m_largeObjects(Owner::Heap)
+    : m_largeObjects(VMState::HasPhysical::True)
     , m_isAllocatingPages(false)
     , m_scavenger(*this, &Heap::concurrentScavenge)
 {
@@ -346,18 +346,8 @@ void Heap::deallocateXLarge(std::unique_lock<StaticMutex>& lock, void* object)
     lock.lock();
 }
 
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
+inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t size)
 {
-    BASSERT(size <= largeMax);
-    BASSERT(size >= largeMin);
-    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
-    
-    LargeObject largeObject = m_largeObjects.take(size);
-    if (!largeObject) {
-        m_isAllocatingPages = true;
-        largeObject = m_vmHeap.allocateLargeObject(size);
-    }
-
     BASSERT(largeObject.isFree());
 
     LargeObject nextLargeObject;
@@ -367,35 +357,19 @@ void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
         largeObject = split.first;
         nextLargeObject = split.second;
     }
-    
+
     largeObject.setFree(false);
-    
+
     if (nextLargeObject) {
         BASSERT(!nextLargeObject.nextCanMerge());
         m_largeObjects.insert(nextLargeObject);
     }
-    
-    return largeObject.begin();
+
+    return largeObject;
 }
 
-void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size, size_t unalignedSize)
+inline LargeObject& Heap::splitAndAllocate(LargeObject& largeObject, size_t alignment, size_t size)
 {
-    BASSERT(size <= largeMax);
-    BASSERT(size >= largeMin);
-    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
-    BASSERT(unalignedSize <= largeMax);
-    BASSERT(unalignedSize >= largeMin);
-    BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
-    BASSERT(alignment <= largeChunkSize / 2);
-    BASSERT(alignment >= largeAlignment);
-    BASSERT(isPowerOfTwo(alignment));
-
-    LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
-    if (!largeObject) {
-        m_isAllocatingPages = true;
-        largeObject = m_vmHeap.allocateLargeObject(alignment, size, unalignedSize);
-    }
-
     LargeObject prevLargeObject;
     LargeObject nextLargeObject;
 
@@ -408,13 +382,13 @@ void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_
     }
 
     BASSERT(largeObject.isFree());
-    
+
     if (largeObject.size() - size > largeMin) {
         std::pair<LargeObject, LargeObject> split = largeObject.split(size);
         largeObject = split.first;
         nextLargeObject = split.second;
     }
-    
+
     largeObject.setFree(false);
 
     if (prevLargeObject) {
@@ -427,6 +401,56 @@ void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_
         m_largeObjects.insert(merged);
     }
 
+    return largeObject;
+}
+
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t size)
+{
+    BASSERT(size <= largeMax);
+    BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
+
+    LargeObject largeObject = m_largeObjects.take(size);
+    if (!largeObject)
+        largeObject = m_vmHeap.allocateLargeObject(size);
+
+    if (largeObject.vmState().hasVirtual()) {
+        m_isAllocatingPages = true;
+        // We commit before we split in order to avoid split/merge commit/decommit churn.
+        vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
+        largeObject.setVMState(VMState::Physical);
+    }
+
+    largeObject = splitAndAllocate(largeObject, size);
+
+    return largeObject.begin();
+}
+
+void* Heap::allocateLarge(std::lock_guard<StaticMutex>&, size_t alignment, size_t size, size_t unalignedSize)
+{
+    BASSERT(size <= largeMax);
+    BASSERT(size >= largeMin);
+    BASSERT(size == roundUpToMultipleOf<largeAlignment>(size));
+    BASSERT(unalignedSize <= largeMax);
+    BASSERT(unalignedSize >= largeMin);
+    BASSERT(unalignedSize == roundUpToMultipleOf<largeAlignment>(unalignedSize));
+    BASSERT(alignment <= largeChunkSize / 2);
+    BASSERT(alignment >= largeAlignment);
+    BASSERT(isPowerOfTwo(alignment));
+
+    LargeObject largeObject = m_largeObjects.take(alignment, size, unalignedSize);
+    if (!largeObject)
+        largeObject = m_vmHeap.allocateLargeObject(alignment, size, unalignedSize);
+
+    if (largeObject.vmState().hasVirtual()) {
+        m_isAllocatingPages = true;
+        // We commit before we split in order to avoid split/merge commit/decommit churn.
+        vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
+        largeObject.setVMState(VMState::Physical);
+    }
+
+    largeObject = splitAndAllocate(largeObject, alignment, size);
+
     return largeObject.begin();
 }
 
index 698e738..726e27f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -85,7 +85,8 @@ private:
 
     void deallocateLarge(std::lock_guard<StaticMutex>&, const LargeObject&);
 
-    void splitLarge(BeginTag*, size_t, EndTag*&, Range&);
+    LargeObject& splitAndAllocate(LargeObject&, size_t);
+    LargeObject& splitAndAllocate(LargeObject&, size_t, size_t);
     void mergeLarge(BeginTag*&, EndTag*&, Range&);
     void mergeLargeLeft(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& inVMHeap);
index 7cbfb0e..58bf275 100644 (file)
@@ -57,13 +57,13 @@ public:
     bool prevCanMerge() const;
     bool nextCanMerge() const;
 
-    Owner owner() const;
-    void setOwner(Owner) const;
-    
+    VMState vmState() const;
+    void setVMState(VMState) const;
+
     bool isMarked() const;
     void setMarked(bool) const;
-    
-    bool isValidAndFree(Owner, size_t) const;
+
+    bool isValidAndFree(VMState::HasPhysical, size_t) const;
 
     LargeObject merge() const;
     std::pair<LargeObject, LargeObject> split(size_t) const;
@@ -123,29 +123,25 @@ inline bool LargeObject::isFree() const
 
 inline bool LargeObject::prevCanMerge() const
 {
-    EndTag* prev = m_beginTag->prev();
-
-    return prev->isFree() && prev->owner() == this->owner();
+    return m_beginTag->prev()->isFree();
 }
 
 inline bool LargeObject::nextCanMerge() const
 {
-    BeginTag* next = m_endTag->next();
-
-    return next->isFree() && next->owner() == this->owner();
+    return m_endTag->next()->isFree();
 }
 
-inline Owner LargeObject::owner() const
+inline VMState LargeObject::vmState() const
 {
     validate();
-    return m_beginTag->owner();
+    return m_beginTag->vmState();
 }
 
-inline void LargeObject::setOwner(Owner owner) const
+inline void LargeObject::setVMState(VMState vmState) const
 {
     validate();
-    m_beginTag->setOwner(owner);
-    m_endTag->setOwner(owner);
+    m_beginTag->setVMState(vmState);
+    m_endTag->setVMState(vmState);
 }
 
 inline bool LargeObject::isMarked() const
@@ -161,7 +157,7 @@ inline void LargeObject::setMarked(bool isMarked) const
     m_endTag->setMarked(isMarked);
 }
 
-inline bool LargeObject::isValidAndFree(Owner expectedOwner, size_t expectedSize) const
+inline bool LargeObject::isValidAndFree(VMState::HasPhysical hasPhysical, size_t expectedSize) const
 {
     if (!m_beginTag->isFree())
         return false;
@@ -175,9 +171,9 @@ inline bool LargeObject::isValidAndFree(Owner expectedOwner, size_t expectedSize
     if (m_beginTag->compactBegin() != BoundaryTag::compactBegin(m_object))
         return false;
 
-    if (m_beginTag->owner() != expectedOwner)
+    if (m_beginTag->vmState().hasPhysical() != static_cast<bool>(hasPhysical))
         return false;
-    
+
     return true;
 }
 
@@ -189,10 +185,11 @@ inline LargeObject LargeObject::merge() const
     BeginTag* beginTag = m_beginTag;
     EndTag* endTag = m_endTag;
     Range range = this->range();
-    Owner owner = this->owner();
-    
+    VMState vmState = this->vmState();
+
     EndTag* prev = beginTag->prev();
-    if (prev->isFree() && prev->owner() == owner) {
+    if (prev->isFree()) {
+        vmState.merge(prev->vmState());
         Range left(range.begin() - prev->size(), prev->size());
         range = Range(left.begin(), left.size() + range.size());
 
@@ -203,7 +200,8 @@ inline LargeObject LargeObject::merge() const
     }
 
     BeginTag* next = endTag->next();
-    if (next->isFree() && next->owner() == owner) {
+    if (next->isFree()) {
+        vmState.merge(next->vmState());
         Range right(range.end(), next->size());
         range = Range(range.begin(), range.size() + right.size());
 
@@ -215,7 +213,7 @@ inline LargeObject LargeObject::merge() const
 
     beginTag->setRange(range);
     beginTag->setFree(true);
-    beginTag->setOwner(owner);
+    beginTag->setVMState(vmState);
     endTag->init(beginTag);
 
     return LargeObject(beginTag, endTag, range.begin());
@@ -254,7 +252,7 @@ inline void LargeObject::validateSelf() const
 
     BASSERT(m_beginTag->size() == m_endTag->size());
     BASSERT(m_beginTag->isFree() == m_endTag->isFree());
-    BASSERT(m_beginTag->owner() == m_endTag->owner());
+    BASSERT(m_beginTag->vmState() == m_endTag->vmState());
     BASSERT(m_beginTag->isMarked() == m_endTag->isMarked());
 }
 
@@ -280,7 +278,7 @@ inline Range LargeObject::init(LargeChunk* chunk)
     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
     beginTag->setRange(range);
     beginTag->setFree(true);
-    beginTag->setOwner(Owner::VMHeap);
+    beginTag->setVMState(VMState::Virtual);
 
     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
     endTag->init(beginTag);
index 96f6671..4bcf1c5 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 
 namespace bmalloc {
 
-SegregatedFreeList::SegregatedFreeList(Owner owner)
-    : m_owner(owner)
+SegregatedFreeList::SegregatedFreeList(VMState::HasPhysical hasPhysical)
+    : m_hasPhysical(hasPhysical)
 {
     BASSERT(static_cast<size_t>(&select(largeMax) - m_freeLists.begin()) == m_freeLists.size() - 1);
 }
 
 void SegregatedFreeList::insert(const LargeObject& largeObject)
 {
-    BASSERT(largeObject.owner() == m_owner);
     auto& list = select(largeObject.size());
-    list.push(m_owner, largeObject);
+    list.push(hasPhysical(), largeObject);
 }
 
 LargeObject SegregatedFreeList::takeGreedy()
 {
     for (size_t i = m_freeLists.size(); i-- > 0; ) {
-        LargeObject largeObject = m_freeLists[i].takeGreedy(m_owner);
+        LargeObject largeObject = m_freeLists[i].takeGreedy(hasPhysical());
         if (!largeObject)
             continue;
 
@@ -55,7 +54,7 @@ LargeObject SegregatedFreeList::takeGreedy()
 LargeObject SegregatedFreeList::take(size_t size)
 {
     for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
-        LargeObject largeObject = list->take(m_owner, size);
+        LargeObject largeObject = list->take(hasPhysical(), size);
         if (!largeObject)
             continue;
 
@@ -67,7 +66,7 @@ LargeObject SegregatedFreeList::take(size_t size)
 LargeObject SegregatedFreeList::take(size_t alignment, size_t size, size_t unalignedSize)
 {
     for (auto* list = &select(size); list != m_freeLists.end(); ++list) {
-        LargeObject largeObject = list->take(m_owner, alignment, size, unalignedSize);
+        LargeObject largeObject = list->take(hasPhysical(), alignment, size, unalignedSize);
         if (!largeObject)
             continue;
 
index 7bc5441..33f8b3b 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -33,7 +33,7 @@ namespace bmalloc {
 
 class SegregatedFreeList {
 public:
-    SegregatedFreeList(Owner);
+    SegregatedFreeList(VMState::HasPhysical);
 
     void insert(const LargeObject&);
 
@@ -56,10 +56,11 @@ public:
     // the returned object from the free list.
     LargeObject takeGreedy();
 
+    VMState::HasPhysical hasPhysical() const { return m_hasPhysical; }
 private:
     FreeList& select(size_t);
 
-    Owner m_owner;
+    VMState::HasPhysical m_hasPhysical;
     std::array<FreeList, 15> m_freeLists;
 };
 
index 7e698c2..0273a0d 100644 (file)
@@ -183,10 +183,10 @@ inline void vmDeallocatePhysicalPagesSloppy(void* p, size_t size)
     vmDeallocatePhysicalPages(begin, end - begin);
 }
 
-// Expands requests that are un-page-aligned. NOTE: Allocation must proceed left-to-right.
+// Expands requests that are un-page-aligned.
 inline void vmAllocatePhysicalPagesSloppy(void* p, size_t size)
 {
-    char* begin = roundUpToMultipleOf<vmPageSize>(static_cast<char*>(p));
+    char* begin = roundDownToMultipleOf<vmPageSize>(static_cast<char*>(p));
     char* end = roundUpToMultipleOf<vmPageSize>(static_cast<char*>(p) + size);
 
     if (begin >= end)
index 3659bfa..6d7aabe 100644 (file)
@@ -33,7 +33,7 @@
 namespace bmalloc {
 
 VMHeap::VMHeap()
-    : m_largeObjects(Owner::VMHeap)
+    : m_largeObjects(VMState::HasPhysical::False)
 {
 }
 
index 17c956d..7e5d420 100644 (file)
@@ -34,6 +34,7 @@
 #include "Range.h"
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
+#include "VMState.h"
 #include "Vector.h"
 #if BOS(DARWIN)
 #include "Zone.h"
@@ -53,14 +54,13 @@ public:
     SmallPage* allocateSmallPage();
     MediumPage* allocateMediumPage();
     LargeObject allocateLargeObject(size_t);
-    LargeObject allocateLargeObject(size_t alignment, size_t, size_t unalignedSize);
+    LargeObject allocateLargeObject(size_t, size_t, size_t);
 
     void deallocateSmallPage(std::unique_lock<StaticMutex>&, SmallPage*);
     void deallocateMediumPage(std::unique_lock<StaticMutex>&, MediumPage*);
     void deallocateLargeObject(std::unique_lock<StaticMutex>&, LargeObject);
 
 private:
-    LargeObject allocateLargeObject(LargeObject&, size_t);
     void grow();
 
     Vector<SmallPage*> m_smallPages;
@@ -91,30 +91,6 @@ inline MediumPage* VMHeap::allocateMediumPage()
     return page;
 }
 
-inline LargeObject VMHeap::allocateLargeObject(LargeObject& largeObject, size_t size)
-{
-    BASSERT(largeObject.isFree());
-
-    LargeObject nextLargeObject;
-
-    if (largeObject.size() - size > largeMin) {
-        std::pair<LargeObject, LargeObject> split = largeObject.split(size);
-        largeObject = split.first;
-        nextLargeObject = split.second;
-    }
-
-    vmAllocatePhysicalPagesSloppy(largeObject.begin(), largeObject.size());
-    largeObject.setOwner(Owner::Heap);
-
-    // Be sure to set the owner for the object we return before inserting the leftover back
-    // into the free list. The free list asserts that we never insert an object that could
-    // have merged with its neighbor.
-    if (nextLargeObject)
-        m_largeObjects.insert(nextLargeObject);
-
-    return largeObject.begin();
-}
-
 inline LargeObject VMHeap::allocateLargeObject(size_t size)
 {
     LargeObject largeObject = m_largeObjects.take(size);
@@ -124,7 +100,7 @@ inline LargeObject VMHeap::allocateLargeObject(size_t size)
         BASSERT(largeObject);
     }
 
-    return allocateLargeObject(largeObject, size);
+    return largeObject;
 }
 
 inline LargeObject VMHeap::allocateLargeObject(size_t alignment, size_t size, size_t unalignedSize)
@@ -136,10 +112,7 @@ inline LargeObject VMHeap::allocateLargeObject(size_t alignment, size_t size, si
         BASSERT(largeObject);
     }
 
-    size_t alignmentMask = alignment - 1;
-    if (test(largeObject.begin(), alignmentMask))
-        return allocateLargeObject(largeObject, unalignedSize);
-    return allocateLargeObject(largeObject, size);
+    return largeObject;
 }
 
 inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, SmallPage* page)
@@ -162,13 +135,9 @@ inline void VMHeap::deallocateMediumPage(std::unique_lock<StaticMutex>& lock, Me
 
 inline void VMHeap::deallocateLargeObject(std::unique_lock<StaticMutex>& lock, LargeObject largeObject)
 {
-    largeObject.setOwner(Owner::VMHeap);
-
     // Multiple threads might scavenge concurrently, meaning that new merging opportunities
     // become visible after we reacquire the lock. Therefore we loop.
     do {
-        // If we couldn't merge with our neighbors before because they were in the
-        // VM heap, we can merge with them now.
         largeObject = largeObject.merge();
 
         // Temporarily mark this object as allocated to prevent clients from merging
@@ -182,6 +151,7 @@ inline void VMHeap::deallocateLargeObject(std::unique_lock<StaticMutex>& lock, L
         largeObject.setFree(true);
     } while (largeObject.prevCanMerge() || largeObject.nextCanMerge());
 
+    largeObject.setVMState(VMState::Virtual);
     m_largeObjects.insert(largeObject);
 }
 
similarity index 57%
rename from Source/bmalloc/bmalloc/Owner.h
rename to Source/bmalloc/bmalloc/VMState.h
index 8554623..3c85367 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  */
 
-#ifndef Owner_h
-#define Owner_h
+#ifndef VMState_h
+#define VMState_h
 
 namespace bmalloc {
 
-enum class Owner : unsigned {
-    VMHeap,
-    Heap
+class VMState {
+public:
+    enum class HasPhysical : bool {
+        False = false,
+        True = true
+    };
+
+    enum State : unsigned {
+        Invalid = 0x0,
+        Physical = 0x1,
+        Virtual = 0x2,
+        Mixed = 0x3
+    };
+
+    VMState(State vmState)
+        : m_state(vmState)
+    {
+    }
+
+    explicit VMState(unsigned vmState)
+        : m_state(static_cast<State>(vmState))
+    {
+    }
+
+    inline bool hasPhysical()
+    {
+        return !!(m_state & VMState::Physical);
+    }
+
+    inline bool hasVirtual()
+    {
+        return !!(m_state & VMState::Virtual);
+    }
+
+    inline void merge(VMState otherVMState)
+    {
+        m_state = static_cast<State>(m_state | otherVMState.m_state);
+    }
+
+    bool operator==(VMState other) const { return m_state == other.m_state; }
+    explicit operator unsigned() const { return m_state; }
+
+private:
+    State m_state;
 };
 
 } // namespace bmalloc
 
-#endif // Owner_h
+#endif // VMState_h