bmalloc: Added an XSmall line size
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Apr 2014 20:17:59 +0000 (20:17 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 18 Apr 2014 20:17:59 +0000 (20:17 +0000)
https://bugs.webkit.org/show_bug.cgi?id=131851

Reviewed by Sam Weinig.

Reduces malloc footprint on Membuster recordings by 10%.

This is a throughput regression, but we're still way ahead of TCMalloc.
I have some ideas for how to recover the regression -- but I wanted to
get this win in first.

Full set of benchmark results:

        bmalloc> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks --measure-heap nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/

                                                       nopatch                      patch                                Δ
        Peak Memory:
            reddit_memory_warning                      7,896kB                    7,532kB                  ^ 1.05x smaller
            flickr_memory_warning                     12,968kB                   12,324kB                  ^ 1.05x smaller
            theverge_memory_warning                   16,672kB                   15,200kB                   ^ 1.1x smaller

            <geometric mean>                          11,952kB                   11,216kB                  ^ 1.07x smaller
            <arithmetic mean>                         12,512kB                   11,685kB                  ^ 1.07x smaller
            <harmonic mean>                           11,375kB                   10,726kB                  ^ 1.06x smaller

        Memory at End:
            reddit_memory_warning                      7,320kB                    6,856kB                  ^ 1.07x smaller
            flickr_memory_warning                     10,848kB                    9,692kB                  ^ 1.12x smaller
            theverge_memory_warning                   16,380kB                   14,872kB                   ^ 1.1x smaller

            <geometric mean>                          10,916kB                    9,961kB                   ^ 1.1x smaller
            <arithmetic mean>                         11,516kB                   10,473kB                   ^ 1.1x smaller
            <harmonic mean>                           10,350kB                    9,485kB                  ^ 1.09x smaller

        MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/

                                           nopatch                patch                         Δ
        Execution Time:
            churn                            127ms                151ms            ! 1.19x slower
            list_allocate                    130ms                164ms            ! 1.26x slower
            tree_allocate                    109ms                127ms            ! 1.17x slower
            tree_churn                       115ms                120ms            ! 1.04x slower
            facebook                         240ms                259ms            ! 1.08x slower
            fragment                          91ms                131ms            ! 1.44x slower
            fragment_iterate                 105ms                106ms            ! 1.01x slower
            message_one                      260ms                259ms             ^ 1.0x faster
            message_many                     149ms                154ms            ! 1.03x slower
            medium                           194ms                248ms            ! 1.28x slower
            big                              157ms                160ms            ! 1.02x slower

            <geometric mean>                 144ms                163ms            ! 1.13x slower
            <arithmetic mean>                152ms                171ms            ! 1.12x slower
            <harmonic mean>                  137ms                156ms            ! 1.14x slower

        MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/

                                                               nopatch                          patch                                     Δ
        Execution Time:
            churn                                                126ms                          148ms                        ! 1.17x slower
            churn --parallel                                      62ms                           76ms                        ! 1.23x slower
            list_allocate                                        130ms                          164ms                        ! 1.26x slower
            list_allocate --parallel                             120ms                          175ms                        ! 1.46x slower
            tree_allocate                                        111ms                          127ms                        ! 1.14x slower
            tree_allocate --parallel                              95ms                          135ms                        ! 1.42x slower
            tree_churn                                           115ms                          124ms                        ! 1.08x slower
            tree_churn --parallel                                107ms                          126ms                        ! 1.18x slower
            facebook                                             240ms                          276ms                        ! 1.15x slower
            facebook --parallel                                  802ms                        1,088ms                        ! 1.36x slower
            fragment                                              92ms                          130ms                        ! 1.41x slower
            fragment --parallel                                   66ms                          124ms                        ! 1.88x slower
            fragment_iterate                                     109ms                          127ms                        ! 1.17x slower
            fragment_iterate --parallel                           55ms                           64ms                        ! 1.16x slower
            message_one                                          260ms                          260ms
            message_many                                         170ms                          238ms                         ! 1.4x slower
            medium                                               185ms                          250ms                        ! 1.35x slower
            medium --parallel                                    210ms                          334ms                        ! 1.59x slower
            big                                                  150ms                          169ms                        ! 1.13x slower
            big --parallel                                       138ms                          144ms                        ! 1.04x slower

            <geometric mean>                                     135ms                          170ms                        ! 1.26x slower
            <arithmetic mean>                                    167ms                          214ms                        ! 1.28x slower
            <harmonic mean>                                      117ms                          148ms                        ! 1.26x slower

        MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/

                                                            TC                      patch                                Δ
        Peak Memory:
            reddit_memory_warning                     13,836kB                   13,436kB                  ^ 1.03x smaller
            flickr_memory_warning                     24,868kB                   25,188kB                   ! 1.01x bigger
            theverge_memory_warning                   24,504kB                   26,636kB                   ! 1.09x bigger

            <geometric mean>                          20,353kB                   20,812kB                   ! 1.02x bigger
            <arithmetic mean>                         21,069kB                   21,753kB                   ! 1.03x bigger
            <harmonic mean>                           19,570kB                   19,780kB                   ! 1.01x bigger

        Memory at End:
            reddit_memory_warning                      8,656kB                   10,016kB                   ! 1.16x bigger
            flickr_memory_warning                     11,844kB                   13,784kB                   ! 1.16x bigger
            theverge_memory_warning                   18,516kB                   22,748kB                   ! 1.23x bigger

            <geometric mean>                          12,382kB                   14,644kB                   ! 1.18x bigger
            <arithmetic mean>                         13,005kB                   15,516kB                   ! 1.19x bigger
            <harmonic mean>                           11,813kB                   13,867kB                   ! 1.17x bigger

        MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/

                                                TC                patch                         Δ
        Execution Time:
            churn                            416ms                148ms            ^ 2.81x faster
            list_allocate                    463ms                164ms            ^ 2.82x faster
            tree_allocate                    292ms                127ms             ^ 2.3x faster
            tree_churn                       157ms                120ms            ^ 1.31x faster
            facebook                         327ms                276ms            ^ 1.18x faster
            fragment                         335ms                129ms             ^ 2.6x faster
            fragment_iterate                 344ms                108ms            ^ 3.19x faster
            message_one                      386ms                258ms             ^ 1.5x faster
            message_many                     410ms                154ms            ^ 2.66x faster
            medium                           391ms                245ms             ^ 1.6x faster
            big                              261ms                167ms            ^ 1.56x faster

            <geometric mean>                 332ms                164ms            ^ 2.02x faster
            <arithmetic mean>                344ms                172ms            ^ 1.99x faster
            <harmonic mean>                  317ms                157ms            ^ 2.02x faster

* bmalloc.xcodeproj/project.pbxproj:
* bmalloc/Allocator.cpp:
(bmalloc::Allocator::Allocator): Don't assume that each allocator's
index corresponds with its size. Instead, use the size selection function
explicitly. Now that we have XSmall, some small allocator entries are
unused.

(bmalloc::Allocator::scavenge):
(bmalloc::Allocator::log):
(bmalloc::Allocator::processXSmallAllocatorLog):
(bmalloc::Allocator::allocateSlowCase):
* bmalloc/Allocator.h:
(bmalloc::Allocator::xSmallAllocatorFor):
(bmalloc::Allocator::allocateFastCase):
* bmalloc/Chunk.h:
* bmalloc/Deallocator.cpp:
(bmalloc::Deallocator::scavenge):
(bmalloc::Deallocator::processObjectLog):
(bmalloc::Deallocator::deallocateSlowCase):
(bmalloc::Deallocator::deallocateXSmallLine):
(bmalloc::Deallocator::allocateXSmallLine):
* bmalloc/Deallocator.h:
(bmalloc::Deallocator::deallocateFastCase):
* bmalloc/Heap.cpp:
(bmalloc::Heap::scavenge):
(bmalloc::Heap::scavengeXSmallPages):
(bmalloc::Heap::allocateXSmallLineSlowCase):
* bmalloc/Heap.h:
(bmalloc::Heap::deallocateXSmallLine):
(bmalloc::Heap::allocateXSmallLine):
* bmalloc/LargeChunk.h:
(bmalloc::LargeChunk::get):
(bmalloc::LargeChunk::endTag):
* bmalloc/Line.h:
* bmalloc/MediumAllocator.h:
(bmalloc::MediumAllocator::allocate):
(bmalloc::MediumAllocator::refill):
* bmalloc/ObjectType.cpp:
(bmalloc::objectType):
* bmalloc/ObjectType.h:
(bmalloc::isXSmall):
(bmalloc::isSmall):
(bmalloc::isMedium):
(bmalloc::isLarge):
(bmalloc::isSmallOrMedium): Deleted.
* bmalloc/SegregatedFreeList.h: I boiler-plate copied existing code for
handling small objects. There's probably a reasonable way to share this
code in the future -- I'll look into that once it's stopped changing.

* bmalloc/Sizes.h: Tweaked size classes to make Membuster happy. This
is the main reason things got slower.

* bmalloc/SmallAllocator.h:
(bmalloc::SmallAllocator::allocate):
* bmalloc/SmallTraits.h:
* bmalloc/VMHeap.cpp:
(bmalloc::VMHeap::allocateXSmallChunk):
* bmalloc/VMHeap.h:
(bmalloc::VMHeap::allocateXSmallPage):
(bmalloc::VMHeap::deallocateXSmallPage):
* bmalloc/XSmallAllocator.h: Added.
(bmalloc::XSmallAllocator::isNull):
(bmalloc::XSmallAllocator::canAllocate):
(bmalloc::XSmallAllocator::XSmallAllocator):
(bmalloc::XSmallAllocator::line):
(bmalloc::XSmallAllocator::allocate):
(bmalloc::XSmallAllocator::objectCount):
(bmalloc::XSmallAllocator::derefCount):
(bmalloc::XSmallAllocator::refill):
* bmalloc/XSmallChunk.h: Added.
* bmalloc/XSmallLine.h: Added.
* bmalloc/XSmallPage.h: Added.
* bmalloc/XSmallTraits.h: Added.
* bmalloc/bmalloc.h:
(bmalloc::api::realloc): Boiler-plate copy, as above.

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

26 files changed:
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc.xcodeproj/project.pbxproj
Source/bmalloc/bmalloc/Allocator.cpp
Source/bmalloc/bmalloc/Allocator.h
Source/bmalloc/bmalloc/Chunk.h
Source/bmalloc/bmalloc/Deallocator.cpp
Source/bmalloc/bmalloc/Deallocator.h
Source/bmalloc/bmalloc/Heap.cpp
Source/bmalloc/bmalloc/Heap.h
Source/bmalloc/bmalloc/LargeChunk.h
Source/bmalloc/bmalloc/Line.h
Source/bmalloc/bmalloc/MediumAllocator.h
Source/bmalloc/bmalloc/ObjectType.cpp
Source/bmalloc/bmalloc/ObjectType.h
Source/bmalloc/bmalloc/SegregatedFreeList.h
Source/bmalloc/bmalloc/Sizes.h
Source/bmalloc/bmalloc/SmallAllocator.h
Source/bmalloc/bmalloc/SmallTraits.h
Source/bmalloc/bmalloc/VMHeap.cpp
Source/bmalloc/bmalloc/VMHeap.h
Source/bmalloc/bmalloc/XSmallAllocator.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XSmallChunk.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XSmallLine.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XSmallPage.h [new file with mode: 0644]
Source/bmalloc/bmalloc/XSmallTraits.h [new file with mode: 0644]
Source/bmalloc/bmalloc/bmalloc.h

index de31220..a75bc2e 100644 (file)
@@ -1,3 +1,205 @@
+2014-04-18  Geoffrey Garen  <ggaren@apple.com>
+
+        bmalloc: Added an XSmall line size
+        https://bugs.webkit.org/show_bug.cgi?id=131851
+
+        Reviewed by Sam Weinig.
+
+        Reduces malloc footprint on Membuster recordings by 10%.
+
+        This is a throughput regression, but we're still way ahead of TCMalloc.
+        I have some ideas for how to recover the regression -- but I wanted to
+        get this win in first.
+
+        Full set of benchmark results:
+
+                bmalloc> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks --measure-heap nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
+                                                                                                
+                                                               nopatch                      patch                                Δ
+                Peak Memory:
+                    reddit_memory_warning                      7,896kB                    7,532kB                  ^ 1.05x smaller
+                    flickr_memory_warning                     12,968kB                   12,324kB                  ^ 1.05x smaller
+                    theverge_memory_warning                   16,672kB                   15,200kB                   ^ 1.1x smaller
+
+                    <geometric mean>                          11,952kB                   11,216kB                  ^ 1.07x smaller
+                    <arithmetic mean>                         12,512kB                   11,685kB                  ^ 1.07x smaller
+                    <harmonic mean>                           11,375kB                   10,726kB                  ^ 1.06x smaller
+
+                Memory at End:
+                    reddit_memory_warning                      7,320kB                    6,856kB                  ^ 1.07x smaller
+                    flickr_memory_warning                     10,848kB                    9,692kB                  ^ 1.12x smaller
+                    theverge_memory_warning                   16,380kB                   14,872kB                   ^ 1.1x smaller
+
+                    <geometric mean>                          10,916kB                    9,961kB                   ^ 1.1x smaller
+                    <arithmetic mean>                         11,516kB                   10,473kB                   ^ 1.1x smaller
+                    <harmonic mean>                           10,350kB                    9,485kB                  ^ 1.09x smaller
+
+                MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
+                                                                                                
+                                                   nopatch                patch                         Δ
+                Execution Time:
+                    churn                            127ms                151ms            ! 1.19x slower
+                    list_allocate                    130ms                164ms            ! 1.26x slower
+                    tree_allocate                    109ms                127ms            ! 1.17x slower
+                    tree_churn                       115ms                120ms            ! 1.04x slower
+                    facebook                         240ms                259ms            ! 1.08x slower
+                    fragment                          91ms                131ms            ! 1.44x slower
+                    fragment_iterate                 105ms                106ms            ! 1.01x slower
+                    message_one                      260ms                259ms             ^ 1.0x faster
+                    message_many                     149ms                154ms            ! 1.03x slower
+                    medium                           194ms                248ms            ! 1.28x slower
+                    big                              157ms                160ms            ! 1.02x slower
+
+                    <geometric mean>                 144ms                163ms            ! 1.13x slower
+                    <arithmetic mean>                152ms                171ms            ! 1.12x slower
+                    <harmonic mean>                  137ms                156ms            ! 1.14x slower
+
+                MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
+                                                                                                
+                                                                       nopatch                          patch                                     Δ
+                Execution Time:
+                    churn                                                126ms                          148ms                        ! 1.17x slower
+                    churn --parallel                                      62ms                           76ms                        ! 1.23x slower
+                    list_allocate                                        130ms                          164ms                        ! 1.26x slower
+                    list_allocate --parallel                             120ms                          175ms                        ! 1.46x slower
+                    tree_allocate                                        111ms                          127ms                        ! 1.14x slower
+                    tree_allocate --parallel                              95ms                          135ms                        ! 1.42x slower
+                    tree_churn                                           115ms                          124ms                        ! 1.08x slower
+                    tree_churn --parallel                                107ms                          126ms                        ! 1.18x slower
+                    facebook                                             240ms                          276ms                        ! 1.15x slower
+                    facebook --parallel                                  802ms                        1,088ms                        ! 1.36x slower
+                    fragment                                              92ms                          130ms                        ! 1.41x slower
+                    fragment --parallel                                   66ms                          124ms                        ! 1.88x slower
+                    fragment_iterate                                     109ms                          127ms                        ! 1.17x slower
+                    fragment_iterate --parallel                           55ms                           64ms                        ! 1.16x slower
+                    message_one                                          260ms                          260ms                                      
+                    message_many                                         170ms                          238ms                         ! 1.4x slower
+                    medium                                               185ms                          250ms                        ! 1.35x slower
+                    medium --parallel                                    210ms                          334ms                        ! 1.59x slower
+                    big                                                  150ms                          169ms                        ! 1.13x slower
+                    big --parallel                                       138ms                          144ms                        ! 1.04x slower
+
+                    <geometric mean>                                     135ms                          170ms                        ! 1.26x slower
+                    <arithmetic mean>                                    167ms                          214ms                        ! 1.28x slower
+                    <harmonic mean>                                      117ms                          148ms                        ! 1.26x slower
+
+                MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
+
+                                                                    TC                      patch                                Δ
+                Peak Memory:
+                    reddit_memory_warning                     13,836kB                   13,436kB                  ^ 1.03x smaller
+                    flickr_memory_warning                     24,868kB                   25,188kB                   ! 1.01x bigger
+                    theverge_memory_warning                   24,504kB                   26,636kB                   ! 1.09x bigger
+
+                    <geometric mean>                          20,353kB                   20,812kB                   ! 1.02x bigger
+                    <arithmetic mean>                         21,069kB                   21,753kB                   ! 1.03x bigger
+                    <harmonic mean>                           19,570kB                   19,780kB                   ! 1.01x bigger
+
+                Memory at End:
+                    reddit_memory_warning                      8,656kB                   10,016kB                   ! 1.16x bigger
+                    flickr_memory_warning                     11,844kB                   13,784kB                   ! 1.16x bigger
+                    theverge_memory_warning                   18,516kB                   22,748kB                   ! 1.23x bigger
+
+                    <geometric mean>                          12,382kB                   14,644kB                   ! 1.18x bigger
+                    <arithmetic mean>                         13,005kB                   15,516kB                   ! 1.19x bigger
+                    <harmonic mean>                           11,813kB                   13,867kB                   ! 1.17x bigger
+
+                MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
+                                                                                                
+                                                        TC                patch                         Δ
+                Execution Time:
+                    churn                            416ms                148ms            ^ 2.81x faster
+                    list_allocate                    463ms                164ms            ^ 2.82x faster
+                    tree_allocate                    292ms                127ms             ^ 2.3x faster
+                    tree_churn                       157ms                120ms            ^ 1.31x faster
+                    facebook                         327ms                276ms            ^ 1.18x faster
+                    fragment                         335ms                129ms             ^ 2.6x faster
+                    fragment_iterate                 344ms                108ms            ^ 3.19x faster
+                    message_one                      386ms                258ms             ^ 1.5x faster
+                    message_many                     410ms                154ms            ^ 2.66x faster
+                    medium                           391ms                245ms             ^ 1.6x faster
+                    big                              261ms                167ms            ^ 1.56x faster
+
+                    <geometric mean>                 332ms                164ms            ^ 2.02x faster
+                    <arithmetic mean>                344ms                172ms            ^ 1.99x faster
+                    <harmonic mean>                  317ms                157ms            ^ 2.02x faster
+
+        * bmalloc.xcodeproj/project.pbxproj:
+        * bmalloc/Allocator.cpp:
+        (bmalloc::Allocator::Allocator): Don't assume that each allocator's
+        index corresponds with its size. Instead, use the size selection function
+        explicitly. Now that we have XSmall, some small allocator entries are
+        unused.
+
+        (bmalloc::Allocator::scavenge):
+        (bmalloc::Allocator::log):
+        (bmalloc::Allocator::processXSmallAllocatorLog):
+        (bmalloc::Allocator::allocateSlowCase):
+        * bmalloc/Allocator.h:
+        (bmalloc::Allocator::xSmallAllocatorFor):
+        (bmalloc::Allocator::allocateFastCase):
+        * bmalloc/Chunk.h:
+        * bmalloc/Deallocator.cpp:
+        (bmalloc::Deallocator::scavenge):
+        (bmalloc::Deallocator::processObjectLog):
+        (bmalloc::Deallocator::deallocateSlowCase):
+        (bmalloc::Deallocator::deallocateXSmallLine):
+        (bmalloc::Deallocator::allocateXSmallLine):
+        * bmalloc/Deallocator.h:
+        (bmalloc::Deallocator::deallocateFastCase):
+        * bmalloc/Heap.cpp:
+        (bmalloc::Heap::scavenge):
+        (bmalloc::Heap::scavengeXSmallPages):
+        (bmalloc::Heap::allocateXSmallLineSlowCase):
+        * bmalloc/Heap.h:
+        (bmalloc::Heap::deallocateXSmallLine):
+        (bmalloc::Heap::allocateXSmallLine):
+        * bmalloc/LargeChunk.h:
+        (bmalloc::LargeChunk::get):
+        (bmalloc::LargeChunk::endTag):
+        * bmalloc/Line.h:
+        * bmalloc/MediumAllocator.h:
+        (bmalloc::MediumAllocator::allocate):
+        (bmalloc::MediumAllocator::refill):
+        * bmalloc/ObjectType.cpp:
+        (bmalloc::objectType):
+        * bmalloc/ObjectType.h:
+        (bmalloc::isXSmall):
+        (bmalloc::isSmall):
+        (bmalloc::isMedium):
+        (bmalloc::isLarge):
+        (bmalloc::isSmallOrMedium): Deleted.
+        * bmalloc/SegregatedFreeList.h: I boiler-plate copied existing code for
+        handling small objects. There's probably a reasonable way to share this
+        code in the future -- I'll look into that once it's stopped changing.
+
+        * bmalloc/Sizes.h: Tweaked size classes to make Membuster happy. This
+        is the main reason things got slower.
+
+        * bmalloc/SmallAllocator.h:
+        (bmalloc::SmallAllocator::allocate):
+        * bmalloc/SmallTraits.h:
+        * bmalloc/VMHeap.cpp:
+        (bmalloc::VMHeap::allocateXSmallChunk):
+        * bmalloc/VMHeap.h:
+        (bmalloc::VMHeap::allocateXSmallPage):
+        (bmalloc::VMHeap::deallocateXSmallPage):
+        * bmalloc/XSmallAllocator.h: Added.
+        (bmalloc::XSmallAllocator::isNull):
+        (bmalloc::XSmallAllocator::canAllocate):
+        (bmalloc::XSmallAllocator::XSmallAllocator):
+        (bmalloc::XSmallAllocator::line):
+        (bmalloc::XSmallAllocator::allocate):
+        (bmalloc::XSmallAllocator::objectCount):
+        (bmalloc::XSmallAllocator::derefCount):
+        (bmalloc::XSmallAllocator::refill):
+        * bmalloc/XSmallChunk.h: Added.
+        * bmalloc/XSmallLine.h: Added.
+        * bmalloc/XSmallPage.h: Added.
+        * bmalloc/XSmallTraits.h: Added.
+        * bmalloc/bmalloc.h:
+        (bmalloc::api::realloc): Boiler-plate copy, as above.
+
 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
 
         MallocBench should scavenge explicitly instead of waiting
index d12271a..bf7ab5d 100644 (file)
                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 */; };
                1448C30018F3754600502839 /* mbmalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1448C2FF18F3754300502839 /* mbmalloc.cpp */; };
                1448C30118F3754C00502839 /* bmalloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 1448C2FE18F3754300502839 /* bmalloc.h */; settings = {ATTRIBUTES = (Private, ); }; };
                14C919C918FCC59F0028DB43 /* BPlatform.h in Headers */ = {isa = PBXBuildFile; fileRef = 14C919C818FCC59F0028DB43 /* BPlatform.h */; };
                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>"; };
                143E29E918CAE8BE00FE8A0F /* MediumPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = MediumPage.h; path = bmalloc/MediumPage.h; sourceTree = "<group>"; };
                143E29ED18CAE90500FE8A0F /* SmallPage.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SmallPage.h; path = bmalloc/SmallPage.h; sourceTree = "<group>"; };
                144469E417A46BFE00F9EA1D /* Cache.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; lineEnding = 0; name = Cache.cpp; path = bmalloc/Cache.cpp; sourceTree = "<group>"; xcLanguageSpecificationIdentifier = xcode.lang.cpp; };
                                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 */,
                                14DD78D118F48EC600950702 /* XLargeChunk.h in Headers */,
                                14DD78B918F48D6B00950702 /* MediumTraits.h in Headers */,
                                1448C30118F3754C00502839 /* bmalloc.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 */,
