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 "Object.h"
30#include "Sizes.h"
31#include "SmallLine.h"
32#include "SmallPage.h"
33#include "VMAllocate.h"
34#include <array>
35
36namespace bmalloc {
37
38class Chunk : public ListNode<Chunk> {
39public:
40 static Chunk* get(void*);
41
42 Chunk(size_t pageSize);
43
44 void ref() { ++m_refCount; }
45 void deref() { BASSERT(m_refCount); --m_refCount; }
46 unsigned refCount() { return m_refCount; }
47
48 size_t offset(void*);
49
50 char* address(size_t offset);
51 SmallPage* page(size_t offset);
52 SmallLine* line(size_t offset);
53
54 char* bytes() { return reinterpret_cast<char*>(this); }
55 SmallLine* lines() { return &m_lines[0]; }
56 SmallPage* pages() { return &m_pages[0]; }
57
58 List<SmallPage>& freePages() { return m_freePages; }
59
60private:
61 size_t m_refCount { };
62 List<SmallPage> m_freePages { };
63
64 std::array<SmallLine, chunkSize / smallLineSize> m_lines { };
65 std::array<SmallPage, chunkSize / smallPageSize> m_pages { };
66};
67
68struct ChunkHash {
69 static unsigned hash(Chunk* key)
70 {
71 return static_cast<unsigned>(
72 reinterpret_cast<uintptr_t>(key) / chunkSize);
73 }
74};
75
76template<typename Function> void forEachPage(Chunk* chunk, size_t pageSize, Function function)
77{
78 // We align to at least the page size so we can service aligned allocations
79 // at equal and smaller powers of two, and also so we can vmDeallocatePhysicalPages().
80 size_t metadataSize = roundUpToMultipleOfNonPowerOfTwo(pageSize, sizeof(Chunk));
81
82 Object begin(chunk, metadataSize);
83 Object end(chunk, chunkSize);
84
85 for (auto it = begin; it + pageSize <= end; it = it + pageSize)
86 function(it.page());
87}
88
89inline Chunk::Chunk(size_t pageSize)
90{
91 size_t smallPageCount = pageSize / smallPageSize;
92 forEachPage(this, pageSize, [&](SmallPage* page) {
93 for (size_t i = 0; i < smallPageCount; ++i)
94 page[i].setSlide(i);
95 });
96}
97
98inline Chunk* Chunk::get(void* address)
99{
100 return static_cast<Chunk*>(mask(address, chunkMask));
101}
102
103inline size_t Chunk::offset(void* address)
104{
105 BASSERT(address >= this);
106 BASSERT(address < bytes() + chunkSize);
107 return static_cast<char*>(address) - bytes();
108}
109
110inline char* Chunk::address(size_t offset)
111{
112 return bytes() + offset;
113}
114
115inline SmallPage* Chunk::page(size_t offset)
116{
117 size_t pageNumber = offset / smallPageSize;
118 SmallPage* page = &m_pages[pageNumber];
119 return page - page->slide();
120}
121
122inline SmallLine* Chunk::line(size_t offset)
123{
124 size_t lineNumber = offset / smallLineSize;
125 return &m_lines[lineNumber];
126}
127
128inline char* SmallLine::begin()
129{
130 Chunk* chunk = Chunk::get(this);
131 size_t lineNumber = this - chunk->lines();
132 size_t offset = lineNumber * smallLineSize;
133 return &reinterpret_cast<char*>(chunk)[offset];
134}
135
136inline char* SmallLine::end()
137{
138 return begin() + smallLineSize;
139}
140
141inline SmallLine* SmallPage::begin()
142{
143 BASSERT(!m_slide);
144 Chunk* chunk = Chunk::get(this);
145 size_t pageNumber = this - chunk->pages();
146 size_t lineNumber = pageNumber * smallPageLineCount;
147 return &chunk->lines()[lineNumber];
148}
149
150inline Object::Object(void* object)
151 : m_chunk(Chunk::get(object))
152 , m_offset(m_chunk->offset(object))
153{
154}
155
156inline Object::Object(Chunk* chunk, void* object)
157 : m_chunk(chunk)
158 , m_offset(m_chunk->offset(object))
159{
160 BASSERT(chunk == Chunk::get(object));
161}
162
163inline char* Object::address()
164{
165 return m_chunk->address(m_offset);
166}
167
168inline SmallLine* Object::line()
169{
170 return m_chunk->line(m_offset);
171}
172
173inline SmallPage* Object::page()
174{
175 return m_chunk->page(m_offset);
176}
177
178}; // namespace bmalloc
179
180#endif // Chunk
181