Unreviewed, rolling out r197955.
[WebKit-https.git] / Source / bmalloc / bmalloc / LargeChunk.h
1 /*
2  * Copyright (C) 2014 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef LargeChunk_h
27 #define LargeChunk_h
28
29 #include "BeginTag.h"
30 #include "EndTag.h"
31 #include "ObjectType.h"
32 #include "Sizes.h"
33 #include "VMAllocate.h"
34 #include <array>
35
36 namespace bmalloc {
37
38 class LargeChunk {
39 public:
40     LargeChunk();
41     static LargeChunk* get(void*);
42
43     static BeginTag* beginTag(void*);
44     static EndTag* endTag(void*, size_t);
45
46     char* begin() { return m_memory; }
47     char* end() { return reinterpret_cast<char*>(this) + largeChunkSize; }
48
49 private:
50     static const size_t boundaryTagCount = largeChunkSize / largeMin;
51     static_assert(boundaryTagCount > 2, "LargeChunk must have space for two sentinel boundary tags");
52
53     // Our metadata layout includes a left and right edge sentinel.
54     // Metadata takes up enough space to leave at least the first two
55     // boundary tag slots unused.
56     //
57     //      So, boundary tag space looks like this:
58     //
59     //          [OOXXXXX...]
60     //
61     //      And BoundaryTag::get subtracts one, producing:
62     //
63     //          [OXXXXX...O].
64     //
65     // We use the X's for boundary tags and the O's for edge sentinels.
66
67     std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
68     char m_memory[] __attribute__((aligned(largeAlignment+0)));
69 };
70
71 static_assert(largeChunkMetadataSize == sizeof(LargeChunk), "Our largeChunkMetadataSize math in Sizes.h is wrong");
72 static_assert(largeChunkMetadataSize + largeMax == largeChunkSize, "largeMax is too small or too big");
73
74 inline LargeChunk::LargeChunk()
75 {
76     Range range(begin(), end() - begin());
77     BASSERT(range.size() == largeMax);
78
79     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
80     beginTag->setRange(range);
81     beginTag->setFree(true);
82     beginTag->setVMState(VMState::Virtual);
83
84     EndTag* endTag = LargeChunk::endTag(range.begin(), range.size());
85     endTag->init(beginTag);
86
87     // Mark the left and right edges of our range as allocated. This naturally
88     // prevents merging logic from overflowing left (into metadata) or right
89     // (beyond our chunk), without requiring special-case checks.
90
91     EndTag* leftSentinel = beginTag->prev();
92     BASSERT(leftSentinel >= m_boundaryTags.begin());
93     BASSERT(leftSentinel < m_boundaryTags.end());
94     leftSentinel->initSentinel();
95
96     BeginTag* rightSentinel = endTag->next();
97     BASSERT(rightSentinel >= m_boundaryTags.begin());
98     BASSERT(rightSentinel < m_boundaryTags.end());
99     rightSentinel->initSentinel();
100 }
101
102 inline LargeChunk* LargeChunk::get(void* object)
103 {
104     BASSERT(!isSmall(object));
105     return static_cast<LargeChunk*>(mask(object, largeChunkMask));
106 }
107
108 inline BeginTag* LargeChunk::beginTag(void* object)
109 {
110     LargeChunk* chunk = get(object);
111     size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
112     return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
113 }
114
115 inline EndTag* LargeChunk::endTag(void* object, size_t size)
116 {
117     BASSERT(!isSmall(object));
118
119     LargeChunk* chunk = get(object);
120     char* end = static_cast<char*>(object) + size;
121
122     // We subtract largeMin before computing the end pointer's boundary tag. An
123     // object's size need not be an even multiple of largeMin. Subtracting
124     // largeMin rounds down to the last boundary tag prior to our neighbor.
125
126     size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
127     return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
128 }
129
130 }; // namespace bmalloc
131
132 #endif // LargeChunk