1 // Copyright 2014 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7 #include <algorithm>
8
9 #include "xfa/src/fgas/src/fgas_base.h"
10 #include "fx_memory.h"
11 #define FX_4BYTEALIGN(size) (((size) + 3) / 4 * 4)
FX_CreateAllocator(FX_ALLOCTYPE eType,size_t chunkSize,size_t blockSize)12 IFX_MEMAllocator* FX_CreateAllocator(FX_ALLOCTYPE eType,
13 size_t chunkSize,
14 size_t blockSize) {
15 switch (eType) {
16 #ifndef _FXEMB
17 case FX_ALLOCTYPE_Dynamic:
18 return new CFX_DynamicStore(chunkSize);
19 #endif
20 case FX_ALLOCTYPE_Default:
21 return new CFX_DefStore();
22 case FX_ALLOCTYPE_Static:
23 return new CFX_StaticStore(chunkSize);
24 case FX_ALLOCTYPE_Fixed:
25 return new CFX_FixedStore(blockSize, chunkSize);
26 default:
27 return NULL;
28 }
29 }
CFX_StaticStore(size_t iDefChunkSize)30 CFX_StaticStore::CFX_StaticStore(size_t iDefChunkSize)
31 : m_iAllocatedSize(0),
32 m_iDefChunkSize(iDefChunkSize),
33 m_pChunk(NULL),
34 m_pLastChunk(NULL) {
35 FXSYS_assert(m_iDefChunkSize != 0);
36 }
~CFX_StaticStore()37 CFX_StaticStore::~CFX_StaticStore() {
38 FX_LPSTATICSTORECHUNK pChunk, pNext;
39 pChunk = m_pChunk;
40 while (pChunk != NULL) {
41 pNext = pChunk->pNextChunk;
42 FX_Free(pChunk);
43 pChunk = pNext;
44 }
45 }
AllocChunk(size_t size)46 FX_LPSTATICSTORECHUNK CFX_StaticStore::AllocChunk(size_t size) {
47 FXSYS_assert(size != 0);
48 FX_LPSTATICSTORECHUNK pChunk = (FX_LPSTATICSTORECHUNK)FX_Alloc(
49 uint8_t, sizeof(FX_STATICSTORECHUNK) + size);
50 pChunk->iChunkSize = size;
51 pChunk->iFreeSize = size;
52 pChunk->pNextChunk = NULL;
53 if (m_pLastChunk == NULL) {
54 m_pChunk = pChunk;
55 } else {
56 m_pLastChunk->pNextChunk = pChunk;
57 }
58 m_pLastChunk = pChunk;
59 return pChunk;
60 }
FindChunk(size_t size)61 FX_LPSTATICSTORECHUNK CFX_StaticStore::FindChunk(size_t size) {
62 FXSYS_assert(size != 0);
63 if (m_pLastChunk == NULL || m_pLastChunk->iFreeSize < size) {
64 return AllocChunk(std::max(m_iDefChunkSize, size));
65 }
66 return m_pLastChunk;
67 }
Alloc(size_t size)68 void* CFX_StaticStore::Alloc(size_t size) {
69 size = FX_4BYTEALIGN(size);
70 FXSYS_assert(size != 0);
71 FX_LPSTATICSTORECHUNK pChunk = FindChunk(size);
72 FXSYS_assert(pChunk != NULL && pChunk->iFreeSize >= size);
73 uint8_t* p = (uint8_t*)pChunk;
74 p += sizeof(FX_STATICSTORECHUNK) + pChunk->iChunkSize - pChunk->iFreeSize;
75 pChunk->iFreeSize -= size;
76 m_iAllocatedSize += size;
77 return p;
78 }
SetDefChunkSize(size_t size)79 size_t CFX_StaticStore::SetDefChunkSize(size_t size) {
80 FXSYS_assert(size != 0);
81 size_t v = m_iDefChunkSize;
82 m_iDefChunkSize = size;
83 return v;
84 }
CFX_FixedStore(size_t iBlockSize,size_t iBlockNumsInChunk)85 CFX_FixedStore::CFX_FixedStore(size_t iBlockSize, size_t iBlockNumsInChunk)
86 : m_iBlockSize(FX_4BYTEALIGN(iBlockSize)),
87 m_iDefChunkSize(FX_4BYTEALIGN(iBlockNumsInChunk)),
88 m_pChunk(NULL) {
89 FXSYS_assert(m_iBlockSize != 0 && m_iDefChunkSize != 0);
90 }
~CFX_FixedStore()91 CFX_FixedStore::~CFX_FixedStore() {
92 FX_LPFIXEDSTORECHUNK pChunk, pNext;
93 pChunk = m_pChunk;
94 while (pChunk != NULL) {
95 pNext = pChunk->pNextChunk;
96 FX_Free(pChunk);
97 pChunk = pNext;
98 }
99 }
AllocChunk()100 FX_LPFIXEDSTORECHUNK CFX_FixedStore::AllocChunk() {
101 int32_t iTotalSize = sizeof(FX_FIXEDSTORECHUNK) + m_iDefChunkSize +
102 m_iBlockSize * m_iDefChunkSize;
103 FX_LPFIXEDSTORECHUNK pChunk =
104 (FX_LPFIXEDSTORECHUNK)FX_Alloc(uint8_t, iTotalSize);
105 if (pChunk == NULL) {
106 return NULL;
107 }
108 FXSYS_memset(pChunk->FirstFlag(), 0, m_iDefChunkSize);
109 pChunk->pNextChunk = m_pChunk;
110 pChunk->iChunkSize = m_iDefChunkSize;
111 pChunk->iFreeNum = m_iDefChunkSize;
112 m_pChunk = pChunk;
113 return pChunk;
114 }
Alloc(size_t size)115 void* CFX_FixedStore::Alloc(size_t size) {
116 if (size > m_iBlockSize) {
117 return NULL;
118 }
119 FX_LPFIXEDSTORECHUNK pChunk = m_pChunk;
120 while (pChunk != NULL) {
121 if (pChunk->iFreeNum > 0) {
122 break;
123 }
124 pChunk = pChunk->pNextChunk;
125 }
126 if (pChunk == NULL) {
127 pChunk = AllocChunk();
128 }
129 FXSYS_assert(pChunk != NULL);
130 uint8_t* pFlags = pChunk->FirstFlag();
131 size_t i = 0;
132 for (; i < pChunk->iChunkSize; i++)
133 if (pFlags[i] == 0) {
134 break;
135 }
136 FXSYS_assert(i < pChunk->iChunkSize);
137 pFlags[i] = 1;
138 pChunk->iFreeNum--;
139 return pChunk->FirstBlock() + i * m_iBlockSize;
140 }
Free(void * pBlock)141 void CFX_FixedStore::Free(void* pBlock) {
142 FXSYS_assert(pBlock != NULL);
143 FX_LPFIXEDSTORECHUNK pPrior, pChunk;
144 pPrior = NULL, pChunk = m_pChunk;
145 uint8_t* pStart = NULL;
146 uint8_t* pEnd;
147 while (pChunk != NULL) {
148 pStart = pChunk->FirstBlock();
149 if (pBlock >= pStart) {
150 pEnd = pStart + m_iBlockSize * pChunk->iChunkSize;
151 if (pBlock < pEnd) {
152 break;
153 }
154 }
155 pPrior = pChunk, pChunk = pChunk->pNextChunk;
156 }
157 FXSYS_assert(pChunk != NULL);
158 size_t iPos = ((uint8_t*)pBlock - pStart) / m_iBlockSize;
159 FXSYS_assert(iPos < pChunk->iChunkSize);
160 uint8_t* pFlags = pChunk->FirstFlag();
161 if (pFlags[iPos] == 0) {
162 return;
163 }
164 pFlags[iPos] = 0;
165 pChunk->iFreeNum++;
166 if (pChunk->iFreeNum == pChunk->iChunkSize) {
167 if (pPrior == NULL) {
168 m_pChunk = pChunk->pNextChunk;
169 } else {
170 pPrior->pNextChunk = pChunk->pNextChunk;
171 }
172 FX_Free(pChunk);
173 }
174 }
SetDefChunkSize(size_t iChunkSize)175 size_t CFX_FixedStore::SetDefChunkSize(size_t iChunkSize) {
176 FXSYS_assert(iChunkSize != 0);
177 size_t v = m_iDefChunkSize;
178 m_iDefChunkSize = FX_4BYTEALIGN(iChunkSize);
179 return v;
180 }
181 #ifndef _FXEMB
CFX_DynamicStore(size_t iDefChunkSize)182 CFX_DynamicStore::CFX_DynamicStore(size_t iDefChunkSize)
183 : m_iDefChunkSize(iDefChunkSize), m_pChunk(NULL) {
184 FXSYS_assert(m_iDefChunkSize != 0);
185 }
~CFX_DynamicStore()186 CFX_DynamicStore::~CFX_DynamicStore() {
187 FX_LPDYNAMICSTORECHUNK pChunk, pNext;
188 pChunk = m_pChunk;
189 while (pChunk != NULL) {
190 pNext = pChunk->pNextChunk;
191 FX_Free(pChunk);
192 pChunk = pNext;
193 }
194 }
AllocChunk(size_t size)195 FX_LPDYNAMICSTORECHUNK CFX_DynamicStore::AllocChunk(size_t size) {
196 FXSYS_assert(size != 0);
197 FX_LPDYNAMICSTORECHUNK pChunk = (FX_LPDYNAMICSTORECHUNK)FX_Alloc(
198 uint8_t,
199 sizeof(FX_DYNAMICSTORECHUNK) + sizeof(FX_DYNAMICSTOREBLOCK) * 2 + size);
200 if (pChunk == NULL) {
201 return NULL;
202 }
203 pChunk->iChunkSize = size;
204 pChunk->iFreeSize = size;
205 FX_LPDYNAMICSTOREBLOCK pBlock = pChunk->FirstBlock();
206 pBlock->iBlockSize = size;
207 pBlock->bUsed = FALSE;
208 pBlock = pBlock->NextBlock();
209 pBlock->iBlockSize = 0;
210 pBlock->bUsed = TRUE;
211 if (m_pChunk != NULL && size >= m_iDefChunkSize) {
212 FX_LPDYNAMICSTORECHUNK pLast = m_pChunk;
213 while (pLast->pNextChunk != NULL) {
214 pLast = pLast->pNextChunk;
215 }
216 pLast->pNextChunk = pChunk;
217 pChunk->pNextChunk = NULL;
218 } else {
219 pChunk->pNextChunk = m_pChunk;
220 m_pChunk = pChunk;
221 }
222 return pChunk;
223 }
Alloc(size_t size)224 void* CFX_DynamicStore::Alloc(size_t size) {
225 size = FX_4BYTEALIGN(size);
226 FXSYS_assert(size != 0);
227 FX_LPDYNAMICSTORECHUNK pChunk = m_pChunk;
228 FX_LPDYNAMICSTOREBLOCK pBlock = NULL;
229 while (pChunk != NULL) {
230 if (pChunk->iFreeSize >= size) {
231 pBlock = pChunk->FirstBlock();
232 FX_BOOL bFind = FALSE;
233 while (pBlock->iBlockSize != 0) {
234 if (!pBlock->bUsed && pBlock->iBlockSize >= size) {
235 bFind = TRUE;
236 break;
237 }
238 pBlock = pBlock->NextBlock();
239 }
240 if (bFind) {
241 break;
242 }
243 }
244 pChunk = pChunk->pNextChunk;
245 }
246 if (pChunk == NULL) {
247 pChunk = AllocChunk(std::max(m_iDefChunkSize, size));
248 pBlock = pChunk->FirstBlock();
249 }
250 FXSYS_assert(pChunk != NULL && pBlock != NULL);
251 size_t m = size + sizeof(FX_DYNAMICSTOREBLOCK);
252 pBlock->bUsed = TRUE;
253 if (pBlock->iBlockSize > m) {
254 size_t n = pBlock->iBlockSize;
255 pBlock->iBlockSize = size;
256 FX_LPDYNAMICSTOREBLOCK pNextBlock = pBlock->NextBlock();
257 pNextBlock->bUsed = FALSE;
258 pNextBlock->iBlockSize = n - size - sizeof(FX_DYNAMICSTOREBLOCK);
259 pChunk->iFreeSize -= size + sizeof(FX_DYNAMICSTOREBLOCK);
260 } else {
261 pChunk->iFreeSize -= pBlock->iBlockSize;
262 }
263 return pBlock->Data();
264 }
Free(void * pBlock)265 void CFX_DynamicStore::Free(void* pBlock) {
266 FXSYS_assert(pBlock != NULL);
267 FX_LPDYNAMICSTORECHUNK pPriorChunk, pChunk;
268 pPriorChunk = NULL, pChunk = m_pChunk;
269 while (pChunk != NULL) {
270 if (pBlock > pChunk &&
271 pBlock <= ((uint8_t*)pChunk + sizeof(FX_DYNAMICSTORECHUNK) +
272 pChunk->iChunkSize)) {
273 break;
274 }
275 pPriorChunk = pChunk, pChunk = pChunk->pNextChunk;
276 }
277 FXSYS_assert(pChunk != NULL);
278 FX_LPDYNAMICSTOREBLOCK pPriorBlock, pFindBlock;
279 pPriorBlock = NULL, pFindBlock = pChunk->FirstBlock();
280 while (pFindBlock->iBlockSize != 0) {
281 if (pBlock == (void*)pFindBlock->Data()) {
282 break;
283 }
284 pPriorBlock = pFindBlock;
285 pFindBlock = pFindBlock->NextBlock();
286 }
287 FXSYS_assert(pFindBlock->iBlockSize != 0 && pFindBlock->bUsed &&
288 pBlock == (void*)pFindBlock->Data());
289 pFindBlock->bUsed = FALSE;
290 pChunk->iFreeSize += pFindBlock->iBlockSize;
291 if (pPriorBlock == NULL) {
292 pPriorBlock = pChunk->FirstBlock();
293 } else if (pPriorBlock->bUsed) {
294 pPriorBlock = pFindBlock;
295 }
296 pFindBlock = pPriorBlock;
297 size_t sizeFree = 0;
298 size_t sizeBlock = 0;
299 while (pFindBlock->iBlockSize != 0 && !pFindBlock->bUsed) {
300 if (pFindBlock != pPriorBlock) {
301 sizeFree += sizeof(FX_DYNAMICSTOREBLOCK);
302 sizeBlock += sizeof(FX_DYNAMICSTOREBLOCK);
303 }
304 sizeBlock += pFindBlock->iBlockSize;
305 pFindBlock = pFindBlock->NextBlock();
306 }
307 pPriorBlock->iBlockSize = sizeBlock;
308 pChunk->iFreeSize += sizeFree;
309 if (pChunk->iFreeSize == pChunk->iChunkSize) {
310 if (pPriorChunk == NULL) {
311 m_pChunk = pChunk->pNextChunk;
312 } else {
313 pPriorChunk->pNextChunk = pChunk->pNextChunk;
314 }
315 FX_Free(pChunk);
316 }
317 }
SetDefChunkSize(size_t size)318 size_t CFX_DynamicStore::SetDefChunkSize(size_t size) {
319 FXSYS_assert(size != 0);
320 size_t v = m_iDefChunkSize;
321 m_iDefChunkSize = size;
322 return v;
323 }
324 #endif
325