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