1 /*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "varenaalloc.h"
9 #include <algorithm>
10 #include <new>
11
end_chain(char *)12 static char* end_chain(char*) { return nullptr; }
13
first_allocated_block(uint32_t blockSize,uint32_t firstHeapAllocation)14 static uint32_t first_allocated_block(uint32_t blockSize, uint32_t firstHeapAllocation) {
15 return firstHeapAllocation > 0 ? firstHeapAllocation :
16 blockSize > 0 ? blockSize : 1024;
17 }
18
VArenaAlloc(char * block,size_t size,size_t firstHeapAllocation)19 VArenaAlloc::VArenaAlloc(char* block, size_t size, size_t firstHeapAllocation)
20 : fDtorCursor {block}
21 , fCursor {block}
22 , fEnd {block + ToU32(size)}
23 , fFirstBlock {block}
24 , fFirstSize {ToU32(size)}
25 , fFirstHeapAllocationSize {first_allocated_block(ToU32(size), ToU32(firstHeapAllocation))}
26 {
27 if (size < sizeof(Footer)) {
28 fEnd = fCursor = fDtorCursor = nullptr;
29 }
30
31 if (fCursor != nullptr) {
32 this->installFooter(end_chain, 0);
33 }
34 }
35
~VArenaAlloc()36 VArenaAlloc::~VArenaAlloc() {
37 RunDtorsOnBlock(fDtorCursor);
38 }
39
reset()40 void VArenaAlloc::reset() {
41 this->~VArenaAlloc();
42 new (this) VArenaAlloc{fFirstBlock, fFirstSize, fFirstHeapAllocationSize};
43 }
44
installFooter(FooterAction * action,uint32_t padding)45 void VArenaAlloc::installFooter(FooterAction* action, uint32_t padding) {
46 assert(padding < 64);
47 int64_t actionInt = (int64_t)(intptr_t)action;
48
49 // The top 14 bits should be either all 0s or all 1s. Check this.
50 assert((actionInt << 6) >> 6 == actionInt);
51 Footer encodedFooter = (actionInt << 6) | padding;
52 memmove(fCursor, &encodedFooter, sizeof(Footer));
53 fCursor += sizeof(Footer);
54 fDtorCursor = fCursor;
55 }
56
installPtrFooter(FooterAction * action,char * ptr,uint32_t padding)57 void VArenaAlloc::installPtrFooter(FooterAction* action, char* ptr, uint32_t padding) {
58 memmove(fCursor, &ptr, sizeof(char*));
59 fCursor += sizeof(char*);
60 this->installFooter(action, padding);
61 }
62
SkipPod(char * footerEnd)63 char* VArenaAlloc::SkipPod(char* footerEnd) {
64 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(int32_t));
65 int32_t skip;
66 memmove(&skip, objEnd, sizeof(int32_t));
67 return objEnd - skip;
68 }
69
RunDtorsOnBlock(char * footerEnd)70 void VArenaAlloc::RunDtorsOnBlock(char* footerEnd) {
71 while (footerEnd != nullptr) {
72 Footer footer;
73 memcpy(&footer, footerEnd - sizeof(Footer), sizeof(Footer));
74
75 FooterAction* action = (FooterAction*)(footer >> 6);
76 ptrdiff_t padding = footer & 63;
77
78 footerEnd = action(footerEnd) - padding;
79 }
80 }
81
NextBlock(char * footerEnd)82 char* VArenaAlloc::NextBlock(char* footerEnd) {
83 char* objEnd = footerEnd - (sizeof(Footer) + sizeof(char*));
84 char* next;
85 memmove(&next, objEnd, sizeof(char*));
86 RunDtorsOnBlock(next);
87 delete [] objEnd;
88 return nullptr;
89 }
90
installUint32Footer(FooterAction * action,uint32_t value,uint32_t padding)91 void VArenaAlloc::installUint32Footer(FooterAction* action, uint32_t value, uint32_t padding) {
92 memmove(fCursor, &value, sizeof(uint32_t));
93 fCursor += sizeof(uint32_t);
94 this->installFooter(action, padding);
95 }
96
ensureSpace(uint32_t size,uint32_t alignment)97 void VArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) {
98 constexpr uint32_t headerSize = sizeof(Footer) + sizeof(ptrdiff_t);
99 // The chrome c++ library we use does not define std::max_align_t.
100 // This must be conservative to add the right amount of extra memory to handle the alignment
101 // padding.
102 constexpr uint32_t alignof_max_align_t = 8;
103 constexpr uint32_t maxSize = std::numeric_limits<uint32_t>::max();
104 constexpr uint32_t overhead = headerSize + sizeof(Footer);
105 AssertRelease(size <= maxSize - overhead);
106 uint32_t objSizeAndOverhead = size + overhead;
107 if (alignment > alignof_max_align_t) {
108 uint32_t alignmentOverhead = alignment - 1;
109 AssertRelease(objSizeAndOverhead <= maxSize - alignmentOverhead);
110 objSizeAndOverhead += alignmentOverhead;
111 }
112
113 uint32_t minAllocationSize;
114 if (fFirstHeapAllocationSize <= maxSize / fFib0) {
115 minAllocationSize = fFirstHeapAllocationSize * fFib0;
116 fFib0 += fFib1;
117 std::swap(fFib0, fFib1);
118 } else {
119 minAllocationSize = maxSize;
120 }
121 uint32_t allocationSize = std::max(objSizeAndOverhead, minAllocationSize);
122
123 // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K
124 // heuristic is from the JEMalloc behavior.
125 {
126 uint32_t mask = allocationSize > (1 << 15) ? (1 << 12) - 1 : 16 - 1;
127 AssertRelease(allocationSize <= maxSize - mask);
128 allocationSize = (allocationSize + mask) & ~mask;
129 }
130
131 char* newBlock = new char[allocationSize];
132
133 auto previousDtor = fDtorCursor;
134 fCursor = newBlock;
135 fDtorCursor = newBlock;
136 fEnd = fCursor + allocationSize;
137 this->installPtrFooter(NextBlock, previousDtor, 0);
138 }
139
allocObjectWithFooter(uint32_t sizeIncludingFooter,uint32_t alignment)140 char* VArenaAlloc::allocObjectWithFooter(uint32_t sizeIncludingFooter, uint32_t alignment) {
141 uintptr_t mask = alignment - 1;
142
143 restart:
144 uint32_t skipOverhead = 0;
145 bool needsSkipFooter = fCursor != fDtorCursor;
146 if (needsSkipFooter) {
147 skipOverhead = sizeof(Footer) + sizeof(uint32_t);
148 }
149 char* objStart = (char*)((uintptr_t)(fCursor + skipOverhead + mask) & ~mask);
150 uint32_t totalSize = sizeIncludingFooter + skipOverhead;
151 //std::cout<<"non POD object size = "<<totalSize<<"\n";
152 if ((ptrdiff_t)totalSize > fEnd - objStart) {
153 this->ensureSpace(totalSize, alignment);
154 goto restart;
155 }
156
157 AssertRelease((ptrdiff_t)totalSize <= fEnd - objStart);
158
159 // Install a skip footer if needed, thus terminating a run of POD data. The calling code is
160 // responsible for installing the footer after the object.
161 if (needsSkipFooter) {
162 this->installUint32Footer(SkipPod, ToU32(fCursor - fDtorCursor), 0);
163 }
164
165 return objStart;
166 }
167