1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 #ifndef OSCL_VARIABLESIZE_MEMPOOL_H_INCLUDED 19 #define OSCL_VARIABLESIZE_MEMPOOL_H_INCLUDED 20 21 22 #ifndef OSCL_MEM_H_INCLUDED 23 #include "oscl_mem.h" 24 #endif 25 26 #ifndef OSCL_DEFALLOC_H_INCLUDED 27 #include "oscl_defalloc.h" 28 #endif 29 30 #ifndef OSCL_VECTOR_H_INCLUDED 31 #include "oscl_vector.h" 32 #endif 33 34 /////////////////////////////////////////////////////////////////////////////////////////////////////////// 35 ////////////////////// Variable size memory pool ///////////////////////////////////////////////////////// 36 /////////////////////////////////////////////////////////////////////////////////////////////////////////// 37 #define DEFAULT_NUM_CHUNKS_IN_VARIABLE_SIZE_MEMORY_POOL 16 38 39 /** \class allocator 40 ** A memory allocator class which allocates and deallocated from a variable size memory pool; 41 ** 42 */ 43 44 class OsclMemPoolVariableChunkAllocatorObserver 45 { 46 public: 47 virtual void freeVariableSizeChunkAvailable(OsclAny* aContextData) = 0; ~OsclMemPoolVariableChunkAllocatorObserver()48 virtual ~OsclMemPoolVariableChunkAllocatorObserver() 49 { 50 ; 51 } 52 }; 53 54 class OsclMemPoolVariableChunkAllocator : public Oscl_DefAlloc 55 { 56 public: 57 58 /** 59 * This API throws an exception when the memory allocation for pool fails 60 * If maximum pool size must be provided, otherwise it will throw an exception 61 * 62 * @return void 63 * 64 */ OsclMemPoolVariableChunkAllocator(const uint32 maxPoolSize)65 OsclMemPoolVariableChunkAllocator(const uint32 maxPoolSize) : 66 iMaxPoolSize(maxPoolSize), iMemPool(NULL), iNumRealAlloc(0), iAverAllocSize(0), 67 iCheckNextAvailableFreeChunk(false), iObserver(NULL) 68 { 69 createMempool(); 70 } 71 72 ~OsclMemPoolVariableChunkAllocator()73 virtual ~OsclMemPoolVariableChunkAllocator() 74 { 75 destroyMempool(); 76 } 77 78 /** 79 * This API throws an exception when n is greater than the maximum pool size or when there are no chunk available in the pool for the request size n 80 * If the memory pool hasn't been created yet, the pool will be created with the current maximum pool size 81 * Exception will be thrown if memory allocation for the memory pool fails. 82 * 83 * @return pointer to available chunk from memory pool 84 * 85 */ allocate(const uint32 n)86 OsclAny* allocate(const uint32 n) 87 { 88 // Create the memory pool if it hasn't been created yet. 89 if (iMemPool == NULL) createMempool(); 90 91 // sanity check 92 uint32 request_size = oscl_mem_aligned_size(n); 93 if (!allocateSanityCheck(request_size)) 94 { 95 OSCL_LEAVE(OsclErrNoMemory); 96 // return NULL; This statement was removed to avoid compiler warning for Unreachable Code 97 } 98 99 // do actual allocation 100 return doAllocate(request_size); 101 } 102 103 /** 104 * This API throws an exception when the pointer p passed in is not part of the memory pool. 105 * Exception will be thrown if the memory pool is not set up yet. 106 * 107 * @return void 108 * 109 */ deallocate(OsclAny * p)110 void deallocate(OsclAny* p) 111 { 112 // sanity check for "p" 113 if (!deallocateSanityCheck(p)) 114 { 115 OSCL_LEAVE(OsclErrNoMemory); 116 // return; This statement was removed to avoid compiler warning for Unreachable Code 117 } 118 119 // re-claim "p" 120 if (!doDeAllocate(p)) 121 { 122 // Returned memory is not aligned to the chunk. 123 OSCL_LEAVE(OsclErrNoMemory); 124 // return; This statement was removed to avoid compiler warning for Unreachable Code 125 } 126 127 // Notify the observer about free chunk available if waiting for such callback 128 if (iCheckNextAvailableFreeChunk) 129 { 130 iCheckNextAvailableFreeChunk = false; 131 if (iObserver) iObserver->freeVariableSizeChunkAvailable((OsclAny*)this); 132 } 133 } 134 135 /** 136 * Returns a tail segment of a previously allocated memory segmant back to the memory pool. 137 * This function allows the user to allocate a larger size memory segment initially when the amount needed is unknown 138 * and then return the unused portion of the segment when the amount becomes known. 139 * This API throws an exception if the pointer passed in is not part of the memory pool or the 140 * size to return is bigger than the size of the passed-in block. 141 * Exception will be thrown if the memory pool is not set up yet. 142 * 143 * @param aPtr is the starting pointer of the unused portion of memory segment 144 * @param aBytesToFree is the length of the unused portion 145 * @return bool True if reclaim operation successful. 146 * 147 */ reclaimUnusedPortion(OsclAny * aPtr,uint32 aBytesToFree)148 bool reclaimUnusedPortion(OsclAny* aPtr, uint32 aBytesToFree) 149 { 150 // sanity check for "p" 151 if (!deallocateSanityCheck(aPtr)) 152 { 153 OSCL_LEAVE(OsclErrNoMemory); 154 return false; 155 } 156 157 // construct a new memory chunk for this unused portion of pre-allocated memory chunk 158 OsclMemoryFragment memChunk; 159 memChunk.ptr = aPtr; 160 memChunk.len = aBytesToFree; 161 162 // reclaim this segment to iFreeMemChunkList 163 return reclaim(&memChunk); 164 } 165 166 /** 167 * This API will retrieve the maximum free memory chunk size to help user get the idea of how 168 * big the next allocation size could be. 169 * 170 * @return maximum chunk size, if there is no free memory or the memory pool hasn't been created, then return 0 171 * 172 */ getMaxFreeChunkSize()173 uint32 getMaxFreeChunkSize() 174 { 175 if (iFreeMemChunkList.empty() || iMemPool == NULL) return 0; 176 177 uint32 maxChunkSize = 0; 178 for (uint32 i = 0; i < iFreeMemChunkList.size(); i++) 179 { 180 if (maxChunkSize < iFreeMemChunkList[i].len) 181 { 182 maxChunkSize = iFreeMemChunkList[i].len; 183 } 184 } 185 return maxChunkSize; 186 } 187 188 /** 189 * This two APIs will retrieve the total free memory size (the actual size should be smaller due to fragment) and 190 * the actual memory usage (8-byte alignement) to help user get the idea of memory usage. 191 * 192 * @return total free memory size, if there is no free memory or the memory pool hasn't been created, then return 0 193 * 194 */ getTotalAvailableSize()195 uint32 getTotalAvailableSize() 196 { 197 if (iFreeMemChunkList.empty() || iMemPool == NULL) return 0; 198 199 uint32 totalSize = 0; 200 for (uint32 i = 0; i < iFreeMemChunkList.size(); i++) 201 { 202 totalSize += iFreeMemChunkList[i].len; 203 } 204 return totalSize; 205 } 206 getCurrMemoryUsage()207 uint32 getCurrMemoryUsage() 208 { 209 if (iUsedMemChunkList.empty() || iMemPool == NULL) return 0; 210 211 uint32 totalSize = 0; 212 for (uint32 i = 0; i < iUsedMemChunkList.size(); i++) 213 { 214 totalSize += iUsedMemChunkList[i].len; 215 } 216 return totalSize; 217 } 218 getPoolSize()219 uint32 getPoolSize() const 220 { 221 return iMaxPoolSize; 222 } 223 224 225 /** 226 * This API clears all the records of all allocations. Please NOTE that, after this API gets called, 227 * the memory pool returns to the initial state, i.e. one big free segment. 228 * 229 */ clear()230 void clear() 231 { 232 // clear the records 233 iFreeMemChunkList.clear(); 234 iUsedMemChunkList.clear(); 235 iNumRealAlloc = 0; 236 iAverAllocSize = 0; 237 238 // set up the first memory segment in the free mem chunk list 239 OsclMemoryFragment memChunk; 240 memChunk.ptr = iMemPool; 241 memChunk.len = iMaxPoolSize; 242 iFreeMemChunkList.push_back(memChunk); 243 } 244 245 /** 246 * This API will set the flag to send a callback via specified observer object when the 247 * next memory chunk is deallocated by deallocate() call.. 248 * 249 * @return void 250 * 251 */ notifyFreeChunkAvailable(OsclMemPoolVariableChunkAllocatorObserver & obs)252 void notifyFreeChunkAvailable(OsclMemPoolVariableChunkAllocatorObserver& obs) 253 { 254 iCheckNextAvailableFreeChunk = true; 255 iObserver = &obs; 256 } 257 258 private: 259 260 ////////////////////////////////////////////////////////////////////////////// 261 /////// create and destroy memory pool /////////////////////////////////////// 262 ////////////////////////////////////////////////////////////////////////////// 263 createMempool()264 void createMempool() 265 { 266 if (iMaxPoolSize == 0) 267 { 268 OSCL_LEAVE(OsclErrNoMemory); 269 // return; This statement was removed to avoid compiler warning for Unreachable Code 270 } 271 272 // Create one block of memory for the memory pool 273 iMaxPoolSize = oscl_mem_aligned_size(iMaxPoolSize); 274 iMemPool = OSCL_MALLOC(iMaxPoolSize); 275 if (iMemPool == NULL) 276 { 277 OSCL_LEAVE(OsclErrNoMemory); 278 // return; This statement was removed to avoid compiler warning for Unreachable Code 279 } 280 281 // Set up the free and used mem chunk list vector 282 int32 err = 0; 283 OSCL_TRY(err, 284 iFreeMemChunkList.reserve(DEFAULT_NUM_CHUNKS_IN_VARIABLE_SIZE_MEMORY_POOL); 285 iUsedMemChunkList.reserve(DEFAULT_NUM_CHUNKS_IN_VARIABLE_SIZE_MEMORY_POOL); 286 ); 287 if (err) 288 { 289 OSCL_LEAVE(OsclErrNoMemory); 290 // return; This statement was removed to avoid compiler warning for Unreachable Code 291 } 292 293 // set up the first memory segment in the free mem chunk list 294 OsclMemoryFragment memChunk; 295 memChunk.ptr = iMemPool; 296 memChunk.len = iMaxPoolSize; 297 iFreeMemChunkList.push_back(memChunk); 298 } 299 destroyMempool()300 void destroyMempool() 301 { 302 iFreeMemChunkList.clear(); 303 iUsedMemChunkList.clear(); 304 if (iMemPool) OSCL_FREE(iMemPool); 305 } 306 307 308 ////////////////////////////////////////////////////////////////////////////// 309 /////// Supporting functions for API allocate() ///////////////////////////// 310 ////////////////////////////////////////////////////////////////////////////// allocateSanityCheck(const uint32 n)311 bool allocateSanityCheck(const uint32 n) 312 { 313 if (n > iMaxPoolSize) return false; 314 if (iFreeMemChunkList.empty()) return false; 315 316 return true; 317 } 318 PushMemChunkToChunkVector(OsclMemoryFragment * aMemChunk)319 int32 PushMemChunkToChunkVector(OsclMemoryFragment* aMemChunk) 320 { 321 int32 leavecode = OsclErrNone; 322 OSCL_TRY(leavecode, iUsedMemChunkList.push_back(*aMemChunk)); 323 return leavecode; 324 } 325 doAllocate(const uint32 n)326 OsclAny* doAllocate(const uint32 n) 327 { 328 OsclMemoryFragment memChunk; 329 OsclMemoryFragment *pMemChunk = &memChunk; 330 331 // get the available memory chunk 332 uint32 alloc_size = n; 333 if (!getFreeMemChunk(pMemChunk, alloc_size)) 334 { 335 // No free chunk is available 336 OSCL_LEAVE(OsclErrNoMemory); 337 // return NULL; This statement was removed to avoid compiler warning for Unreachable Code 338 } 339 340 // insert the removed segment into the iUsedMemChunkList if there is 341 int32 err = PushMemChunkToChunkVector(pMemChunk); 342 if (err) 343 { 344 OSCL_LEAVE(OsclErrNoMemory); 345 // return NULL; This statement was removed to avoid compiler warning for Unreachable Code 346 } 347 348 // calculate the average alloc size for next split decision -- 349 // to split, the remaining size should not be smaller than the so-far average allocated size 350 iAverAllocSize = (iAverAllocSize * iNumRealAlloc + alloc_size); 351 iAverAllocSize /= (OsclFloat)(++iNumRealAlloc); 352 353 return pMemChunk->ptr; 354 } 355 getFreeMemChunk(OsclMemoryFragment * pMemChunk,uint32 & alloc_size)356 bool getFreeMemChunk(OsclMemoryFragment* pMemChunk, uint32 &alloc_size) 357 { 358 pMemChunk->ptr = NULL; 359 pMemChunk->len = 0; 360 361 for (uint32 i = 0; i < iFreeMemChunkList.size(); i++) 362 { 363 if (iFreeMemChunkList[i].len < alloc_size) continue; 364 365 // Allocation must happen 366 if (iFreeMemChunkList[i].len - alloc_size > (uint32)iAverAllocSize) 367 { 368 // split the current segment 369 pMemChunk->ptr = iFreeMemChunkList[i].ptr; 370 pMemChunk->len = alloc_size; 371 372 uint8 *p = (uint8*)iFreeMemChunkList[i].ptr + alloc_size; 373 iFreeMemChunkList[i].ptr = (OsclAny*)p; 374 iFreeMemChunkList[i].len -= alloc_size; 375 } 376 else 377 { 378 // allocate the whole segment 379 pMemChunk->ptr = iFreeMemChunkList[i].ptr; 380 pMemChunk->len = iFreeMemChunkList[i].len; 381 alloc_size = pMemChunk->len; 382 383 // remove this segment 384 iFreeMemChunkList.erase(iFreeMemChunkList.begin() + i); 385 } 386 break; 387 } 388 389 return (pMemChunk->ptr != NULL); 390 } 391 392 ////////////////////////////////////////////////////////////////////////////// 393 /////// Supporting functions for API deallocate() /////////////////////////// 394 ////////////////////////////////////////////////////////////////////////////// deallocateSanityCheck(OsclAny * p)395 bool deallocateSanityCheck(OsclAny* p) 396 { 397 if (iMemPool == NULL) 398 { 399 // Memory pool hasn't been allocated yet so error 400 return false; 401 } 402 403 uint8* ptmp = (uint8*)p; 404 uint8* mptmp = (uint8*)iMemPool; 405 if (ptmp < mptmp || ptmp >= (mptmp + iMaxPoolSize)) 406 { 407 // Returned memory is not part of this memory pool 408 return false; 409 } 410 411 if (iUsedMemChunkList.empty()) return false; 412 413 return true; 414 } 415 doDeAllocate(OsclAny * p)416 bool doDeAllocate(OsclAny* p) 417 { 418 // remove the segment associated with "p" from iUsedMemChunkList 419 OsclMemoryFragment memChunk; 420 bool bFound = false; 421 for (uint32 i = 0; i < iUsedMemChunkList.size(); i++) 422 { 423 if ((uint8*)iUsedMemChunkList[i].ptr == (uint8*)p) 424 { 425 memChunk.ptr = iUsedMemChunkList[i].ptr; 426 memChunk.len = iUsedMemChunkList[i].len; 427 iUsedMemChunkList.erase(iUsedMemChunkList.begin() + i); 428 bFound = true; 429 break; 430 } 431 } 432 433 if (!bFound) return false; // Not found 434 435 // reclaim this segment to iFreeMemChunkList 436 return reclaim(&memChunk); 437 } 438 reclaim(OsclMemoryFragment * aMemChunk)439 bool reclaim(OsclMemoryFragment *aMemChunk) 440 { 441 // short cut 442 if (iFreeMemChunkList.empty()) 443 { 444 int32 err = 0; 445 OSCL_TRY(err, iFreeMemChunkList.push_back(*aMemChunk)); 446 return (err == 0); 447 } 448 449 // the input memory segment can be continuous with one or two existing memory segments in iFreeMemChunkList 450 // and thus it can be merged into the existing continuous memory segments 451 // so search the continuities: left continuity(the input segment is continuous to an existing memory segment on its left side) 452 // right continuity(the input segment is continuous to an existing memory segment on its right side) 453 // both continuity(the input segment is continuous to two existing memory segments on both sides) 454 int32 index_leftContinuity = -1, index_rightContinuity = -1; 455 searchSegmentContinuity(aMemChunk, index_leftContinuity, index_rightContinuity); 456 457 // merge the two or three continuous memory segments if there are 458 return doMerge(aMemChunk, index_leftContinuity, index_rightContinuity); 459 } 460 461 /** 462 * the input memory segment can be continuous with one or two existing memory segments in iFreeMemChunkList 463 * and thus it can be merged into the existing continuous memory segments 464 * so search the continuities; left continuity(the input segment is continuous to an existing memory segment on its left side) 465 * right continuity(the input segment is continuous to an existing memory segment on its right side) 466 * both-sided continuity(the input segment is continuous to two existing memory segments on both sides) 467 * @param aMemChunk, input memory segment 468 * @param index_leftContinuity, index of the existing memory segment in iFreeMemChunkList that is continuous to 469 * the input memory segment on its left side 470 * @param index_rightContinuity, index of the existing memory segment in iFreeMemChunkList that is continuous to 471 * the input memory segment on its left side 472 **/ searchSegmentContinuity(OsclMemoryFragment * aMemChunk,int32 & index_leftContinuity,int32 & index_rightContinuity)473 void searchSegmentContinuity(OsclMemoryFragment *aMemChunk, int32 &index_leftContinuity, int32 &index_rightContinuity) 474 { 475 uint8 *leftPtr = (uint8 *)aMemChunk->ptr; 476 uint8 *rightPtr = (uint8 *)aMemChunk->ptr + aMemChunk->len; 477 478 for (uint32 i = 0; i < iFreeMemChunkList.size(); i++) 479 { 480 if (leftPtr == (uint8*)iFreeMemChunkList[i].ptr + iFreeMemChunkList[i].len) 481 { 482 index_leftContinuity = (int32)i; 483 } 484 485 if (rightPtr == (uint8*)iFreeMemChunkList[i].ptr) 486 { 487 index_rightContinuity = (int32)i; 488 } 489 490 if (index_leftContinuity >= 0 && index_rightContinuity >= 0) break; 491 } 492 } 493 494 /** 495 * merge the two or three continuous memory segments if there are 496 * 497 * @param aMemChunk, input memory segment 498 * @param index_leftContinuity, index of the existing memory segment in iFreeMemChunkList that is continuous to 499 * the input memory segment on its left side, or not 500 * @param index_rightContinuity, index of the existing memory segment in iFreeMemChunkList that is continuous to 501 * the input memory segment on its left side, or not 502 * @return true => success, false => fail in push_back operation 503 **/ doMerge(OsclMemoryFragment * aMemChunk,const int32 index_leftContinuity,const int32 index_rightContinuity)504 bool doMerge(OsclMemoryFragment *aMemChunk, const int32 index_leftContinuity, const int32 index_rightContinuity) 505 { 506 if (index_leftContinuity < 0 && index_rightContinuity < 0) 507 { 508 // no merge, push to the end of iFreeMemChunkList 509 int32 err = 0; 510 OSCL_TRY(err, iFreeMemChunkList.push_back(*aMemChunk)); 511 return (err == 0); 512 } 513 514 // merge two or three segments 515 if (index_leftContinuity >= 0 && index_rightContinuity >= 0) // merge three segments 516 { 517 // keep the segment with index_leftContinuity, and remove the segment with index_rightContinuity 518 iFreeMemChunkList[index_leftContinuity].len += (aMemChunk->len + iFreeMemChunkList[index_rightContinuity].len); 519 iFreeMemChunkList.erase(iFreeMemChunkList.begin() + index_rightContinuity); 520 } 521 else if (index_leftContinuity >= 0) 522 { 523 iFreeMemChunkList[index_leftContinuity].len += aMemChunk->len; 524 } 525 else if (index_rightContinuity >= 0) 526 { 527 iFreeMemChunkList[index_rightContinuity].ptr = aMemChunk->ptr; 528 iFreeMemChunkList[index_rightContinuity].len += aMemChunk->len; 529 } 530 531 return true; 532 } 533 534 private: 535 536 uint32 iMaxPoolSize; 537 OsclAny* iMemPool; 538 uint32 iNumRealAlloc; 539 OsclFloat iAverAllocSize; 540 541 Oscl_Vector<OsclMemoryFragment, OsclMemAllocator> iFreeMemChunkList; 542 Oscl_Vector<OsclMemoryFragment, OsclMemAllocator> iUsedMemChunkList; 543 544 bool iCheckNextAvailableFreeChunk; 545 OsclMemPoolVariableChunkAllocatorObserver* iObserver; 546 }; 547 548 #endif 549