bmalloc: allocate small and medium objects using the same bump pointer class
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Sep 2014 02:24:35 +0000 (02:24 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 16 Sep 2014 02:24:35 +0000 (02:24 +0000)
https://bugs.webkit.org/show_bug.cgi?id=136843

Reviewed by Gavin Barraclough.

4% speedup on MallocBench.

Now that medium-sized objects have dedicated per-size allocators, they
don't need to use an arbitrary bump pointer allocator. This means that
every allocator knows how many objects it will allocate from the start,
and we don't need a post-processing step to adjust refcounts based on
real allocation count.

* bmalloc.xcodeproj/project.pbxproj: Renamed SmallAllocator to BumpAllocator
since it's used for small and medium objects now.

* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Updated to use new interface.
(bmalloc::Allocator::scavenge): To "retire" an allocator, we just need
to make sure that we finish allocating all the objects in it.

(bmalloc::Allocator::allocateMedium):
(bmalloc::Allocator::allocateSlowCase):
(bmalloc::Allocator::retire): Deleted.
(bmalloc::Allocator::processSmallAllocatorLog): Deleted.
(bmalloc::Allocator::processMediumAllocatorLog): Deleted.
* bmalloc/Allocator.h:
(bmalloc::Allocator::allocateFastCase): Removed abstractions and data
used to post-process an allocator based on how many objects it allocated.

* bmalloc/BumpAllocator.h: Copied from Source/bmalloc/bmalloc/SmallAllocator.h.
(bmalloc::BumpAllocator::BumpAllocator):
(bmalloc::BumpAllocator::init):
(bmalloc::BumpAllocator::line):
(bmalloc::BumpAllocator::validate):
(bmalloc::BumpAllocator::allocate):
(bmalloc::BumpAllocator::refill):
(bmalloc::BumpAllocator::clear): Updated these functions to be agnostic
about the kinds of lines they allocate into. In some cases, the line
type must be provided as a template parameter by the caller.

(bmalloc::SmallAllocator::SmallAllocator): Deleted.
(bmalloc::SmallAllocator::line): Deleted.
(bmalloc::SmallAllocator::allocate): Deleted.
(bmalloc::SmallAllocator::objectCount): Deleted.
(bmalloc::SmallAllocator::derefCount): Deleted.
(bmalloc::SmallAllocator::refill): Deleted.
(bmalloc::SmallAllocator::clear): Deleted.

* bmalloc/ObjectType.h:
(bmalloc::isMedium):

* bmalloc/SmallAllocator.h:
(bmalloc::SmallAllocator::isNull): Deleted.
(bmalloc::SmallAllocator::canAllocate): Deleted.
(bmalloc::SmallAllocator::SmallAllocator): Deleted.
(bmalloc::SmallAllocator::line): Deleted.
(bmalloc::SmallAllocator::allocate): Deleted.
(bmalloc::SmallAllocator::objectCount): Deleted.
(bmalloc::SmallAllocator::derefCount): Deleted.
(bmalloc::SmallAllocator::refill): Deleted.
(bmalloc::SmallAllocator::clear): Deleted.

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

Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/BumpAllocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/ObjectType.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/SmallAllocator.h

index 5fffda4..f0ca1a1 100644 (file)
@@ -1,3 +1,68 @@
+2014-09-15  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: allocate small and medium objects using the same bump pointer class
+        https://bugs.webkit.org/show_bug.cgi?id=136843
+
+        Reviewed by Gavin Barraclough.
+
+        4% speedup on MallocBench.
+
+        Now that medium-sized objects have dedicated per-size allocators, they
+        don't need to use an arbitrary bump pointer allocator. This means that
+        every allocator knows how many objects it will allocate from the start,
+        and we don't need a post-processing step to adjust refcounts based on
+        real allocation count.
+
+        * bmalloc.xcodeproj/project.pbxproj: Renamed SmallAllocator to BumpAllocator
+        since it's used for small and medium objects now.
+
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::Allocator): Updated to use new interface.
+        (bmalloc::Allocator::scavenge): To "retire" an allocator, we just need
+        to make sure that we finish allocating all the objects in it.
+
+        (bmalloc::Allocator::allocateMedium):
+        (bmalloc::Allocator::allocateSlowCase):
+        (bmalloc::Allocator::retire): Deleted.
+        (bmalloc::Allocator::processSmallAllocatorLog): Deleted.
+        (bmalloc::Allocator::processMediumAllocatorLog): Deleted.
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::allocateFastCase): Removed abstractions and data
+        used to post-process an allocator based on how many objects it allocated.
+
+        * bmalloc/BumpAllocator.h: Copied from Source/bmalloc/bmalloc/SmallAllocator.h.
+        (bmalloc::BumpAllocator::BumpAllocator):
+        (bmalloc::BumpAllocator::init):
+        (bmalloc::BumpAllocator::line):
+        (bmalloc::BumpAllocator::validate):
+        (bmalloc::BumpAllocator::allocate):
+        (bmalloc::BumpAllocator::refill):
+        (bmalloc::BumpAllocator::clear): Updated these functions to be agnostic
+        about the kinds of lines they allocate into. In some cases, the line
+        type must be provided as a template parameter by the caller.
+
+        (bmalloc::SmallAllocator::SmallAllocator): Deleted.
+        (bmalloc::SmallAllocator::line): Deleted.
+        (bmalloc::SmallAllocator::allocate): Deleted.
+        (bmalloc::SmallAllocator::objectCount): Deleted.
+        (bmalloc::SmallAllocator::derefCount): Deleted.
+        (bmalloc::SmallAllocator::refill): Deleted.
+        (bmalloc::SmallAllocator::clear): Deleted.
+
+        * bmalloc/ObjectType.h:
+        (bmalloc::isMedium):
+
+        * bmalloc/SmallAllocator.h:
+        (bmalloc::SmallAllocator::isNull): Deleted.
+        (bmalloc::SmallAllocator::canAllocate): Deleted.
+        (bmalloc::SmallAllocator::SmallAllocator): Deleted.
+        (bmalloc::SmallAllocator::line): Deleted.
+        (bmalloc::SmallAllocator::allocate): Deleted.
+        (bmalloc::SmallAllocator::objectCount): Deleted.
+        (bmalloc::SmallAllocator::derefCount): Deleted.
+        (bmalloc::SmallAllocator::refill): Deleted.
+        (bmalloc::SmallAllocator::clear): Deleted.
+
 2014-09-12  Geoffrey Garen  <ggaren@apple.com>
 
         Fixed a goof in bmalloc Vector sizing
