bmalloc: Use List<T> instead of Vector<T> in some places
[WebKit-https.git] / Source / bmalloc / bmalloc / SmallChunk.h
1 /*
2  * Copyright (C) 2014-2016 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 SmallChunk_h
27 #define SmallChunk_h
28
29 #include "Sizes.h"
30 #include "SmallLine.h"
31 #include "SmallPage.h"
32 #include "VMAllocate.h"
33
34 namespace bmalloc {
35
36 class SmallChunk {
37 public:
38     SmallChunk(std::lock_guard<StaticMutex>&);
39
40     static SmallChunk* get(void*);
41
42     SmallPage* begin() { return SmallPage::get(SmallLine::get(m_memory)); }
43     SmallPage* end() { return m_pages.end(); }
44     
45     SmallLine* lines() { return m_lines.begin(); }
46     SmallPage* pages() { return m_pages.begin(); }
47     
48 private:
49     std::array<SmallLine, smallChunkSize / smallLineSize> m_lines;
50     std::array<SmallPage, smallChunkSize / vmPageSize> m_pages;
51     char m_memory[] __attribute__((aligned(smallLineSize+0)));
52 };
53
54 static_assert(!(vmPageSize % smallLineSize), "vmPageSize must be an even multiple of line size");
55 static_assert(!(smallChunkSize % smallLineSize), "chunk size must be an even multiple of line size");
56 static_assert(
57     sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize,
58     "the first page of object memory in a small chunk must be able to allocate smallMax");
59
60 inline SmallChunk::SmallChunk(std::lock_guard<StaticMutex>& lock)
61 {
62     // Track the memory used for metadata by allocating imaginary objects.
63     for (SmallLine* line = m_lines.begin(); line < SmallLine::get(m_memory); ++line) {
64         line->ref(lock, 1);
65
66         SmallPage* page = SmallPage::get(line);
67         page->ref(lock);
68     }
69
70     for (SmallPage* page = begin(); page != end(); ++page)
71         page->setHasFreeLines(lock, true);
72 }
73
74 inline SmallChunk* SmallChunk::get(void* object)
75 {
76     BASSERT(isSmall(object));
77     return static_cast<SmallChunk*>(mask(object, smallChunkMask));
78 }
79
80 inline SmallLine* SmallLine::get(void* object)
81 {
82     BASSERT(isSmall(object));
83     SmallChunk* chunk = SmallChunk::get(object);
84     size_t lineNumber = (reinterpret_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / smallLineSize;
85     return &chunk->lines()[lineNumber];
86 }
87
88 inline char* SmallLine::begin()
89 {
90     SmallChunk* chunk = SmallChunk::get(this);
91     size_t lineNumber = this - chunk->lines();
92     size_t offset = lineNumber * smallLineSize;
93     return &reinterpret_cast<char*>(chunk)[offset];
94 }
95
96 inline char* SmallLine::end()
97 {
98     return begin() + smallLineSize;
99 }
100
101 inline SmallPage* SmallPage::get(SmallLine* line)
102 {
103     SmallChunk* chunk = SmallChunk::get(line);
104     size_t lineNumber = line - chunk->lines();
105     size_t pageNumber = lineNumber * smallLineSize / vmPageSize;
106     return &chunk->pages()[pageNumber];
107 }
108
109 inline SmallLine* SmallPage::begin()
110 {
111     SmallChunk* chunk = SmallChunk::get(this);
112     size_t pageNumber = this - chunk->pages();
113     size_t lineNumber = pageNumber * smallLineCount;
114     return &chunk->lines()[lineNumber];
115 }
116
117 inline SmallLine* SmallPage::end()
118 {
119     return begin() + smallLineCount;
120 }
121
122 }; // namespace bmalloc
123
124 #endif // Chunk