2016-03-26 Geoffrey Garen <ggaren@apple.com>
[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>&);
49
50     size_t offset(void*);
51
52     void* object(size_t offset);
53     SmallPage* page(size_t offset);
54     SmallLine* line(size_t offset);
55
56     SmallPage* pageBegin() { return Object(m_memory).page(); }
57     SmallPage* pageEnd() { return m_pages.end(); }
58     
59     SmallLine* lines() { return m_lines.begin(); }
60     SmallPage* pages() { return m_pages.begin(); }
61
62     char* begin() { return m_memory; }
63     char* end() { return reinterpret_cast<char*>(this) + chunkSize; }
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     std::array<SmallLine, chunkSize / smallLineSize> m_lines;
84     std::array<SmallPage, chunkSize / vmPageSize> m_pages;
85     std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
86     char m_memory[] __attribute__((aligned(2 * smallMax + 0)));
87 };
88
89 static_assert(sizeof(Chunk) + largeMax <= chunkSize, "largeMax is too big");
90 static_assert(
91     sizeof(Chunk) % vmPageSize + 2 * smallMax <= vmPageSize,
92     "the first page of object memory in a small chunk must be able to allocate smallMax");
93
94 inline Chunk::Chunk(std::lock_guard<StaticMutex>& lock)
95 {
96     Range range(begin(), end() - begin());
97     BASSERT(range.size() <= largeObjectMax);
98
99     BeginTag* beginTag = Chunk::beginTag(range.begin());
100     beginTag->setRange(range);
101     beginTag->setFree(true);
102     beginTag->setVMState(VMState::Virtual);
103
104     EndTag* endTag = Chunk::endTag(range.begin(), range.size());
105     endTag->init(beginTag);
106
107     // Mark the left and right edges of our range as allocated. This naturally
108     // prevents merging logic from overflowing left (into metadata) or right
109     // (beyond our chunk), without requiring special-case checks.
110
111     EndTag* leftSentinel = beginTag->prev();
112     BASSERT(leftSentinel >= m_boundaryTags.begin());
113     BASSERT(leftSentinel < m_boundaryTags.end());
114     leftSentinel->initSentinel();
115
116     BeginTag* rightSentinel = endTag->next();
117     BASSERT(rightSentinel >= m_boundaryTags.begin());
118     BASSERT(rightSentinel < m_boundaryTags.end());
119     rightSentinel->initSentinel();
120
121     // Track the memory used for metadata by allocating imaginary objects.
122     for (char* it = reinterpret_cast<char*>(this); it < m_memory; it += smallLineSize) {
123         Object object(it);
124         object.line()->ref(lock);
125         object.page()->ref(lock);
126     }
127 }
128
129 inline Chunk* Chunk::get(void* object)
130 {
131     return static_cast<Chunk*>(mask(object, chunkMask));
132 }
133
134 inline BeginTag* Chunk::beginTag(void* object)
135 {
136     Chunk* chunk = get(object);
137     size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
138     return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
139 }
140
141 inline EndTag* Chunk::endTag(void* object, size_t size)
142 {
143     Chunk* chunk = get(object);
144     char* end = static_cast<char*>(object) + size;
145
146     // We subtract largeMin before computing the end pointer's boundary tag. An
147     // object's size need not be an even multiple of largeMin. Subtracting
148     // largeMin rounds down to the last boundary tag prior to our neighbor.
149
150     size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
151     return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
152 }
153
154 inline size_t Chunk::offset(void* object)
155 {
156     BASSERT(object >= this);
157     BASSERT(object < reinterpret_cast<char*>(this) + chunkSize);
158     return static_cast<char*>(object) - reinterpret_cast<char*>(this);
159 }
160
161 inline void* Chunk::object(size_t offset)
162 {
163     return reinterpret_cast<char*>(this) + offset;
164 }
165
166 inline SmallPage* Chunk::page(size_t offset)
167 {
168     size_t pageNumber = offset / vmPageSize;
169     return &m_pages[pageNumber];
170 }
171
172 inline SmallLine* Chunk::line(size_t offset)
173 {
174     size_t lineNumber = offset / smallLineSize;
175     return &m_lines[lineNumber];
176 }
177
178 inline char* SmallLine::begin()
179 {
180     Chunk* chunk = Chunk::get(this);
181     size_t lineNumber = this - chunk->lines();
182     size_t offset = lineNumber * smallLineSize;
183     return &reinterpret_cast<char*>(chunk)[offset];
184 }
185
186 inline char* SmallLine::end()
187 {
188     return begin() + smallLineSize;
189 }
190
191 inline SmallLine* SmallPage::begin()
192 {
193     Chunk* chunk = Chunk::get(this);
194     size_t pageNumber = this - chunk->pages();
195     size_t lineNumber = pageNumber * smallLineCount;
196     return &chunk->lines()[lineNumber];
197 }
198
199 inline SmallLine* SmallPage::end()
200 {
201     return begin() + smallLineCount;
202 }
203
204 inline Object::Object(void* object)
205     : m_chunk(Chunk::get(object))
206     , m_offset(m_chunk->offset(object))
207 {
208 }
209
210 inline Object::Object(Chunk* chunk, void* object)
211     : m_chunk(chunk)
212     , m_offset(m_chunk->offset(object))
213 {
214     BASSERT(chunk == Chunk::get(object));
215 }
216
217 inline void* Object::begin()
218 {
219     return m_chunk->object(m_offset);
220 }
221
222 inline void* Object::pageBegin()
223 {
224     return m_chunk->object(roundDownToMultipleOf(vmPageSize, m_offset));
225 }
226
227 inline SmallLine* Object::line()
228 {
229     return m_chunk->line(m_offset);
230 }
231
232 inline SmallPage* Object::page()
233 {
234     return m_chunk->page(m_offset);
235 }
236
237 }; // namespace bmalloc
238
239 #endif // Chunk