index 8433763..22ca077 100644 (file)
@@ -43,10 +43,11 @@ Allocator::Allocator(Deallocator& deallocator)
     , m_mediumAllocatorLog()
 {
     unsigned short size = alignment;
-    for (auto& allocator : m_smallAllocators) {
-        allocator = SmallAllocator(size);
-        size += alignment;
-    }
+    for ( ; size <= xSmallMax; size += alignment)
+        xSmallAllocatorFor(size) = XSmallAllocator(size);
+
+    for ( ; size <= smallMax; size += alignment)
+        smallAllocatorFor(size) = SmallAllocator(size);
 }
 
 Allocator::~Allocator()
@@ -56,6 +57,10 @@ Allocator::~Allocator()
     
 void Allocator::scavenge()
 {
+    for (auto& allocator : m_xSmallAllocators)
+        log(allocator);
+    processXSmallAllocatorLog();
+
     for (auto& allocator : m_smallAllocators)
         log(allocator);
     processSmallAllocatorLog();
@@ -64,14 +69,37 @@ void Allocator::scavenge()
     processMediumAllocatorLog();
 }
 
-void Allocator::log(SmallAllocator& allocator)
+void Allocator::log(XSmallAllocator& allocator)
 {
-    if (m_smallAllocatorLog.size() == m_smallAllocatorLog.capacity())
-        processSmallAllocatorLog();
+    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<Mutex> 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();
+    
     m_smallAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
 }
 
