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) 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 } 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 182 CFX_DynamicStore::CFX_DynamicStore(size_t iDefChunkSize) 183 : m_iDefChunkSize(iDefChunkSize), m_pChunk(NULL) { 184 FXSYS_assert(m_iDefChunkSize != 0); 185 } 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 } 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 } 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 } 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 } 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
