2014-04-19 Geoffrey Garen <ggaren@apple.com>
+ Rolled out r167502 because it caused a crash on the facebook benchmark.
+
+ Unreviewed.
+
+ bmalloc: Added an XSmall line size
+ https://bugs.webkit.org/show_bug.cgi?id=131851
+
+ Reviewed by Sam Weinig.
+
+2014-04-19 Geoffrey Garen <ggaren@apple.com>
+
bmalloc: Mutex should be harder to use wrong
https://bugs.webkit.org/show_bug.cgi?id=131879
1400274A18F89C2300115C97 /* VMHeap.h in Headers */ = {isa = PBXBuildFile; fileRef = 144F7BFC18BFC517003537F3 /* VMHeap.h */; settings = {ATTRIBUTES = (Private, ); }; };
1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */ = {isa = PBXBuildFile; fileRef = 14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */; settings = {ATTRIBUTES = (Private, ); }; };
1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */ = {isa = PBXBuildFile; fileRef = 146BEE1E18C841C50002D5A2 /* SegregatedFreeList.h */; settings = {ATTRIBUTES = (Private, ); }; };
- 142FCC78190080B8009032D4 /* XSmallChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 142FCC74190080B8009032D4 /* XSmallChunk.h */; };
- 142FCC79190080B8009032D4 /* XSmallLine.h in Headers */ = {isa = PBXBuildFile; fileRef = 142FCC75190080B8009032D4 /* XSmallLine.h */; };
- 142FCC7A190080B8009032D4 /* XSmallPage.h in Headers */ = {isa = PBXBuildFile; fileRef = 142FCC76190080B8009032D4 /* XSmallPage.h */; };
- 142FCC7B190080B8009032D4 /* XSmallTraits.h in Headers */ = {isa = PBXBuildFile; fileRef = 142FCC77190080B8009032D4 /* XSmallTraits.h */; };
- 142FCC7D1900815E009032D4 /* XSmallAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 142FCC7C1900815E009032D4 /* XSmallAllocator.h */; };
143CB81C19022BC900B16A45 /* StaticMutex.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143CB81A19022BC900B16A45 /* StaticMutex.cpp */; };
143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */ = {isa = PBXBuildFile; fileRef = 143CB81B19022BC900B16A45 /* StaticMutex.h */; };
1448C30018F3754600502839 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1448C2FF18F3754300502839 /* mbmalloc.cpp */; };
1417F64F18B7280C0076FA3F /* Syscall.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Syscall.h; path = bmalloc/Syscall.h; sourceTree = "<group>"; };
1417F65218BA88A00076FA3F /* AsyncTask.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = AsyncTask.h; path = bmalloc/AsyncTask.h; sourceTree = "<group>"; };
1421A87718EE462A00B4DD68 /* Algorithm.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; name = Algorithm.h; path = bmalloc/Algorithm.h; sourceTree = "<group>"; };
- 142FCC74190080B8009032D4 /* XSmallChunk.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XSmallChunk.h; path = bmalloc/XSmallChunk.h; sourceTree = "<group>"; };
- 142FCC75190080B8009032D4 /* XSmallLine.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XSmallLine.h; path = bmalloc/XSmallLine.h; sourceTree = "<group>"; };
- 142FCC76190080B8009032D4 /* XSmallPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XSmallPage.h; path = bmalloc/XSmallPage.h; sourceTree = "<group>"; };
- 142FCC77190080B8009032D4 /* XSmallTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XSmallTraits.h; path = bmalloc/XSmallTraits.h; sourceTree = "<group>"; };
- 142FCC7C1900815E009032D4 /* XSmallAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = XSmallAllocator.h; path = bmalloc/XSmallAllocator.h; sourceTree = "<group>"; };
143CB81A19022BC900B16A45 /* StaticMutex.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = StaticMutex.cpp; path = bmalloc/StaticMutex.cpp; sourceTree = "<group>"; };
143CB81B19022BC900B16A45 /* StaticMutex.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StaticMutex.h; path = bmalloc/StaticMutex.h; sourceTree = "<group>"; };
143E29E918CAE8BE00FE8A0F /* MediumPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumPage.h; path = bmalloc/MediumPage.h; sourceTree = "<group>"; };
1452478618BC757C00F80098 /* SmallLine.h */,
143E29ED18CAE90500FE8A0F /* SmallPage.h */,
147AAA9718CE5FB6002201E4 /* SmallTraits.h */,
- 142FCC74190080B8009032D4 /* XSmallChunk.h */,
- 142FCC75190080B8009032D4 /* XSmallLine.h */,
- 142FCC76190080B8009032D4 /* XSmallPage.h */,
- 142FCC77190080B8009032D4 /* XSmallTraits.h */,
);
name = "heap: small | medium";
sourceTree = "<group>";
145F685A179DC90200D65598 /* Deallocator.h */,
1413E47018A0661700546D68 /* MediumAllocator.h */,
1413E462189DE1CD00546D68 /* SmallAllocator.h */,
- 142FCC7C1900815E009032D4 /* XSmallAllocator.h */,
);
name = cache;
sourceTree = "<group>";
isa = PBXHeadersBuildPhase;
buildActionMask = 2147483647;
files = (
- 142FCC7B190080B8009032D4 /* XSmallTraits.h in Headers */,
14DD78B518F48D6B00950702 /* Line.h in Headers */,
14DD78CF18F48D7500950702 /* Vector.h in Headers */,
14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */,
14DD78CC18F48D7500950702 /* PerThread.h in Headers */,
14DD78B418F48D6B00950702 /* Chunk.h in Headers */,
14DD78CA18F48D7500950702 /* Mutex.h in Headers */,
- 142FCC7D1900815E009032D4 /* XSmallAllocator.h in Headers */,
143CB81D19022BC900B16A45 /* StaticMutex.h in Headers */,
14DD78D118F48EC600950702 /* XLargeChunk.h in Headers */,
14DD78B918F48D6B00950702 /* MediumTraits.h in Headers */,
14DD78BB18F48D6B00950702 /* SmallChunk.h in Headers */,
14DD78C918F48D7500950702 /* Inline.h in Headers */,
1400274A18F89C2300115C97 /* VMHeap.h in Headers */,
- 142FCC7A190080B8009032D4 /* XSmallPage.h in Headers */,
1400274918F89C1300115C97 /* Heap.h in Headers */,
14DD78B818F48D6B00950702 /* MediumPage.h in Headers */,
14DD78C518F48D7500950702 /* Algorithm.h in Headers */,
14DD78BD18F48D6B00950702 /* SmallPage.h in Headers */,
1400274B18F89C3D00115C97 /* BoundaryTagInlines.h in Headers */,
- 142FCC79190080B8009032D4 /* XSmallLine.h in Headers */,
- 142FCC78190080B8009032D4 /* XSmallChunk.h in Headers */,
14DD788E18F48CCD00950702 /* BoundaryTag.h in Headers */,
14DD78C818F48D7500950702 /* FixedVector.h in Headers */,
14DD78B718F48D6B00950702 /* MediumLine.h in Headers */,
, m_mediumAllocatorLog()
{
unsigned short size = alignment;
- for ( ; size <= xSmallMax; size += alignment)
- xSmallAllocatorFor(size) = XSmallAllocator(size);
-
- for ( ; size <= smallMax; size += alignment)
- smallAllocatorFor(size) = SmallAllocator(size);
+ for (auto& allocator : m_smallAllocators) {
+ allocator = SmallAllocator(size);
+ size += alignment;
+ }
}
Allocator::~Allocator()
void Allocator::scavenge()
{
- for (auto& allocator : m_xSmallAllocators)
- log(allocator);
- processXSmallAllocatorLog();
-
for (auto& allocator : m_smallAllocators)
log(allocator);
processSmallAllocatorLog();
processMediumAllocatorLog();
}
-void Allocator::log(XSmallAllocator& allocator)
-{
- if (allocator.isNull())
- return;
-
- if (m_xSmallAllocatorLog.size() == m_xSmallAllocatorLog.capacity())
- processXSmallAllocatorLog();
-
- m_xSmallAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
-}
-
-void Allocator::processXSmallAllocatorLog()
-{
- std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-
- for (auto& logEntry : m_xSmallAllocatorLog) {
- if (!logEntry.first->deref(lock, logEntry.second))
- continue;
- m_deallocator.deallocateXSmallLine(lock, logEntry.first);
- }
- m_xSmallAllocatorLog.clear();
-}
-
void Allocator::log(SmallAllocator& allocator)
{
- if (allocator.isNull())
- return;
-
if (m_smallAllocatorLog.size() == m_smallAllocatorLog.capacity())
processSmallAllocatorLog();
+ if (allocator.isNull())
+ return;
+
m_smallAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
}
void Allocator::log(MediumAllocator& allocator)
{
- if (allocator.isNull())
- return;
-
if (m_mediumAllocatorLog.size() == m_mediumAllocatorLog.capacity())
processMediumAllocatorLog();
+ if (allocator.isNull())
+ return;
+
m_mediumAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
}
void* dummy;
BASSERT(!allocateFastCase(size, dummy));
)
- if (size <= xSmallMax) {
- XSmallAllocator& allocator = xSmallAllocatorFor(size);
- log(allocator);
- allocator.refill(m_deallocator.allocateXSmallLine());
- return allocator.allocate();
- }
-
if (size <= smallMax) {
SmallAllocator& allocator = smallAllocatorFor(size);
log(allocator);
#include "MediumAllocator.h"
#include "Sizes.h"
#include "SmallAllocator.h"
-#include "XSmallAllocator.h"
#include <array>
namespace bmalloc {
void scavenge();
private:
- XSmallAllocator& xSmallAllocatorFor(size_t);
SmallAllocator& smallAllocatorFor(size_t);
-
void* allocateFastCase(SmallAllocator&);
void* allocateMedium(size_t);
void* allocateLarge(size_t);
void* allocateXLarge(size_t);
- void log(XSmallAllocator&);
void log(SmallAllocator&);
void log(MediumAllocator&);
- void processXSmallAllocatorLog();
void processSmallAllocatorLog();
void processMediumAllocatorLog();
Deallocator& m_deallocator;
- std::array<XSmallAllocator, xSmallMax / alignment> m_xSmallAllocators;
std::array<SmallAllocator, smallMax / alignment> m_smallAllocators;
MediumAllocator m_mediumAllocator;
- FixedVector<std::pair<XSmallLine*, unsigned char>, xSmallAllocatorLogCapacity> m_xSmallAllocatorLog;
FixedVector<std::pair<SmallLine*, unsigned char>, smallAllocatorLogCapacity> m_smallAllocatorLog;
FixedVector<std::pair<MediumLine*, unsigned char>, mediumAllocatorLogCapacity> m_mediumAllocatorLog;
};
-inline XSmallAllocator& Allocator::xSmallAllocatorFor(size_t size)
-{
- size_t index = mask((size - 1ul) / alignment, m_xSmallAllocators.size() - 1);
- return m_xSmallAllocators[index];
-}
-
inline SmallAllocator& Allocator::smallAllocatorFor(size_t size)
{
size_t index = mask((size - 1ul) / alignment, m_smallAllocators.size() - 1);
inline bool Allocator::allocateFastCase(size_t size, void*& object)
{
- if (size <= xSmallMax) {
- XSmallAllocator& allocator = xSmallAllocatorFor(size);
- if (!allocator.canAllocate())
- return false;
-
- object = allocator.allocate();
- return true;
- }
-
- if (size <= smallMax) {
- SmallAllocator& allocator = smallAllocatorFor(size);
- if (!allocator.canAllocate())
- return false;
-
- object = allocator.allocate();
- return true;
- }
-
- return false;
+ if (size > smallMax)
+ return false;
+
+ SmallAllocator& allocator = smallAllocatorFor(size);
+ if (!allocator.canAllocate())
+ return false;
+
+ object = allocator.allocate();
+ return true;
}
inline void* Allocator::allocate(size_t size)
template<class Traits>
inline auto Chunk<Traits>::get(void* object) -> Chunk*
{
- BASSERT(!isLarge(object));
+ BASSERT(isSmallOrMedium(object));
return static_cast<Chunk*>(mask(object, chunkMask));
}
#include "Inline.h"
#include "PerProcess.h"
#include "SmallChunk.h"
-#include "XSmallChunk.h"
#include <algorithm>
#include <sys/mman.h>
std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
Heap* heap = PerProcess<Heap>::getFastCase();
- while (m_xSmallLineCache.size())
- heap->deallocateXSmallLine(lock, m_xSmallLineCache.pop());
while (m_smallLineCache.size())
heap->deallocateSmallLine(lock, m_smallLineCache.pop());
while (m_mediumLineCache.size())
std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
for (auto object : m_objectLog) {
- if (isXSmall(object)) {
- XSmallLine* line = XSmallLine::get(object);
- if (!line->deref(lock))
- continue;
- deallocateXSmallLine(lock, line);
- } else if (isSmall(object)) {
+ if (isSmall(object)) {
SmallLine* line = SmallLine::get(object);
if (!line->deref(lock))
continue;
deallocateSmallLine(lock, line);
} else {
- BASSERT(isMedium(object));
+ BASSERT(isSmallOrMedium(object));
MediumLine* line = MediumLine::get(object);
if (!line->deref(lock))
continue;
if (!object)
return;
- if (!isLarge(object)) {
+ if (isSmallOrMedium(object)) {
processObjectLog();
m_objectLog.push(object);
return;
m_smallLineCache.push(line);
}
-void Deallocator::deallocateXSmallLine(std::lock_guard<StaticMutex>& lock, XSmallLine* line)
-{
- if (m_xSmallLineCache.size() == m_xSmallLineCache.capacity())
- return PerProcess<Heap>::getFastCase()->deallocateXSmallLine(lock, line);
-
- m_xSmallLineCache.push(line);
-}
-
SmallLine* Deallocator::allocateSmallLine()
{
if (!m_smallLineCache.size()) {
return m_smallLineCache.pop();
}
-XSmallLine* Deallocator::allocateXSmallLine()
-{
- if (!m_xSmallLineCache.size()) {
- std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
- Heap* heap = PerProcess<Heap>::getFastCase();
-
- while (m_xSmallLineCache.size() != m_xSmallLineCache.capacity())
- m_xSmallLineCache.push(heap->allocateXSmallLine(lock));
- }
-
- return m_xSmallLineCache.pop();
-}
-
void Deallocator::deallocateMediumLine(std::lock_guard<StaticMutex>& lock, MediumLine* line)
{
if (m_mediumLineCache.size() == m_mediumLineCache.capacity())
#include "MediumLine.h"
#include "Sizes.h"
#include "SmallLine.h"
-#include "XSmallLine.h"
namespace bmalloc {
bool deallocateFastCase(void*);
void deallocateSlowCase(void*);
- void deallocateXSmallLine(std::lock_guard<StaticMutex>&, XSmallLine*);
- XSmallLine* allocateXSmallLine();
-
void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
SmallLine* allocateSmallLine();
void processObjectLog();
FixedVector<void*, deallocatorLogCapacity> m_objectLog;
- FixedVector<XSmallLine*, xSmallLineCacheCapacity> m_xSmallLineCache;
FixedVector<SmallLine*, smallLineCacheCapacity> m_smallLineCache;
FixedVector<MediumLine*, mediumLineCacheCapacity> m_mediumLineCache;
};
inline bool Deallocator::deallocateFastCase(void* object)
{
- if (isLarge(object))
+ if (!isSmallOrMedium(object))
return false;
BASSERT(object);
#include "PerProcess.h"
#include "SmallChunk.h"
#include "XLargeChunk.h"
-#include "XSmallChunk.h"
#include <thread>
namespace bmalloc {
void Heap::scavenge(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
{
- scavengeXSmallPages(lock, sleepDuration);
scavengeSmallPages(lock, sleepDuration);
scavengeMediumPages(lock, sleepDuration);
scavengeLargeRanges(lock, sleepDuration);
}
}
-void Heap::scavengeXSmallPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
-{
- while (1) {
- if (m_isAllocatingPages) {
- m_isAllocatingPages = false;
-
- sleep(lock, sleepDuration);
- continue;
- }
-
- if (!m_xSmallPages.size())
- return;
- m_vmHeap.deallocateXSmallPage(lock, m_xSmallPages.pop());
- }
-}
-
void Heap::scavengeMediumPages(std::unique_lock<StaticMutex>& lock, std::chrono::milliseconds sleepDuration)
{
while (1) {
}
}
-XSmallLine* Heap::allocateXSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
-{
- m_isAllocatingPages = true;
-
- XSmallPage* page = [this]() {
- if (m_xSmallPages.size())
- return m_xSmallPages.pop();
-
- XSmallPage* page = m_vmHeap.allocateXSmallPage();
- vmAllocatePhysicalPages(page->begin()->begin(), vmPageSize);
- return page;
- }();
-
- XSmallLine* line = page->begin();
- for (auto it = line + 1; it != page->end(); ++it)
- m_xSmallLines.push(it);
-
- page->ref(lock);
- return line;
-}
-
SmallLine* Heap::allocateSmallLineSlowCase(std::lock_guard<StaticMutex>& lock)
{
m_isAllocatingPages = true;
#include "FixedVector.h"
#include "VMHeap.h"
+#include "MediumLine.h"
#include "Mutex.h"
+#include "SmallPage.h"
#include "MediumChunk.h"
+#include "MediumPage.h"
#include "SegregatedFreeList.h"
#include "SmallChunk.h"
+#include "SmallLine.h"
#include "Vector.h"
-#include "XSmallChunk.h"
#include <array>
#include <mutex>
class Heap {
public:
Heap(std::lock_guard<StaticMutex>&);
-
- XSmallLine* allocateXSmallLine(std::lock_guard<StaticMutex>&);
- void deallocateXSmallLine(std::lock_guard<StaticMutex>&, XSmallLine*);
SmallLine* allocateSmallLine(std::lock_guard<StaticMutex>&);
void deallocateSmallLine(std::lock_guard<StaticMutex>&, SmallLine*);
private:
~Heap() = delete;
- XSmallLine* allocateXSmallLineSlowCase(std::lock_guard<StaticMutex>&);
SmallLine* allocateSmallLineSlowCase(std::lock_guard<StaticMutex>&);
MediumLine* allocateMediumLineSlowCase(std::lock_guard<StaticMutex>&);
void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
void concurrentScavenge();
- void scavengeXSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
void scavengeSmallPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
void scavengeMediumPages(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
void scavengeLargeRanges(std::unique_lock<StaticMutex>&, std::chrono::milliseconds);
- Vector<XSmallLine*> m_xSmallLines;
Vector<SmallLine*> m_smallLines;
Vector<MediumLine*> m_mediumLines;
- Vector<XSmallPage*> m_xSmallPages;
Vector<SmallPage*> m_smallPages;
Vector<MediumPage*> m_mediumPages;
AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
};
-inline void Heap::deallocateXSmallLine(std::lock_guard<StaticMutex>& lock, XSmallLine* line)
-{
- XSmallPage* page = XSmallPage::get(line);
- if (page->deref(lock)) {
- m_xSmallPages.push(page);
- m_scavenger.run();
- return;
- }
- m_xSmallLines.push(line);
-}
-
-inline XSmallLine* Heap::allocateXSmallLine(std::lock_guard<StaticMutex>& lock)
-{
- while (m_xSmallLines.size()) {
- XSmallLine* line = m_xSmallLines.pop();
- XSmallPage* page = XSmallPage::get(line);
- if (!page->refCount(lock)) // The line was promoted to the small pages list.
- continue;
- page->ref(lock);
- return line;
- }
-
- return allocateXSmallLineSlowCase(lock);
-}
-
inline void Heap::deallocateSmallLine(std::lock_guard<StaticMutex>& lock, SmallLine* line)
{
SmallPage* page = SmallPage::get(line);
inline LargeChunk* LargeChunk::get(void* object)
{
- BASSERT(isLarge(object));
+ BASSERT(!isSmallOrMedium(object));
return static_cast<LargeChunk*>(mask(object, largeChunkMask));
}
inline EndTag* LargeChunk::endTag(void* object, size_t size)
{
- BASSERT(isLarge(object));
+ BASSERT(!isSmallOrMedium(object));
LargeChunk* chunk = get(object);
char* end = static_cast<char*>(object) + size;
template<class Traits>
inline auto Line<Traits>::get(void* object) -> Line*
{
- BASSERT(!isLarge(object));
+ BASSERT(isSmallOrMedium(object));
Chunk* chunk = Chunk::get(object);
size_t lineNumber = (reinterpret_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / lineSize;
return &chunk->lines()[lineNumber];
m_remaining -= size;
void* object = m_end - m_remaining - size;
- BASSERT(objectType(object) == Medium);
+ BASSERT(isSmallOrMedium(object) && !isSmall(object));
++m_objectCount;
return object;
m_end = line->end();
m_remaining = mediumLineSize;
m_objectCount = 0;
- BASSERT(objectType(m_end - 1) == Medium);
}
} // namespace bmalloc
ObjectType objectType(void* object)
{
- switch (mask(reinterpret_cast<uintptr_t>(object), typeMask)) {
- case xSmallType: {
- return XSmall;
- }
- case smallType: {
- return Small;
- }
- case mediumType: {
+ if (isSmallOrMedium(object)) {
+ if (isSmall(object))
+ return Small;
return Medium;
}
- case largeType: {
- BeginTag* beginTag = LargeChunk::beginTag(object);
- if (!beginTag->isXLarge())
- return Large;
- return XLarge;
- }
- default: {
- RELEASE_BASSERT(false);
- return XLarge;
- }
- }
+
+ BeginTag* beginTag = LargeChunk::beginTag(object);
+ if (!beginTag->isXLarge())
+ return Large;
+ return XLarge;
}
} // namespace bmalloc
namespace bmalloc {
-enum ObjectType { XSmall, Small, Medium, Large, XLarge };
+enum ObjectType { Small, Medium, Large, XLarge };
ObjectType objectType(void*);
-inline bool isXSmall(void* object)
+inline bool isSmallOrMedium(void* object)
{
- return mask(reinterpret_cast<uintptr_t>(object), typeMask) == xSmallType;
+ return test(object, smallOrMediumTypeMask);
}
-inline bool isSmall(void* object)
+inline bool isSmall(void* smallOrMedium)
{
- return mask(reinterpret_cast<uintptr_t>(object), typeMask) == smallType;
-}
-
-inline bool isMedium(void* object)
-{
- return mask(reinterpret_cast<uintptr_t>(object), typeMask) == mediumType;
-}
-
-inline bool isLarge(void* object)
-{
- return mask(reinterpret_cast<uintptr_t>(object), typeMask) == largeType;
+ BASSERT(isSmallOrMedium(smallOrMedium));
+ return test(smallOrMedium, smallOrMediumSmallTypeMask);
}
} // namespace bmalloc
Range take(List&, size_t);
Range takeGreedy(List&, size_t);
- std::array<List, 18> m_lists;
+ std::array<List, 19> m_lists;
};
} // namespace bmalloc
static const size_t superChunkSize = 32 * MB;
- static const size_t xSmallMax = 64;
- static const size_t xSmallLineSize = 256;
- static const size_t xSmallLineMask = ~(xSmallLineSize - 1ul);
-
- static const size_t xSmallChunkSize = superChunkSize / 4;
- static const size_t xSmallChunkOffset = superChunkSize * 1 / 4;
- static const size_t xSmallChunkMask = ~(xSmallChunkSize - 1ul);
-
- static const size_t smallMax = 128;
- static const size_t smallLineSize = 256;
+ static const size_t smallMax = 256;
+ static const size_t smallLineSize = 512;
static const size_t smallLineMask = ~(smallLineSize - 1ul);
static const size_t smallChunkSize = superChunkSize / 4;
- static const size_t smallChunkOffset = superChunkSize * 2 / 4;
+ static const size_t smallChunkOffset = superChunkSize * 3 / 4;
static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
- static const size_t mediumMax = 256;
- static const size_t mediumLineSize = 512;
+ static const size_t mediumMax = 1024;
+ static const size_t mediumLineSize = 2048;
static const size_t mediumLineMask = ~(mediumLineSize - 1ul);
static const size_t mediumChunkSize = superChunkSize / 4;
- static const size_t mediumChunkOffset = superChunkSize * 3 / 4;
+ static const size_t mediumChunkOffset = superChunkSize * 2 / 4;
static const size_t mediumChunkMask = ~(mediumChunkSize - 1ul);
- static const size_t largeChunkSize = superChunkSize / 4;
- static const size_t largeChunkOffset = superChunkSize * 0 / 4;
+ static const size_t largeChunkSize = superChunkSize / 2;
+ static const size_t largeChunkOffset = 0;
static const size_t largeChunkMask = ~(largeChunkSize - 1ul);
static const size_t largeAlignment = 64;
static const size_t largeMax = largeChunkSize * 99 / 100; // Plenty of room for metadata.
- static const size_t largeMin = mediumMax;
+ static const size_t largeMin = 1024;
static const size_t segregatedFreeListSearchDepth = 16;
static const uintptr_t typeMask = (superChunkSize - 1) & ~((superChunkSize / 4) - 1); // 4 taggable chunks
- static const uintptr_t xSmallType = (superChunkSize + xSmallChunkOffset) & typeMask;
static const uintptr_t smallType = (superChunkSize + smallChunkOffset) & typeMask;
static const uintptr_t mediumType = (superChunkSize + mediumChunkOffset) & typeMask;
- static const uintptr_t largeType = (superChunkSize + largeChunkOffset) & typeMask;
-
+ static const uintptr_t largeTypeMask = ~(mediumType & smallType);
+ static const uintptr_t smallOrMediumTypeMask = mediumType & smallType;
+ static const uintptr_t smallOrMediumSmallTypeMask = smallType ^ mediumType; // Only valid if object is known to be small or medium.
+
static const size_t deallocatorLogCapacity = 256;
- static const size_t xSmallLineCacheCapacity = 32;
static const size_t smallLineCacheCapacity = 16;
static const size_t mediumLineCacheCapacity = 8;
- static const size_t xSmallAllocatorLogCapacity = 32;
static const size_t smallAllocatorLogCapacity = 16;
static const size_t mediumAllocatorLogCapacity = 8;
#include "BAssert.h"
#include "SmallChunk.h"
+#include "SmallLine.h"
namespace bmalloc {
--m_remaining;
char* result = m_ptr;
m_ptr += m_size;
- BASSERT(objectType(result) == Small);
+ BASSERT(isSmall(result));
return result;
}
typedef Page<SmallTraits> Page;
static const size_t lineSize = smallLineSize;
- static const size_t minimumObjectSize = xSmallMax + alignment;
+ static const size_t minimumObjectSize = alignment;
static const size_t chunkSize = smallChunkSize;
static const size_t chunkOffset = smallChunkOffset;
static const uintptr_t chunkMask = smallChunkMask;
{
}
-void VMHeap::allocateXSmallChunk()
-{
- XSmallChunk* chunk = XSmallChunk::create();
- for (auto* it = chunk->begin(); it != chunk->end(); ++it)
- m_xSmallPages.push(it);
-}
-
void VMHeap::allocateSmallChunk()
{
SmallChunk* chunk = SmallChunk::create();
#include "SegregatedFreeList.h"
#include "SmallChunk.h"
#include "Vector.h"
-#include "XSmallChunk.h"
namespace bmalloc {
public:
VMHeap();
- XSmallPage* allocateXSmallPage();
SmallPage* allocateSmallPage();
MediumPage* allocateMediumPage();
Range allocateLargeRange(size_t);
- void deallocateXSmallPage(std::unique_lock<StaticMutex>&, XSmallPage*);
void deallocateSmallPage(std::unique_lock<StaticMutex>&, SmallPage*);
void deallocateMediumPage(std::unique_lock<StaticMutex>&, MediumPage*);
void deallocateLargeRange(std::unique_lock<StaticMutex>&, Range);
private:
- void allocateXSmallChunk();
void allocateSmallChunk();
void allocateMediumChunk();
Range allocateLargeChunk();
- Vector<XSmallPage*> m_xSmallPages;
Vector<SmallPage*> m_smallPages;
Vector<MediumPage*> m_mediumPages;
SegregatedFreeList m_largeRanges;
};
-inline XSmallPage* VMHeap::allocateXSmallPage()
-{
- if (!m_xSmallPages.size())
- allocateXSmallChunk();
-
- return m_xSmallPages.pop();
-}
-
inline SmallPage* VMHeap::allocateSmallPage()
{
if (!m_smallPages.size())
return range;
}
-inline void VMHeap::deallocateXSmallPage(std::unique_lock<StaticMutex>& lock, XSmallPage* page)
-{
- lock.unlock();
- vmDeallocatePhysicalPages(page->begin()->begin(), vmPageSize);
- lock.lock();
-
- m_xSmallPages.push(page);
-}
-
inline void VMHeap::deallocateSmallPage(std::unique_lock<StaticMutex>& lock, SmallPage* page)
{
lock.unlock();
+++ /dev/null
-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef XSmallAllocator_h
-#define XSmallAllocator_h
-
-#include "BAssert.h"
-#include "XSmallChunk.h"
-
-namespace bmalloc {
-
-// Helper object for allocating XSmall objects.
-
-class XSmallAllocator {
-public:
- XSmallAllocator();
- XSmallAllocator(size_t);
-
- bool isNull() { return !m_ptr; }
- XSmallLine* line();
-
- bool canAllocate() { return !!m_remaining; }
- void* allocate();
-
- unsigned short objectCount();
- unsigned char derefCount();
- void refill(XSmallLine*);
-
-private:
- char* m_ptr;
- unsigned short m_size;
- unsigned char m_remaining;
- unsigned char m_maxObjectCount;
-};
-
-inline XSmallAllocator::XSmallAllocator()
- : m_ptr()
- , m_size()
- , m_remaining()
- , m_maxObjectCount()
-{
-}
-
-inline XSmallAllocator::XSmallAllocator(size_t size)
- : m_ptr()
- , m_size(size)
- , m_remaining()
- , m_maxObjectCount(xSmallLineSize / size)
-{
-}
-
-inline XSmallLine* XSmallAllocator::line()
-{
- return XSmallLine::get(canAllocate() ? m_ptr : m_ptr - 1);
-}
-
-inline void* XSmallAllocator::allocate()
-{
- BASSERT(m_remaining);
- BASSERT(m_size >= XSmallLine::minimumObjectSize);
-
- --m_remaining;
- char* result = m_ptr;
- m_ptr += m_size;
- BASSERT(objectType(result) == XSmall);
- return result;
-}
-
-inline unsigned short XSmallAllocator::objectCount()
-{
- return m_maxObjectCount - m_remaining;
-}
-
-inline unsigned char XSmallAllocator::derefCount()
-{
- return XSmallLine::maxRefCount - objectCount();
-}
-
-inline void XSmallAllocator::refill(XSmallLine* line)
-{
- BASSERT(!canAllocate());
- line->concurrentRef(XSmallLine::maxRefCount);
- m_ptr = line->begin();
- m_remaining = m_maxObjectCount;
-}
-
-} // namespace bmalloc
-
-#endif // XSmallAllocator_h
+++ /dev/null
-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef XSmallChunk_h
-#define XSmallChunk_h
-
-#include "Chunk.h"
-#include "XSmallLine.h"
-#include "XSmallPage.h"
-#include "XSmallTraits.h"
-
-namespace bmalloc {
-
-typedef Chunk<XSmallTraits> XSmallChunk;
-
-}; // namespace bmalloc
-
-#endif // XSmallChunk
+++ /dev/null
-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef XSmallLine_h
-#define XSmallLine_h
-
-#include "Line.h"
-#include "XSmallTraits.h"
-
-namespace bmalloc {
-
-typedef Line<XSmallTraits> XSmallLine;
-
-} // namespace bmalloc
-
-#endif // XSmallLine_h
+++ /dev/null
-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef XSmallPage_h
-#define XSmallPage_h
-
-#include "Page.h"
-#include "XSmallTraits.h"
-
-namespace bmalloc {
-
-typedef Page<XSmallTraits> XSmallPage;
-
-} // namespace bmalloc
-
-#endif // XSmallPage_h
+++ /dev/null
-/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- * notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- * notice, this list of conditions and the following disclaimer in the
- * documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
- * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
- * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
- * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
- * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
- * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- */
-
-#ifndef XSmallTraits_h
-#define XSmallTraits_h
-
-#include "Sizes.h"
-
-namespace bmalloc {
-
-template<class Traits> class Chunk;
-template<class Traits> class Line;
-template<class Traits> class Page;
-
-struct XSmallTraits {
- typedef Chunk<XSmallTraits> Chunk;
- typedef Line<XSmallTraits> Line;
- typedef Page<XSmallTraits> Page;
-
- static const size_t lineSize = xSmallLineSize;
- static const size_t minimumObjectSize = alignment;
- static const size_t chunkSize = xSmallChunkSize;
- static const size_t chunkOffset = xSmallChunkOffset;
- static const uintptr_t chunkMask = xSmallChunkMask;
-};
-
-} // namespace bmalloc
-
-#endif // XSmallTraits_h
return result;
size_t oldSize = 0;
- switch (objectType(object)) {
- case XSmall: {
- // We don't have an exact size, but we can calculate a maximum.
- void* end = roundUpToMultipleOf<xSmallLineSize>(static_cast<char*>(object) + 1);
- oldSize = static_cast<char*>(end) - static_cast<char*>(object);
- break;
- }
+ switch(objectType(object)) {
case Small: {
// We don't have an exact size, but we can calculate a maximum.
void* end = roundUpToMultipleOf<smallLineSize>(static_cast<char*>(object) + 1);