9e768fc6f34a9ccef608e66aa820c019cf672d0e
[WebKit.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     // Our metadata layout includes a left and right edge sentinel.
43     // Metadata takes up enough space to leave at least the first two
44     // boundary tag slots unused.
45     //
46     //      So, boundary tag space looks like this:
47     //
48     //          [OOXXXXX...]
49     //
50     //      And BoundaryTag::get subtracts one, producing:
51     //
52     //          [OXXXXX...O].
53     //
54     // We use the X's for boundary tags and the O's for edge sentinels.
55
56     static const size_t boundaryTagCount = chunkSize / largeMin;
57     static_assert(boundaryTagCount > 2, "Chunk must have space for two sentinel boundary tags");
58
59 public:
60     static Chunk* get(void*);
61
62     static BeginTag* beginTag(void*);
63     static EndTag* endTag(void*, size_t);
64
65     Chunk(std::lock_guard<StaticMutex>&, ObjectType);
66
67     size_t offset(void*);
68
69     char* object(size_t offset);
70     SmallPage* page(size_t offset);
71     SmallLine* line(size_t offset);
72
73     char* bytes() { return reinterpret_cast<char*>(this); }
74     SmallLine* lines() { return m_lines.begin(); }
75     SmallPage* pages() { return m_pages.begin(); }
76     std::array<BoundaryTag, boundaryTagCount>& boundaryTags() { return m_boundaryTags; }
77
78     ObjectType objectType() { return m_objectType; }
79
80 private:
81     union {
82         // The first few bytes of metadata cover the metadata region, so they're
83         // not used. We can steal them to store m_objectType.
84         ObjectType m_objectType;
85         std::array<SmallLine, chunkSize / smallLineSize> m_lines;
86     };
87
88     union {
89         // A chunk is either small or large for its lifetime, so we can union
90         // small and large metadata, and then use one or the other at runtime.
91         std::array<SmallPage, chunkSize / smallPageSize> m_pages;
92         std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
93     };
94 };
95
96 static_assert(sizeof(Chunk) + largeMax <= chunkSize, "largeMax is too big");
97
98 static_assert(sizeof(Chunk) / smallLineSize > sizeof(ObjectType),
99     "Chunk::m_objectType overlaps with metadata");
100
101 inline Chunk::Chunk(std::lock_guard<StaticMutex>&, ObjectType objectType)
102     : m_objectType(objectType)
103 {
104 }
105
106 inline Chunk* Chunk::get(void* object)
107 {
108     return static_cast<Chunk*>(mask(object, chunkMask));
109 }
110
111 inline BeginTag* Chunk::beginTag(void* object)
112 {
113     Chunk* chunk = get(object);
114     size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
115     return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
116 }
117
118 inline EndTag* Chunk::endTag(void* object, size_t size)
119 {
120     Chunk* chunk = get(object);
121     char* end = static_cast<char*>(object) + size;
122
123     // We subtract largeMin before computing the end pointer's boundary tag. An
124     // object's size need not be an even multiple of largeMin. Subtracting
125     // largeMin rounds down to the last boundary tag prior to our neighbor.
126
127     size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
128     return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
129 }
130
131 inline size_t Chunk::offset(void* object)
132 {
133     BASSERT(object >= this);
134     BASSERT(object < bytes() + chunkSize);
135     return static_cast<char*>(object) - bytes();
136 }
137
138 inline char* Chunk::object(size_t offset)
139 {
140     return bytes() + offset;
141 }
142
143 inline SmallPage* Chunk::page(size_t offset)
144 {
145     size_t pageNumber = offset / smallPageSize;
146     SmallPage* page = &m_pages[pageNumber];
147     return page - page->slide();
148 }
149
150 inline SmallLine* Chunk::line(size_t offset)
151 {
152     size_t lineNumber = offset / smallLineSize;
153     return &m_lines[lineNumber];
154 }
155
156 inline char* SmallLine::begin()
157 {
158     Chunk* chunk = Chunk::get(this);
159     size_t lineNumber = this - chunk->lines();
160     size_t offset = lineNumber * smallLineSize;
161     return &reinterpret_cast<char*>(chunk)[offset];
162 }
163
164 inline char* SmallLine::end()
165 {
166     return begin() + smallLineSize;
167 }
168
169 inline SmallLine* SmallPage::begin()
170 {
171     BASSERT(!m_slide);
172     Chunk* chunk = Chunk::get(this);
173     size_t pageNumber = this - chunk->pages();
174     size_t lineNumber = pageNumber * smallPageLineCount;
175     return &chunk->lines()[lineNumber];
176 }
177
178 inline Object::Object(void* object)
179     : m_chunk(Chunk::get(object))
180     , m_offset(m_chunk->offset(object))
181 {
182 }
183
184 inline Object::Object(Chunk* chunk, void* object)
185     : m_chunk(chunk)
186     , m_offset(m_chunk->offset(object))
187 {
188     BASSERT(chunk == Chunk::get(object));
189 }
190
191 inline char* Object::begin()
192 {
193     return m_chunk->object(m_offset);
194 }
195
196 inline SmallLine* Object::line()
197 {
198     return m_chunk->line(m_offset);
199 }
200
201 inline SmallPage* Object::page()
202 {
203     return m_chunk->page(m_offset);
204 }
205
206 }; // namespace bmalloc
207
208 #endif // Chunk