1 /*---------------------------------------------------------------------------* 2 * pmalloc.c * 3 * * 4 * Copyright 2007, 2008 Nuance Communciations, Inc. * 5 * * 6 * Licensed under the Apache License, Version 2.0 (the 'License'); * 7 * you may not use this file except in compliance with the License. * 8 * * 9 * You may obtain a copy of the License at * 10 * http://www.apache.org/licenses/LICENSE-2.0 * 11 * * 12 * Unless required by applicable law or agreed to in writing, software * 13 * distributed under the License is distributed on an 'AS IS' BASIS, * 14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 15 * See the License for the specific language governing permissions and * 16 * limitations under the License. * 17 * * 18 *---------------------------------------------------------------------------*/ 19 20 21 22 23 /* this source file is only used when PORTABLE_DINKUM_MEM_MGR is defined 24 */ 25 #ifdef PORTABLE_DINKUM_MEM_MGR 26 27 #include <stdlib.h> 28 #include <string.h> /* for memset */ 29 #include "pmalloc.h" 30 #include "passert.h" 31 #include "ptypes.h" 32 #include "plog.h" 33 34 #undef malloc 35 #undef calloc 36 #undef realloc 37 #undef free 38 39 #ifdef __cplusplus 40 extern "C" 41 { 42 #endif 43 44 /* 45 * There are two controlling options within this scheme: 46 * 47 * STATIC_MEMORY_POOL: When defined, there is a static array from which memory is 48 * allocated. The size of this array is defined at compile time. When undefined 49 * (the default), the memory is allocated via malloc(). This code works under PSOS and 50 * PSOSIM, but has not been tested anywhere else (4March02). 51 * VOYAGER_KERNEL_MEMORY: When defined for the Voyager platform, it is similar to the 52 * non-static memory pool, but the memory buffer is pre-defined, and is simply pointed 53 * at by the pmalloc initializer. 54 * RTXC_PARTITION_MEMORY: When defined for the RTXC operating system, uses a static kernel 55 * partition resource for the memory chunk. 56 * VOYAGER_KERNEL_MEMORY and RTXC_PARTITION_MEMORY are mutually exclusive and take precedence 57 * over STATIC_MEMORY. 58 * 59 60 * the standard off-the-shelf Dinkumware software is pretty slow, primarily due to 61 * scanning the free-memory linked list in PortFree(). If SPEEDUP is defined, then 62 * split the memory pool into imaginary 'bins', and keep track of the first free list 63 * entry in each bin. Then the linked list lookup can be MUCH faster, as you can 64 * start very close to the final destination in the linked list. 65 * 66 * (If SPEEDUP_COMPARE is defined, then run BOTH the standard technique and the 67 * speedup technique and compare the results.) 68 */ 69 70 /* malloc function */ 71 _STD_BEGIN 72 73 /* data *******************************************************************************/ 74 75 #if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME) 76 /* Verify that memory pool actually was created, because of the lack of structure, this is accessed externally */ 77 ESR_ReturnCode memory_pool_creation_status = ESR_FATAL_ERROR; 78 #endif 79 80 /* static data */ 81 _Altab _Aldata = {0}; /* heap initially empty */ 82 psize_t _Size_block = {SIZE_BLOCK}; /* preferred _Getmem chunk */ 83 84 /* Memory pool size */ 85 #define MEM_SIZE_MB( mbytes ) ((mbytes) * 1024 * 1024 ) 86 87 #ifndef MEM_SIZE 88 /* If not defined on the command line, use default values. */ 89 #define MEM_SIZE MEM_SIZE_MB( 5 ) 90 #endif 91 92 /* Memory pool initialized */ 93 static int pmallocInitted = FALSE; /* TRUE once initialized */ 94 95 #ifdef STATIC_MEMORY_POOL 96 /* The memory pool can either be statically allocated or require a one-time system malloc. 97 * For VTB, the system was taking 2 seconds to zero the static memBuffer[] array at 98 * boot time, since it's in the BSS segment. Therefore, for VTB, it is better to allocate 99 * at run time. 100 */ 101 static char memBuffer[MEM_SIZE]; 102 #else 103 static char *memBuffer; 104 #endif 105 106 static psize_t memSize = MEM_SIZE; 107 108 /* Memory pool free list */ 109 /* partition memory range into 'bins', and keep track of the first 110 * free list entry in each bin. This is to speed up the linked-list search 111 * that takes place when memory is freed. 112 */ 113 #define BIN_BITS 14 /* smaller number ==> more bins */ 114 #define BIN_SIZE 16384 /* 2 ^ BIN_BITS */ 115 116 #define __NUM_MEM_BINS(memPoolSize) (((memPoolSize)/BIN_SIZE) + 5) /* 5 = extra for roundoff */ 117 #define GET_MEM_BIN( _ptr_ ) (int)(((unsigned int)_ptr_ - (unsigned int)&memBuffer[0]) >> BIN_BITS) 118 119 #define NUM_MEM_BINS __NUM_MEM_BINS(MEM_SIZE) 120 static _Cell *binsFirstFreeCell[NUM_MEM_BINS+1] = {0}; 121 static psize_t numMemBins; 122 123 /* Memory Pool sbrk/getmem variables */ 124 125 static char *__heap_ptr = NULL; 126 static char *__heap_end = NULL; 127 static int maxMemUsed = 0; 128 129 /* Memory Pool initialization and _GetMem functions ************************************/ 130 131 #if _USE_EXISTING_SYSTEM_NAMES 132 #define _Sbrk sbrk 133 #endif 134 135 _STD_BEGIN 136 137 void *_Sbrk(int incr) 138 { 139 char *ret; 140 141 /* Subtract 1 from __heap_ptr so that the left hand side of the comparison evaluates to the address of the 142 last address of the requested memory block */ 143 if ((__heap_ptr + incr - 1) > __heap_end) return(void *) - 1; 144 145 ret = __heap_ptr; 146 __heap_ptr += incr; 147 maxMemUsed += incr; 148 return (void *)ret; 149 } 150 151 void *_Getmem(psize_t size) 152 { /* allocate raw storage */ 153 void *p; 154 int isize = size; 155 156 return (isize <= 0 || (p = _Sbrk(isize)) == (void *) - 1 157 ? 0 : p); 158 } 159 _STD_END 160 161 /* PortMallocInit() : initialize memory pool. There is no initialization needed for 162 * a static memory pool. Otherwise, perform a one-time malloc from the OS. 163 */ 164 void PortMallocInit(void) 165 { 166 #if defined STATIC_MEMORY_POOL 167 memSize = MEM_SIZE; 168 #else 169 /* TODO: is malloc of binsFirstFreeCell safe under PSOS in all conditions ? */ 170 memBuffer = (char *)malloc(memSize); 171 #if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME) 172 if (memBuffer != NULL) /* For external access, check comment at top */ 173 memory_pool_creation_status = ESR_SUCCESS; 174 #endif 175 numMemBins = __NUM_MEM_BINS(memSize); 176 #endif /* #ifdef VOYAGER_KERNEL_MEMORY */ 177 178 passert(memBuffer != NULL); 179 passert(binsFirstFreeCell != NULL); 180 181 __heap_ptr = &memBuffer[0]; 182 __heap_end = &memBuffer[memSize-1]; 183 184 /* set initted flag so we only do this once */ 185 pmallocInitted = TRUE; 186 maxMemUsed = 0; 187 188 memset(&_Aldata, 0, sizeof(_Altab)); 189 190 memset(binsFirstFreeCell, 0, sizeof(_Cell*)*(NUM_MEM_BINS + 1)); 191 } 192 193 void PortMallocTerm(void) 194 { 195 #ifndef STATIC_MEMORY_POOL 196 memSize = 0; 197 free(memBuffer); 198 memBuffer = NULL; 199 #if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME) 200 memory_pool_creation_status = ESR_FATAL_ERROR; /* For external access, check comment at top */ 201 #endif 202 #endif 203 pmallocInitted = FALSE; 204 } 205 206 /* PortGetMaxMemUsed() : return the maximum real memory allocated. 207 * There is another function of the same name in pmemory.cpp, for tracking 208 * psos block memory. It uses #ifdef MEM_PSOS_BLOCK_SCHEME to enable. 209 */ 210 int PortMallocGetMaxMemUsed(void) 211 { 212 return maxMemUsed; 213 } 214 215 /* PortMallocSetPoolSize( psize_t size ) : define size of memory pool. 216 */ 217 void PortMallocSetPoolSize(psize_t size) 218 { 219 #if !defined(STATIC_MEMORY_POOL) && !defined(VOYAGER_KERNEL_MEMORY) && !defined(RTXC_PARTITION_MEMORY) 220 if (!pmallocInitted) 221 { 222 memSize = size; 223 } 224 #else 225 (void)size; 226 #endif 227 } 228 229 /* PortMallocGetPoolSize() : return size of memory pool. 230 */ 231 psize_t PortMallocGetPoolSize(void) 232 { 233 #if defined STATIC_MEMORY_POOL 234 return MEM_SIZE; 235 #else 236 return memSize; 237 #endif 238 } 239 240 /* debug *******************************************************************************/ 241 242 /* xalloc.h internal header - debugging components */ 243 #if DEBUG 244 245 int _OK_Cell(_Cell *p) 246 { 247 passert(SIZE_CELL <= p->_Size); 248 return 1; 249 } 250 251 typedef struct _DB_Altab 252 { 253 psize_t total_heap; 254 psize_t total_alloc; 255 psize_t total_free; 256 } 257 _DB_Altab; 258 259 _DB_Altab _DB_Altab_object = {0}; 260 261 void _UPD_Altab(psize_t d_heap, psize_t d_alloc, psize_t d_free) 262 { 263 _DB_Altab *pd = &_DB_Altab_object; 264 pd->total_heap += d_heap; 265 pd->total_alloc += d_alloc; 266 pd->total_free += d_free; 267 } 268 269 int _OK_Altab(_Altab *p) 270 { 271 _DB_Altab *pd = &_DB_Altab_object; 272 _Cell *q; 273 psize_t total_free = 0; 274 if (p->_Head == 0) 275 return 1; 276 for (q = p->_Head; q != 0; q = q->_Next) 277 { 278 total_free += q->_Size; 279 _OK_Cell(q); 280 if (q->_Next != 0) 281 { 282 passert(_PTR_NORM((char *)q + q->_Size) <= 283 _PTR_NORM((char *)q->_Next)); 284 passert(_PTR_NORM(q) < _PTR_NORM(q->_Next)); 285 } 286 } 287 passert(pd->total_heap == pd->total_alloc + pd->total_free); 288 passert(total_free == pd->total_free); 289 return 1; 290 } 291 #endif /* DEBUG */ 292 293 /* allocation functions ***************************************************************/ 294 295 static _Cell **findmem(psize_t size) 296 { /* find storage */ 297 _Cell *q, **qb; 298 299 for (; ;) 300 { /* check freed space first */ 301 if ((qb = _Aldata._Plast) == 0) 302 { /* take it from the top */ 303 for (qb = &_Aldata._Head; *qb != 0; 304 qb = &(*qb)->_Next) 305 if (size <= (*qb)->_Size) 306 return (qb); 307 } 308 else 309 { /* resume where we left off */ 310 for (; *qb != 0; qb = &(*qb)->_Next) 311 if (size <= (*qb)->_Size) 312 return (qb); 313 q = *_Aldata._Plast; 314 for (qb = &_Aldata._Head; *qb != q; 315 qb = &(*qb)->_Next) 316 if (size <= (*qb)->_Size) 317 return (qb); 318 } 319 { /* try to buy more space */ 320 psize_t bs; 321 322 for (bs = _Size_block; ; bs >>= 1) 323 { /* try larger blocks first */ 324 if (bs < size) 325 bs = size; 326 if ((q = (_Cell *)_Getmem(bs)) != 0) 327 break; 328 else if (bs == size) 329 return (0); /* no storage */ 330 } 331 /* got storage: add to heap and retry */ 332 q->_Size = bs; 333 _UPD_Altab(q->_Size, q->_Size, 0); /* heap=alloc+free */ 334 PortFree((char *)q + CELL_OFF); 335 } 336 } 337 } 338 339 340 void *(PortMalloc)(psize_t size_arg) 341 { /* allocate a data object on the heap */ 342 _Cell *q, **qb; 343 #ifdef SPEEDUP 344 int qbsBin; 345 int qbNextBin; 346 #endif /* SPEEDUP */ 347 psize_t size; 348 349 passert(pmallocInitted); 350 351 size = (size_arg + (CELL_OFF + M_MASK)) & ~M_MASK; 352 353 _OK_Altab(&_Aldata); 354 if (size <= size_arg) 355 return (0); /* size_arg too large */ 356 if (size < SIZE_CELL) /* round up size */ 357 size = SIZE_CELL; 358 if ((qb = findmem(size)) == 0) 359 return (0); 360 q = *qb; 361 if (q->_Size - SIZE_CELL < size) 362 { 363 /* use entire cell (there's not enough space to carve out a new cell from this one) */ 364 #ifdef SPEEDUP 365 /* remove *qb cell from free list. 366 * careful : the Next pointer may be in a different bin. 367 */ 368 qbsBin = GET_MEM_BIN(*qb); 369 370 /* Check whether the cell is at the end of the 'free' linked-list */ 371 if (0 != ((*qb)->_Next)) 372 { 373 /* The cell is not at the end of the free linked-list; find out which bin the next free cell is in */ 374 qbNextBin = GET_MEM_BIN((*qb)->_Next); 375 376 if (qbsBin == qbNextBin) 377 { 378 if (binsFirstFreeCell[qbsBin] == *qb) 379 { 380 /* The allocated cell was the first free cell in the bin; update the first free cell 381 pointer to point to the next free cell */ 382 binsFirstFreeCell[qbsBin] = (*qb)->_Next; 383 } 384 } 385 else 386 { 387 if (binsFirstFreeCell[qbsBin] == *qb) 388 { 389 /* The allocated cell was the only free cell in the bin; update the first free cell 390 pointer to point to NULL */ 391 392 binsFirstFreeCell[qbsBin] = 0; 393 } 394 } 395 } 396 else 397 { 398 /* Cell is at the end of the 'free' linked-list */ 399 if (binsFirstFreeCell[qbsBin] == *qb) 400 { 401 /* The allocated cell was the first free cell in the bin; there are no following free cells 402 so set the first free cell pointer to NULL */ 403 binsFirstFreeCell[qbsBin] = 0; 404 } 405 } 406 #endif /* SPEEDUP */ 407 *qb = q->_Next; 408 } 409 else 410 { /* peel off a residual cell */ 411 *qb = (_Cell *)((char *)q + size); 412 (*qb)->_Next = q->_Next; 413 (*qb)->_Size = q->_Size - size; 414 q->_Size = size; 415 #ifdef SPEEDUP 416 /* remove q from free list, and add *qb to free list. 417 * Do this as two separate steps because they may be in 2 different bins. 418 */ 419 /* remove q from free list */ 420 if (binsFirstFreeCell[GET_MEM_BIN(q)] == q) 421 binsFirstFreeCell[GET_MEM_BIN(q)] = 0; 422 /* now add *qb to its bin's free list if it's the first */ 423 qbsBin = GET_MEM_BIN(*qb); 424 if ((binsFirstFreeCell[qbsBin] == 0) || (*qb < binsFirstFreeCell[qbsBin])) 425 binsFirstFreeCell[qbsBin] = *qb; 426 #endif /* SPEEDUP */ 427 } 428 _Aldata._Plast = qb; /* resume scan here */ 429 _UPD_Altab(0, q->_Size, -q->_Size); /* heap=alloc+free */ 430 _OK_Altab(&_Aldata); 431 return ((char *)q + CELL_OFF); 432 } 433 _STD_END 434 435 436 /* free function */ 437 _STD_BEGIN 438 439 void(PortFree)(void *ptr) 440 { /* free an allocated data object */ 441 register _Cell *q; 442 register psize_t size; 443 #ifdef SPEEDUP 444 int binNum; 445 int binIndex; 446 int qNextBin; 447 int qNextNextBin; 448 #endif /* SPEEDUP */ 449 static int portFreeCount = 0; 450 portFreeCount++; 451 452 passert(pmallocInitted); 453 454 _OK_Altab(&_Aldata); 455 if (ptr == 0) 456 return; 457 q = (_Cell *)((char *)ptr - CELL_OFF); 458 size = q->_Size; 459 #ifdef SPEEDUP 460 binNum = GET_MEM_BIN(q); 461 #endif /* SPEEDUP */ 462 if (size < SIZE_CELL || (size & M_MASK) != 0) 463 return; /* erroneous call, bad count */ 464 if (_Aldata._Head == 0 465 || _PTR_NORM(q) < _PTR_NORM(_Aldata._Head)) 466 { /* insert at head of list */ 467 q->_Next = _Aldata._Head; 468 _Aldata._Head = q; 469 #ifdef SPEEDUP 470 /* always the start of a bin */ 471 binsFirstFreeCell[binNum] = q; 472 #endif /* SPEEDUP */ 473 } 474 else 475 { /* scan for insertion point */ 476 register _Cell *qp = _Aldata._Head; 477 register char *qpp; 478 register _Cell *nextCell; 479 #if !defined SPEEDUP || defined SPEEDUP_COMPARE 480 _Cell *savedQp; 481 482 /* this search loop is where all the time is spent */ 483 while ((nextCell = qp->_Next) != 0 484 && _PTR_NORM(nextCell) < _PTR_NORM(q)) 485 qp = qp->_Next; 486 savedQp = qp; 487 #endif /* SPEEDUP */ 488 489 #ifdef SPEEDUP 490 /* this is where the SPEEDUP code is sped up : start with the bin's first free cell */ 491 _Cell *firstFreeInBin = binsFirstFreeCell[binNum]; 492 if ((firstFreeInBin != 0) && (q > firstFreeInBin)) 493 { 494 qp = firstFreeInBin; 495 while ((nextCell = qp->_Next) != 0 496 && _PTR_NORM(nextCell) < _PTR_NORM(q)) 497 { 498 qp = qp->_Next; 499 } 500 } 501 else 502 { 503 /* go back to the previous non-zero bin */ 504 qp = NULL; /* for diagnostics */ 505 for (binIndex = binNum; binIndex >= 0; binIndex--) 506 { 507 if ((binsFirstFreeCell[binIndex] != 0) && (q > binsFirstFreeCell[binIndex])) 508 { 509 qp = binsFirstFreeCell[binIndex]; 510 break; 511 } 512 } 513 /* this code for diagnostic purposes to see how often it happens. otherwise, 514 * qp could have been set to _Aldata._Head prior to the binIndex loop above. 515 */ 516 if (qp == NULL) 517 { 518 qp = _Aldata._Head; 519 } 520 521 /* find the free cell location */ 522 while ((nextCell = qp->_Next) != 0 523 && _PTR_NORM(nextCell) < _PTR_NORM(q)) 524 qp = qp->_Next; 525 } 526 527 #ifdef SPEEDUP_COMPARE 528 if (qp != savedQp) 529 printf("oops \n"); 530 #endif /* SPEEDUP_COMPARE */ 531 #endif /* SPEEDUP */ 532 533 #if !defined SPEEDUP || defined SPEEDUP_COMPARE 534 qp = savedQp; 535 #endif /* SPEEDUP */ 536 537 qpp = (char *)qp + qp->_Size; 538 if (_PTR_NORM((char *)q) < _PTR_NORM(qpp)) 539 return; /* erroneous call, overlaps qp */ 540 else if (_PTR_NORM(qpp) == _PTR_NORM((char *)q)) 541 { /* merge qp and q (merge with prior cell) */ 542 /* nothing to do to bin's free list here */ 543 qp->_Size += q->_Size; 544 q = qp; 545 } 546 else if (qp->_Next != 0 && _PTR_NORM((char *)qp->_Next) 547 < _PTR_NORM((char *)q + q->_Size)) 548 return; /* erroneous call, overlaps qp->_Next */ 549 else 550 { /* splice q after qp */ 551 #ifdef SPEEDUP 552 /* add 1 entry here - this could change first entry in q's bin */ 553 _Cell *firstFree = binsFirstFreeCell[binNum]; 554 if ((firstFree == 0) || (q < firstFree)) 555 binsFirstFreeCell[binNum] = q; 556 #endif /* SPEEDUP */ 557 q->_Next = qp->_Next; 558 qp->_Next = q; 559 } 560 } 561 if (q->_Next != 0 && _PTR_NORM((char *)q + q->_Size) 562 == _PTR_NORM((char *)q->_Next)) 563 { /* merge q and q->_Next (merge with latter cell) */ 564 #ifdef SPEEDUP 565 /* lose 1 cell here - this could change first entry in bin. 566 * if q->_Next was first in bin, now it's its Next. 567 * careful : watch for next being in a different bin. 568 */ 569 qNextBin = GET_MEM_BIN(q->_Next); 570 571 if (binsFirstFreeCell[qNextBin] == q->_Next) 572 { 573 /* The q->_Next cell is the first free cell in its bin; set the first free cell 574 pointer to NULL for now; if there is another free cell in the same bin then 575 the first free cell pointer will be updated in next 'if' code block */ 576 binsFirstFreeCell[qNextBin] = 0; 577 578 /* If there is another free cell after q->_Next and it's in the same bin then 579 update the first free cell pointer if necessary */ 580 if (0 != (q->_Next->_Next)) 581 { 582 qNextNextBin = GET_MEM_BIN(q->_Next->_Next); 583 584 /* The first free cell pointer for q->_Next->_Next's bin can only be set to 0 585 by the code above; if it is 0 then q->_Next->_Next must be the first free 586 cell in the bin */ 587 if (0 == binsFirstFreeCell[qNextNextBin]) 588 { 589 binsFirstFreeCell[qNextNextBin] = q->_Next->_Next; 590 } 591 } 592 } 593 #endif /* SPEEDUP */ 594 _Aldata._Plast = 0; /* deoptimize for safety */ 595 q->_Size += q->_Next->_Size; 596 q->_Next = q->_Next->_Next; 597 } 598 _UPD_Altab(0, -size, size); /* heap=alloc+free */ 599 _OK_Altab(&_Aldata); 600 /* every successful free "falls off" here */ 601 } 602 _STD_END 603 604 #ifdef __cplusplus 605 } /* end extern "C" */ 606 #endif 607 608 #endif /* PORTABLE_DINKUM_MEM_MGR */ 609 610 611