@@ -89,12 +117,12 @@ void Allocator::processSmallAllocatorLog()
 
 void Allocator::log(MediumAllocator& allocator)
 {
-    if (m_mediumAllocatorLog.size() == m_mediumAllocatorLog.capacity())
-        processMediumAllocatorLog();
-
     if (allocator.isNull())
         return;
 
+    if (m_mediumAllocatorLog.size() == m_mediumAllocatorLog.capacity())
+        processMediumAllocatorLog();
+
     m_mediumAllocatorLog.push(std::make_pair(allocator.line(), allocator.derefCount()));
 }
 
@@ -144,6 +172,13 @@ IF_DEBUG(
     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);
index 5e6b2a0..2cd24ed 100644 (file)
@@ -30,6 +30,7 @@
 #include "MediumAllocator.h"
 #include "Sizes.h"
 #include "SmallAllocator.h"
+#include "XSmallAllocator.h"
 #include <array>
 
 namespace bmalloc {
@@ -50,28 +51,40 @@ public:
     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);
@@ -80,15 +93,25 @@ inline SmallAllocator& Allocator::smallAllocatorFor(size_t size)
 
 inline bool Allocator::allocateFastCase(size_t size, void*& object)
 {
-    if (size > smallMax)
-        return false;
-
-    SmallAllocator& allocator = smallAllocatorFor(size);
-    if (!allocator.canAllocate())
-        return false;
-
-    object = allocator.allocate();
-    return true;
+    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;
 }
 
 inline void* Allocator::allocate(size_t size)