index e30498a..0c9485f 100644 (file)
@@ -27,7 +27,7 @@
                14DD789918F48D4A00950702 /* Cache.h in Headers */ = {isa = PBXBuildFile; fileRef = 144469E517A46BFE00F9EA1D /* Cache.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD789A18F48D4A00950702 /* Deallocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 145F685A179DC90200D65598 /* Deallocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD789B18F48D4A00950702 /* MediumAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1413E47018A0661700546D68 /* MediumAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               14DD789C18F48D4A00950702 /* SmallAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1413E462189DE1CD00546D68 /* SmallAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */ = {isa = PBXBuildFile; fileRef = 1413E462189DE1CD00546D68 /* BumpAllocator.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78B418F48D6B00950702 /* Chunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA9418CE5CA6002201E4 /* Chunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78B518F48D6B00950702 /* Line.h in Headers */ = {isa = PBXBuildFile; fileRef = 14DA32071885F9E6007269E0 /* Line.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14DD78B618F48D6B00950702 /* MediumChunk.h in Headers */ = {isa = PBXBuildFile; fileRef = 147AAA8E18CD89E3002201E4 /* MediumChunk.h */; settings = {ATTRIBUTES = (Private, ); }; };
@@ -75,7 +75,7 @@
                14105E7B18DBD7AF003A106E /* BoundaryTagInlines.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BoundaryTagInlines.h; path = bmalloc/BoundaryTagInlines.h; sourceTree = "<group>"; };
                14105E8318E14374003A106E /* ObjectType.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ObjectType.cpp; path = bmalloc/ObjectType.cpp; sourceTree = "<group>"; };
                1413E460189DCE1E00546D68 /* Inline.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = Inline.h; path = bmalloc/Inline.h; sourceTree = "<group>"; };
-               1413E462189DE1CD00546D68 /* SmallAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = SmallAllocator.h; path = bmalloc/SmallAllocator.h; sourceTree = "<group>"; };
+               1413E462189DE1CD00546D68 /* BumpAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; lineEnding = 0; name = BumpAllocator.h; path = bmalloc/BumpAllocator.h; sourceTree = "<group>"; };
                1413E468189EEDE400546D68 /* BAssert.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BAssert.h; path = bmalloc/BAssert.h; sourceTree = "<group>"; };
                1413E47018A0661700546D68 /* MediumAllocator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumAllocator.h; path = bmalloc/MediumAllocator.h; sourceTree = "<group>"; };
                1417F64518B54A700076FA3F /* BeginTag.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = BeginTag.h; path = bmalloc/BeginTag.h; sourceTree = "<group>"; };
                                145F6859179DC90200D65598 /* Deallocator.cpp */,
                                145F685A179DC90200D65598 /* Deallocator.h */,
                                1413E47018A0661700546D68 /* MediumAllocator.h */,
-                               1413E462189DE1CD00546D68 /* SmallAllocator.h */,
+                               1413E462189DE1CD00546D68 /* BumpAllocator.h */,
                        );
                        name = cache;
                        sourceTree = "<group>";
                                1400274C18F89C3D00115C97 /* SegregatedFreeList.h in Headers */,
                                14DD788D18F48CC600950702 /* BeginTag.h in Headers */,
                                14DD78CD18F48D7500950702 /* Range.h in Headers */,
-                               14DD789C18F48D4A00950702 /* SmallAllocator.h in Headers */,
+                               14DD789C18F48D4A00950702 /* BumpAllocator.h in Headers */,
                                14DD789918F48D4A00950702 /* Cache.h in Headers */,
                                14DD789B18F48D4A00950702 /* MediumAllocator.h in Headers */,
                                14DD78BE18F48D6B00950702 /* SmallTraits.h in Headers */,
index 78a2932..c498a0f 100644 (file)
@@ -37,16 +37,12 @@ namespace bmalloc {
 
 Allocator::Allocator(Deallocator& deallocator)
     : m_deallocator(deallocator)
-    , m_smallAllocators()
-    , m_mediumAllocators()
-    , m_smallAllocatorLog()
-    , m_mediumAllocatorLog()
 {
-    unsigned short size = alignment;
-    for (auto& allocator : m_smallAllocators) {
-        allocator = SmallAllocator(size);
-        size += alignment;
-    }
+    for (unsigned short i = alignment; i <= smallMax; i += alignment)
+        m_smallAllocators[smallSizeClassFor(i)].init<SmallLine>(i);
+
+    for (unsigned short i = smallMax + alignment; i <= mediumMax; i += alignment)
+        m_mediumAllocators[mediumSizeClassFor(i)].init<MediumLine>(i);
 }
 
 Allocator::~Allocator()
@@ -57,62 +53,16 @@ Allocator::~Allocator()
 void Allocator::scavenge()
 {
     for (auto& allocator : m_smallAllocators) {
-        retire(allocator);
+        while (allocator.canAllocate())
+            m_deallocator.deallocate(allocator.allocate());
         allocator.clear();
     }
-    processSmallAllocatorLog();
 
     for (auto& allocator : m_mediumAllocators) {
-        retire(allocator);
+        while (allocator.canAllocate())
+            m_deallocator.deallocate(allocator.allocate());
         allocator.clear();
     }
-    processMediumAllocatorLog();
-}
-
-void Allocator::retire(SmallAllocator& allocator)
-{
-    if (m_smallAllocatorLog.size() == m_smallAllocatorLog.capacity())
-        processSmallAllocatorLog();
-    
-    if (allocator.isNull())
-        return;
-
-    m_smallAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
-}
-
-void Allocator::processSmallAllocatorLog()
-{
-    std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-
-    for (auto& logEntry : m_smallAllocatorLog) {
-        if (!logEntry.first->deref(lock, logEntry.second))
-            continue;
-        m_deallocator.deallocateSmallLine(lock, logEntry.first);
-    }
-    m_smallAllocatorLog.clear();
-}
-
-void Allocator::retire(MediumAllocator& allocator)
-{
-    if (m_mediumAllocatorLog.size() == m_mediumAllocatorLog.capacity())
-        processMediumAllocatorLog();
-
-    if (allocator.isNull())
-        return;
-
-    m_mediumAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
-}
-
-void Allocator::processMediumAllocatorLog()
-{
-    std::lock_guard<StaticMutex> lock(PerProcess<Heap>::mutex());
-
-    for (auto& logEntry : m_mediumAllocatorLog) {
-        if (!logEntry.first->deref(lock, logEntry.second))
-            continue;
-        m_deallocator.deallocateMediumLine(lock, logEntry.first);
-    }
-    m_mediumAllocatorLog.clear();
 }
 
 void* Allocator::allocateLarge(size_t size)
@@ -131,16 +81,11 @@ void* Allocator::allocateXLarge(size_t size)
 
 void* Allocator::allocateMedium(size_t size)
 {
-    MediumAllocator& allocator = m_mediumAllocators[mediumSizeClassFor(size)];
-    size = roundUpToMultipleOf<alignment>(size);
-
-    void* object;
-    if (allocator.allocate(size, object))
-        return object;
+    BumpAllocator& allocator = m_mediumAllocators[mediumSizeClassFor(size)];
 
-    retire(allocator);
-    allocator.refill(m_deallocator.allocateMediumLine());
-    return allocator.allocate(size);
+    if (!allocator.canAllocate())
+        allocator.refill(m_deallocator.allocateMediumLine());
+    return allocator.allocate();
 }
 
 void* Allocator::allocateSlowCase(size_t size)
@@ -151,8 +96,7 @@ IF_DEBUG(
 )
     if (size <= smallMax) {
         size_t smallSizeClass = smallSizeClassFor(size);
-        SmallAllocator& allocator = m_smallAllocators[smallSizeClass];
-        retire(allocator);
+        BumpAllocator& allocator = m_smallAllocators[smallSizeClass];
         allocator.refill(m_deallocator.allocateSmallLine(smallSizeClass));
         return allocator.allocate();
     }
index 575eced..65f149a 100644 (file)
 #ifndef Allocator_h
 #define Allocator_h
 
+#include "BumpAllocator.h"
 #include "FixedVector.h"
 #include "MediumAllocator.h"
 #include "Sizes.h"
-#include "SmallAllocator.h"
+#include "SmallLine.h"
 #include <array>
 
 namespace bmalloc {
@@ -50,25 +51,16 @@ public:
     void scavenge();
 
 private:
-    void* allocateFastCase(SmallAllocator&);
+    void* allocateFastCase(BumpAllocator&);
 
     void* allocateMedium(size_t);
     void* allocateLarge(size_t);
     void* allocateXLarge(size_t);
     
-    void retire(SmallAllocator&);
-    void retire(MediumAllocator&);
-
-    void processSmallAllocatorLog();
-    void processMediumAllocatorLog();
-
     Deallocator& m_deallocator;
 
-    std::array<SmallAllocator, smallMax / alignment> m_smallAllocators;
-    std::array<MediumAllocator, mediumMax / alignment> m_mediumAllocators;
-
-    FixedVector<std::pair<SmallLine*, unsigned char>, smallAllocatorLogCapacity> m_smallAllocatorLog;
-    FixedVector<std::pair<MediumLine*, unsigned char>, mediumAllocatorLogCapacity> m_mediumAllocatorLog;
+    std::array<BumpAllocator, smallMax / alignment> m_smallAllocators;
+    std::array<BumpAllocator, mediumMax / alignment> m_mediumAllocators;
 };
 
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
@@ -76,7 +68,7 @@ inline bool Allocator::allocateFastCase(size_t size, void*& object)
     if (size > smallMax)
         return false;
 
-    SmallAllocator& allocator = m_smallAllocators[smallSizeClassFor(size)];
+    BumpAllocator& allocator = m_smallAllocators[smallSizeClassFor(size)];
     if (!allocator.canAllocate())
         return false;
 
diff --git a/Source/bmalloc/bmalloc/BumpAllocator.h b/Source/bmalloc/bmalloc/BumpAllocator.h
new file mode 100644 (file)
index 0000000..44d5c96
--- /dev/null
@@ -0,0 +1,124 @@
+/*
+ * 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 BumpAllocator_h
+#define BumpAllocator_h
+
+#include "BAssert.h"
+#include "ObjectType.h"
+
+namespace bmalloc {
+
+// Helper object for allocating small and medium objects.
+
+class BumpAllocator {
+public:
+    BumpAllocator();
+    template<typename Line> void init(size_t);
+    
+    bool isNull() { return !m_ptr; }
+    template<typename Line> Line* line();
+
+    bool canAllocate() { return !!m_remaining; }
+    void* allocate();
+
+    template<typename Line> void refill(Line*);
+    void clear();
+
+private:
+    void validate(void*);
+
+    char* m_ptr;
+    unsigned short m_size;
+    unsigned char m_remaining;
+    unsigned char m_maxObjectCount;
+};
+
+inline BumpAllocator::BumpAllocator()
+    : m_ptr()
+    , m_size()
+    , m_remaining()
+    , m_maxObjectCount()
+{
+}
+
+template<typename Line>
+inline void BumpAllocator::init(size_t size)
+{
+    BASSERT(size >= Line::minimumObjectSize);
+
+    m_ptr = nullptr;
+    m_size = size;
+    m_remaining = 0;
+    m_maxObjectCount = Line::lineSize / size;
+}
+
+template<typename Line>
+inline Line* BumpAllocator::line()
+{
+    return Line::get(canAllocate() ? m_ptr : m_ptr - 1);
+}
+
+inline void BumpAllocator::validate(void* ptr)
+{
+    UNUSED(ptr);
+    if (m_size <= smallMax) {
+        BASSERT(isSmall(ptr));
+        return;
+    }
+    
+    BASSERT(m_size <= mediumMax);
+    BASSERT(isMedium(ptr));
+}
+
+inline void* BumpAllocator::allocate()
+{
+    BASSERT(m_remaining);
+
+    --m_remaining;
+    char* result = m_ptr;
+    m_ptr += m_size;
+    validate(result);
+    return result;
+}
+
+template<typename Line>
+inline void BumpAllocator::refill(Line* line)
+{
+    BASSERT(!canAllocate());
+    line->concurrentRef(m_maxObjectCount);
+    m_ptr = line->begin();
+    m_remaining = m_maxObjectCount;
+}
+
+inline void BumpAllocator::clear()
+{
+    m_ptr = nullptr;
+    m_remaining = 0;
+}
+
+} // namespace bmalloc
+
+#endif // BumpAllocator_h
index 6558da1..8d5f744 100644 (file)
@@ -46,6 +46,11 @@ inline bool isSmall(void* smallOrMedium)
     return test(smallOrMedium, smallOrMediumSmallTypeMask);
 }
 
+inline bool isMedium(void* smallOrMedium)
+{
+    return !isSmall(smallOrMedium);
+}
+
 } // namespace bmalloc
 
 #endif // ObjectType_h
index b0c5281..ad83495 100644 (file)
@@ -86,9 +86,6 @@ namespace Sizes {
 
     static const size_t smallLineCacheCapacity = 16;
     static const size_t mediumLineCacheCapacity = 8;
-
-    static const size_t smallAllocatorLogCapacity = 16;
-    static const size_t mediumAllocatorLogCapacity = 8;
     
     static const std::chrono::milliseconds scavengeSleepDuration = std::chrono::milliseconds(512);
 
index 677f5de..e69de29 100644 (file)
@@ -1,120 +0,0 @@
-/*
- * 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 SmallAllocator_h
-#define SmallAllocator_h
-
-#include "BAssert.h"
-#include "SmallChunk.h"
-#include "SmallLine.h"
-
-namespace bmalloc {
-
-// Helper object for allocating small objects.
-
-class SmallAllocator {
-public:
-    SmallAllocator();
-    SmallAllocator(size_t);
-    
-    bool isNull() { return !m_ptr; }
-    SmallLine* line();
-
-    bool canAllocate() { return !!m_remaining; }
-    void* allocate();
-
-    unsigned short objectCount();
-    unsigned char derefCount();
-
-    void refill(SmallLine*);
-    void clear();
-
-private:
-    char* m_ptr;
-    unsigned short m_size;
-    unsigned char m_remaining;
-    unsigned char m_maxObjectCount;
-};
-
-inline SmallAllocator::SmallAllocator()
-    : m_ptr()
-    , m_size()
-    , m_remaining()
-    , m_maxObjectCount()
-{
-}
-
-inline SmallAllocator::SmallAllocator(size_t size)
-    : m_ptr()
-    , m_size(size)
-    , m_remaining()
-    , m_maxObjectCount(smallLineSize / size)
-{
-}
-
-inline SmallLine* SmallAllocator::line()
-{
-    return SmallLine::get(canAllocate() ? m_ptr : m_ptr - 1);
-}
-
-inline void* SmallAllocator::allocate()
-{
-    BASSERT(m_remaining);
-    BASSERT(m_size >= SmallLine::minimumObjectSize);
-
-    --m_remaining;
-    char* result = m_ptr;
-    m_ptr += m_size;
-    BASSERT(isSmall(result));
-    return result;
-}
-
-inline unsigned short SmallAllocator::objectCount()
-{
-    return m_maxObjectCount - m_remaining;
-}
-
-inline unsigned char SmallAllocator::derefCount()
-{
-    return SmallLine::maxRefCount - objectCount();
-}
-
-inline void SmallAllocator::refill(SmallLine* line)
-{
-    BASSERT(!canAllocate());
-    line->concurrentRef(SmallLine::maxRefCount);
-    m_ptr = line->begin();
-    m_remaining = m_maxObjectCount;
-}
-
-inline void SmallAllocator::clear()
-{
-    m_ptr = nullptr;
-    m_remaining = 0;
-}
-
-} // namespace bmalloc
-
-#endif // SmallAllocator_h