bmalloc: segregate small and large objects again, and allocate more objects on the...
[WebKit-https.git] / Source / bmalloc / bmalloc / Chunk.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 Chunk_h
27 #define Chunk_h
28
29 #include "BeginTag.h"
30 #include "EndTag.h"
31 #include "Object.h"
32 #include "ObjectType.h"
33 #include "Sizes.h"
34 #include "SmallLine.h"
35 #include "SmallPage.h"
36 #include "VMAllocate.h"
37 #include <array>
38
39 namespace bmalloc {
40
41 class Chunk {
42 public:
43     static Chunk* get(void*);
44
45     static BeginTag* beginTag(void*);
46     static EndTag* endTag(void*, size_t);
47
48     Chunk(std::lock_guard<StaticMutex>&, ObjectType);
49
50     size_t offset(void*);
51
52     char* object(size_t offset);
53     SmallPage* page(size_t offset);
54     SmallLine* line(size_t offset);
55
56     SmallLine* lines() { return m_lines.begin(); }
57     SmallPage* pages() { return m_pages.begin(); }
58
59     char* begin() { return roundUpToMultipleOf(vmPageSizePhysical(), m_memory); }
60     char* end() { return reinterpret_cast<char*>(this) + chunkSize; }
61     size_t size() { return end() - begin(); }
62
63     ObjectType objectType() { return m_objectType; }
64
65 private:
66     static const size_t boundaryTagCount = chunkSize / largeMin;
67     static_assert(boundaryTagCount > 2, "Chunk must have space for two sentinel boundary tags");
68
69     // Our metadata layout includes a left and right edge sentinel.
70     // Metadata takes up enough space to leave at least the first two
71     // boundary tag slots unused.
72     //
73     //      So, boundary tag space looks like this:
74     //
75     //          [OOXXXXX...]
76     //
77     //      And BoundaryTag::get subtracts one, producing:
78     //
79     //          [OXXXXX...O].
80     //
81     // We use the X's for boundary tags and the O's for edge sentinels.
82
83     union {
84         // The first few bytes of metadata cover the metadata region, so they're
85         // not used. We can steal them to store m_objectType.
86         ObjectType m_objectType;
87         std::array<SmallLine, chunkSize / smallLineSize> m_lines;
88     };
89
90     union {
91         // A chunk is either small or large for its lifetime, so we can union
92         // small and large metadata, and then use one or the other at runtime.
93         std::array<SmallPage, chunkSize / smallPageSize> m_pages;
94         std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
95     };
96     char m_memory[];
97 };
98
99 static_assert(sizeof(Chunk) + largeMax <= chunkSize, "largeMax is too big");
100
101 static_assert(sizeof(Chunk) / smallLineSize > sizeof(ObjectType),
102     "Chunk::m_objectType overlaps with metadata");
103
104 inline Chunk::Chunk(std::lock_guard<StaticMutex>&, ObjectType objectType)
105     : m_objectType(objectType)
106 {
107     if (objectType != ObjectType::Large)
108         return;
109
110     Range range(begin(), size());
111     BASSERT(range.size() <= largeObjectMax);
112
113     BeginTag* beginTag = Chunk::beginTag(range.begin());
114     beginTag->setRange(range);
115     beginTag->setFree(true);
116     beginTag->setVMState(VMState::Virtual);
117
118     EndTag* endTag = Chunk::endTag(range.begin(), range.size());
119     endTag->init(beginTag);
120
121     // Mark the left and right edges of our range as allocated. This naturally
122     // prevents merging logic from overflowing left (into metadata) or right
123     // (beyond our chunk), without requiring special-case checks.
124
125     EndTag* leftSentinel = beginTag->prev();
126     BASSERT(leftSentinel >= m_boundaryTags.begin());
127     BASSERT(leftSentinel < m_boundaryTags.end());
128     leftSentinel->initSentinel();
129
130     BeginTag* rightSentinel = endTag->next();
131     BASSERT(rightSentinel >= m_boundaryTags.begin());
132     BASSERT(rightSentinel < m_boundaryTags.end());
133     rightSentinel->initSentinel();
134 }
135
136 inline Chunk* Chunk::get(void* object)
137 {
138     return static_cast<Chunk*>(mask(object, chunkMask));
139 }
140
141 inline BeginTag* Chunk::beginTag(void* object)
142 {
143     Chunk* chunk = get(object);
144     size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
145     return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
146 }
147
148 inline EndTag* Chunk::endTag(void* object, size_t size)
149 {
150     Chunk* chunk = get(object);
151     char* end = static_cast<char*>(object) + size;
152
153     // We subtract largeMin before computing the end pointer's boundary tag. An
154     // object's size need not be an even multiple of largeMin. Subtracting
155     // largeMin rounds down to the last boundary tag prior to our neighbor.
156
157     size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
158     return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
159 }
160
161 inline size_t Chunk::offset(void* object)
162 {
163     BASSERT(object >= this);
164     BASSERT(object < reinterpret_cast<char*>(this) + chunkSize);
165     return static_cast<char*>(object) - reinterpret_cast<char*>(this);
166 }
167
168 inline char* Chunk::object(size_t offset)
169 {
170     return reinterpret_cast<char*>(this) + offset;
171 }
172
173 inline SmallPage* Chunk::page(size_t offset)
174 {
175     size_t pageNumber = offset / smallPageSize;
176     SmallPage* page = &m_pages[pageNumber];
177     return page - page->slide();
178 }
179
180 inline SmallLine* Chunk::line(size_t offset)
181 {
182     size_t lineNumber = offset / smallLineSize;
183     return &m_lines[lineNumber];
184 }
185
186 inline char* SmallLine::begin()
187 {
188     Chunk* chunk = Chunk::get(this);
189     size_t lineNumber = this - chunk->lines();
190     size_t offset = lineNumber * smallLineSize;
191     return &reinterpret_cast<char*>(chunk)[offset];
192 }
193
194 inline char* SmallLine::end()
195 {
196     return begin() + smallLineSize;
197 }
198
199 inline SmallLine* SmallPage::begin()
200 {
201     BASSERT(!m_slide);
202     Chunk* chunk = Chunk::get(this);
203     size_t pageNumber = this - chunk->pages();
204     size_t lineNumber = pageNumber * smallPageLineCount;
205     return &chunk->lines()[lineNumber];
206 }
207
208 inline Object::Object(void* object)
209     : m_chunk(Chunk::get(object))
210     , m_offset(m_chunk->offset(object))
211 {
212 }
213
214 inline Object::Object(Chunk* chunk, void* object)
215     : m_chunk(chunk)
216     , m_offset(m_chunk->offset(object))
217 {
218     BASSERT(chunk == Chunk::get(object));
219 }
220
221 inline char* Object::begin()
222 {
223     return m_chunk->object(m_offset);
224 }
225
226 inline SmallLine* Object::line()
227 {
228     return m_chunk->line(m_offset);
229 }
230
231 inline SmallPage* Object::page()
232 {
233     return m_chunk->page(m_offset);
234 }
235
236 }; // namespace bmalloc
237
238 #endif // Chunk