index b05c5ce..0d402a1 100644 (file)
@@ -77,7 +77,7 @@ inline auto Chunk<Traits>::create() -> Chunk*
 template<class Traits>
 inline auto Chunk<Traits>::get(void* object) -> Chunk*
 {
-    BASSERT(isSmallOrMedium(object));
+    BASSERT(!isLarge(object));
     return static_cast<Chunk*>(mask(object, chunkMask));
 }
 
index 991939e..6c03d35 100644 (file)
@@ -31,6 +31,7 @@
 #include "Inline.h"
 #include "PerProcess.h"
 #include "SmallChunk.h"
+#include "XSmallChunk.h"
 #include <algorithm>
 #include <sys/mman.h>
 
@@ -57,6 +58,8 @@ void Deallocator::scavenge()
     std::lock_guard<Mutex> 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())
@@ -80,13 +83,18 @@ void Deallocator::processObjectLog()
     std::lock_guard<Mutex> lock(PerProcess<Heap>::mutex());
     
     for (auto object : m_objectLog) {
-        if (isSmall(object)) {
+        if (isXSmall(object)) {
+            XSmallLine* line = XSmallLine::get(object);
+            if (!line->deref(lock))
+                continue;
+            deallocateXSmallLine(lock, line);
+        } else if (isSmall(object)) {
             SmallLine* line = SmallLine::get(object);
             if (!line->deref(lock))
                 continue;
             deallocateSmallLine(lock, line);
         } else {
-            BASSERT(isSmallOrMedium(object));
+            BASSERT(isMedium(object));
             MediumLine* line = MediumLine::get(object);
             if (!line->deref(lock))
                 continue;
@@ -104,7 +112,7 @@ void Deallocator::deallocateSlowCase(void* object)
     if (!object)
         return;
 
-    if (isSmallOrMedium(object)) {
+    if (!isLarge(object)) {
         processObjectLog();
         m_objectLog.push(object);
         return;
@@ -125,6 +133,14 @@ void Deallocator::deallocateSmallLine(std::lock_guard<Mutex>& lock, SmallLine* l
     m_smallLineCache.push(line);
 }
 
+void Deallocator::deallocateXSmallLine(std::lock_guard<Mutex>& 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()) {
@@ -138,6 +154,19 @@ SmallLine* Deallocator::allocateSmallLine()
     return m_smallLineCache.pop();
 }
 
+XSmallLine* Deallocator::allocateXSmallLine()
+{
+    if (!m_xSmallLineCache.size()) {
+        std::lock_guard<Mutex> 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<Mutex>& lock, MediumLine* line)
 {
     if (m_mediumLineCache.size() == m_mediumLineCache.capacity())
index e6987d5..df7e468 100644 (file)
@@ -30,6 +30,7 @@
 #include "MediumLine.h"
 #include "Sizes.h"
 #include "SmallLine.h"
+#include "XSmallLine.h"
 
 namespace bmalloc {
 
@@ -44,6 +45,9 @@ public:
     bool deallocateFastCase(void*);
     void deallocateSlowCase(void*);
 
+    void deallocateXSmallLine(std::lock_guard<Mutex>&, XSmallLine*);
+    XSmallLine* allocateXSmallLine();
+
     void deallocateSmallLine(std::lock_guard<Mutex>&, SmallLine*);
     SmallLine* allocateSmallLine();
 
@@ -58,13 +62,14 @@ private:
     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 (!isSmallOrMedium(object))
+    if (isLarge(object))
         return false;
 
     BASSERT(object);
index 0405501..2ea22f3 100644 (file)
@@ -32,6 +32,7 @@
 #include "PerProcess.h"
 #include "SmallChunk.h"
 #include "XLargeChunk.h"
+#include "XSmallChunk.h"
 #include <thread>
 
 namespace bmalloc {
@@ -60,6 +61,7 @@ void Heap::concurrentScavenge()
     
 void Heap::scavenge(std::unique_lock<Mutex>& lock, std::chrono::milliseconds sleepDuration)
 {
+    scavengeXSmallPages(lock, sleepDuration);
     scavengeSmallPages(lock, sleepDuration);
     scavengeMediumPages(lock, sleepDuration);
     scavengeLargeRanges(lock, sleepDuration);
@@ -83,6 +85,22 @@ void Heap::scavengeSmallPages(std::unique_lock<Mutex>& lock, std::chrono::millis
     }
 }
 
+void Heap::scavengeXSmallPages(std::unique_lock<Mutex>& 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<Mutex>& lock, std::chrono::milliseconds sleepDuration)
 {
     while (1) {
@@ -116,6 +134,27 @@ void Heap::scavengeLargeRanges(std::unique_lock<Mutex>& lock, std::chrono::milli
     }
 }
 
+XSmallLine* Heap::allocateXSmallLineSlowCase(std::lock_guard<Mutex>& 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<Mutex>& lock)
 {
     m_isAllocatingPages = true;
index 6c5c5cd..918350b 100644 (file)
 
 #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>
 
@@ -49,6 +46,9 @@ class Heap {
 public:
     Heap(std::lock_guard<Mutex>&);
     
+    XSmallLine* allocateXSmallLine(std::lock_guard<Mutex>&);
+    void deallocateXSmallLine(std::lock_guard<Mutex>&, XSmallLine*);
+
     SmallLine* allocateSmallLine(std::lock_guard<Mutex>&);
     void deallocateSmallLine(std::lock_guard<Mutex>&, SmallLine*);
 
@@ -66,6 +66,7 @@ public:
 private:
     ~Heap() = delete;
 
+    XSmallLine* allocateXSmallLineSlowCase(std::lock_guard<Mutex>&);
     SmallLine* allocateSmallLineSlowCase(std::lock_guard<Mutex>&);
     MediumLine* allocateMediumLineSlowCase(std::lock_guard<Mutex>&);
 
@@ -78,13 +79,16 @@ private:
     void mergeLargeRight(EndTag*&, BeginTag*&, Range&, bool& hasPhysicalPages);
     
     void concurrentScavenge();
+    void scavengeXSmallPages(std::unique_lock<Mutex>&, std::chrono::milliseconds);
     void scavengeSmallPages(std::unique_lock<Mutex>&, std::chrono::milliseconds);
     void scavengeMediumPages(std::unique_lock<Mutex>&, std::chrono::milliseconds);
     void scavengeLargeRanges(std::unique_lock<Mutex>&, 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;
 
@@ -96,6 +100,31 @@ private:
     AsyncTask<Heap, decltype(&Heap::concurrentScavenge)> m_scavenger;
 };
 
+inline void Heap::deallocateXSmallLine(std::lock_guard<Mutex>& 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<Mutex>& 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<Mutex>& lock, SmallLine* line)
 {
     SmallPage* page = SmallPage::get(line);
index c011e76..985ba76 100644 (file)
@@ -76,7 +76,7 @@ inline LargeChunk* LargeChunk::create()
 
 inline LargeChunk* LargeChunk::get(void* object)
 {
-    BASSERT(!isSmallOrMedium(object));
+    BASSERT(isLarge(object));
     return static_cast<LargeChunk*>(mask(object, largeChunkMask));
 }
 
@@ -89,7 +89,7 @@ inline BeginTag* LargeChunk::beginTag(void* object)
 
 inline EndTag* LargeChunk::endTag(void* object, size_t size)
 {
-    BASSERT(!isSmallOrMedium(object));
+    BASSERT(isLarge(object));
 
     LargeChunk* chunk = get(object);
     char* end = static_cast<char*>(object) + size;
index 2145edd..2f8e378 100644 (file)
@@ -58,7 +58,7 @@ private:
 template<class Traits>
 inline auto Line<Traits>::get(void* object) -> Line*
 {
-    BASSERT(isSmallOrMedium(object));
+    BASSERT(!isLarge(object));
     Chunk* chunk = Chunk::get(object);
     size_t lineNumber = (reinterpret_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / lineSize;
     return &chunk->lines()[lineNumber];
index a4bf938..a82b33c 100644 (file)
@@ -73,7 +73,7 @@ inline void* MediumAllocator::allocate(size_t size)
 
     m_remaining -= size;
     void* object = m_end - m_remaining - size;
-    BASSERT(isSmallOrMedium(object) && !isSmall(object));
+    BASSERT(objectType(object) == Medium);
 
     ++m_objectCount;
     return object;
@@ -99,6 +99,7 @@ inline void MediumAllocator::refill(MediumLine* line)
     m_end = line->end();
     m_remaining = mediumLineSize;
     m_objectCount = 0;
+    BASSERT(objectType(m_end - 1) == Medium);
 }
 
 } // namespace bmalloc
index df8c900..ca176dd 100644 (file)
@@ -30,16 +30,27 @@ namespace bmalloc {
 
 ObjectType objectType(void* object)
 {
-    if (isSmallOrMedium(object)) {
-        if (isSmall(object))
-            return Small;
+    switch (mask(reinterpret_cast<uintptr_t>(object), typeMask)) {
+    case xSmallType: {
+        return XSmall;
+    }
+    case smallType: {
+        return Small;
+    }
+    case mediumType: {
         return Medium;
     }
-    
-    BeginTag* beginTag = LargeChunk::beginTag(object);
-    if (!beginTag->isXLarge())
-        return Large;
-    return XLarge;
+    case largeType: {
+        BeginTag* beginTag = LargeChunk::beginTag(object);
+        if (!beginTag->isXLarge())
+            return Large;
+        return XLarge;
+    }
+    default: {
+        RELEASE_BASSERT(false);
+        return XLarge;
+    }
+    }
 }
 
 } // namespace bmalloc
index 6558da1..f72f30d 100644 (file)
 
 namespace bmalloc {
 
-enum ObjectType { Small, Medium, Large, XLarge };
+enum ObjectType { XSmall, Small, Medium, Large, XLarge };
 
 ObjectType objectType(void*);
 
-inline bool isSmallOrMedium(void* object)
+inline bool isXSmall(void* object)
 {
-    return test(object, smallOrMediumTypeMask);
+    return mask(reinterpret_cast<uintptr_t>(object), typeMask) == xSmallType;
 }
 
-inline bool isSmall(void* smallOrMedium)
+inline bool isSmall(void* object)
 {
-    BASSERT(isSmallOrMedium(smallOrMedium));
-    return test(smallOrMedium, smallOrMediumSmallTypeMask);
+    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;
 }
 
 } // namespace bmalloc
index be8ef95..0572c23 100644 (file)
@@ -58,7 +58,7 @@ private:
     Range take(List&, size_t);
     Range takeGreedy(List&, size_t);
 
-    std::array<List, 19> m_lists;
+    std::array<List, 18> m_lists;
 };
 
 } // namespace bmalloc
index 035da50..60bafb4 100644 (file)
@@ -47,44 +47,53 @@ namespace Sizes {
 
     static const size_t superChunkSize = 32 * MB;
 
-    static const size_t smallMax = 256;
-    static const size_t smallLineSize = 512;
+    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 smallLineMask = ~(smallLineSize - 1ul);
 
     static const size_t smallChunkSize = superChunkSize / 4;
-    static const size_t smallChunkOffset = superChunkSize * 3 / 4;
+    static const size_t smallChunkOffset = superChunkSize * 2 / 4;
     static const size_t smallChunkMask = ~(smallChunkSize - 1ul);
 
-    static const size_t mediumMax = 1024;
-    static const size_t mediumLineSize = 2048;
+    static const size_t mediumMax = 256;
+    static const size_t mediumLineSize = 512;
     static const size_t mediumLineMask = ~(mediumLineSize - 1ul);
 
     static const size_t mediumChunkSize = superChunkSize / 4;
-    static const size_t mediumChunkOffset = superChunkSize * 2 / 4;
+    static const size_t mediumChunkOffset = superChunkSize * 3 / 4;
     static const size_t mediumChunkMask = ~(mediumChunkSize - 1ul);
 
-    static const size_t largeChunkSize = superChunkSize / 2;
-    static const size_t largeChunkOffset = 0;
+    static const size_t largeChunkSize = superChunkSize / 4;
+    static const size_t largeChunkOffset = superChunkSize * 0 / 4;
     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 = 1024;
+    static const size_t largeMin = mediumMax;
 
     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 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 uintptr_t largeType = (superChunkSize + largeChunkOffset) & typeMask;
+    
     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;
     
index 842bf05..bbfe78b 100644 (file)
@@ -28,7 +28,6 @@
 
 #include "BAssert.h"
 #include "SmallChunk.h"
-#include "SmallLine.h"
 
 namespace bmalloc {
 
@@ -85,7 +84,7 @@ inline void* SmallAllocator::allocate()
     --m_remaining;
     char* result = m_ptr;
     m_ptr += m_size;
-    BASSERT(isSmall(result));
+    BASSERT(objectType(result) == Small);
     return result;
 }
 
index e40c166..318abeb 100644 (file)
@@ -40,7 +40,7 @@ struct SmallTraits {
     typedef Page<SmallTraits> Page;
 
     static const size_t lineSize = smallLineSize;
-    static const size_t minimumObjectSize = alignment;
+    static const size_t minimumObjectSize = xSmallMax + alignment;
     static const size_t chunkSize = smallChunkSize;
     static const size_t chunkOffset = smallChunkOffset;
     static const uintptr_t chunkMask = smallChunkMask;
index 4464bd1..50629e0 100644 (file)
@@ -36,6 +36,13 @@ VMHeap::VMHeap()
 {
 }
 
+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();
index f6f6f73..9702276 100644 (file)
@@ -34,6 +34,7 @@
 #include "SegregatedFreeList.h"
 #include "SmallChunk.h"
 #include "Vector.h"
+#include "XSmallChunk.h"
 
 namespace bmalloc {
 
@@ -45,24 +46,36 @@ class VMHeap {
 public:
     VMHeap();
 
+    XSmallPage* allocateXSmallPage();
     SmallPage* allocateSmallPage();
     MediumPage* allocateMediumPage();
     Range allocateLargeRange(size_t);
 
+    void deallocateXSmallPage(std::unique_lock<Mutex>&, XSmallPage*);
     void deallocateSmallPage(std::unique_lock<Mutex>&, SmallPage*);
     void deallocateMediumPage(std::unique_lock<Mutex>&, MediumPage*);
     void deallocateLargeRange(std::unique_lock<Mutex>&, 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())
@@ -87,6 +100,15 @@ inline Range VMHeap::allocateLargeRange(size_t size)
     return range;
 }
 
+inline void VMHeap::deallocateXSmallPage(std::unique_lock<Mutex>& lock, XSmallPage* page)
+{
+    lock.unlock();
+    vmDeallocatePhysicalPages(page->begin()->begin(), vmPageSize);
+    lock.lock();
+    
+    m_xSmallPages.push(page);
+}
+
 inline void VMHeap::deallocateSmallPage(std::unique_lock<Mutex>& lock, SmallPage* page)
 {
     lock.unlock();
diff --git a/Source/bmalloc/bmalloc/XSmallAllocator.h b/Source/bmalloc/bmalloc/XSmallAllocator.h
new file mode 100644 (file)
index 0000000..85bb1b1
--- /dev/null
@@ -0,0 +1,111 @@
+/*
+ * 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
diff --git a/Source/bmalloc/bmalloc/XSmallChunk.h b/Source/bmalloc/bmalloc/XSmallChunk.h
new file mode 100644 (file)
index 0000000..d8ebc3d
--- /dev/null
@@ -0,0 +1,40 @@
+/*
+ * 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
diff --git a/Source/bmalloc/bmalloc/XSmallLine.h b/Source/bmalloc/bmalloc/XSmallLine.h
new file mode 100644 (file)
index 0000000..5ae6806
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * 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
diff --git a/Source/bmalloc/bmalloc/XSmallPage.h b/Source/bmalloc/bmalloc/XSmallPage.h
new file mode 100644 (file)
index 0000000..c231c03
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * 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
diff --git a/Source/bmalloc/bmalloc/XSmallTraits.h b/Source/bmalloc/bmalloc/XSmallTraits.h
new file mode 100644 (file)
index 0000000..3532540
--- /dev/null
@@ -0,0 +1,51 @@
+/*
+ * 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
index b322437..8b927bc 100644 (file)
@@ -50,7 +50,13 @@ inline void* realloc(void* object, size_t newSize)
         return result;
 
     size_t oldSize = 0;
-    switch(objectType(object)) {
+    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;
+    }
     case Small: {
         // We don't have an exact size, but we can calculate a maximum.
         void* end = roundUpToMultipleOf<smallLineSize>(static_cast<char*>(object) + 1);