1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the library */ 4 /* BMS --- Block Memory Shell */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file memory.c 26 * @ingroup OTHER_CFILES 27 * @brief memory allocation routines 28 * @author Tobias Achterberg 29 * @author Gerald Gamrath 30 * @author Marc Pfetsch 31 * @author Jakob Witzig 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #ifdef __cplusplus 37 #define __STDC_LIMIT_MACROS 38 #endif 39 40 #include <stdio.h> 41 #include <stdlib.h> 42 #include <assert.h> 43 #include <string.h> 44 45 /* 46 * include build configuration flags 47 */ 48 #include "scip/config.h" 49 50 #ifdef WITH_SCIPDEF 51 #include "scip/def.h" 52 #include "scip/pub_message.h" 53 #else 54 #include <stdint.h> 55 #endif 56 57 #include "blockmemshell/memory.h" 58 #include "scip/rbtree.h" 59 60 /* uncomment the following to enable the use of a memlist in debug mode 61 * that checks for some memory leaks and allows to add the additional 62 * checks enabled with the defines below. 63 * The maintenance of the memlist, however, is not threadsafe. 64 */ 65 #ifndef SCIP_THREADSAFE 66 /*#define ENABLE_MEMLIST_CHECKS*/ 67 #endif 68 69 #ifdef ENABLE_MEMLIST_CHECKS 70 /* uncomment the following for debugging: 71 * - CHECKMEM: run a thorough test on every memory function call, very slow 72 * - CHECKCHKFREE: check for the presence of a pointer in a chunk block 73 */ 74 /*#define CHECKMEM*/ 75 /*#define CHECKCHKFREE*/ 76 #endif 77 78 /* Uncomment the following for checks that clean buffer is really clean when being freed. */ 79 /* #define CHECKCLEANBUFFER */ 80 81 /* Uncomment the following for a warnings if buffers are not freed in the reverse order of allocation. */ 82 /* #define CHECKBUFFERORDER */ 83 84 /* if we are included in SCIP, use SCIP's message output methods */ 85 #ifdef SCIPdebugMessage 86 #define debugMessage SCIPdebugMessage 87 #define errorMessage SCIPerrorMessage 88 #else 89 #define debugMessage while( FALSE ) printf 90 #define errorMessage printf 91 #define printErrorHeader(f,l) printf("[%s:%d] ERROR: ", f, l) 92 #define printError printf 93 #endif 94 95 #ifdef ENABLE_MEMLIST_CHECKS 96 #define warningMessage printf 97 #endif 98 #define printInfo printf 99 100 /* define some macros (if not already defined) */ 101 #ifndef FALSE 102 #define FALSE 0 103 #define TRUE 1 104 #endif 105 #ifndef MAX 106 #define MAX(x,y) ((x) >= (y) ? (x) : (y)) 107 #define MIN(x,y) ((x) <= (y) ? (x) : (y)) 108 #endif 109 110 #ifndef SCIP_LONGINT_FORMAT 111 #if defined(_WIN32) || defined(_WIN64) 112 #define LONGINT_FORMAT "I64d" 113 #else 114 #define LONGINT_FORMAT "lld" 115 #endif 116 #else 117 #define LONGINT_FORMAT SCIP_LONGINT_FORMAT 118 #endif 119 120 #ifndef SCIP_MAXMEMSIZE 121 /* we take SIZE_MAX / 2 to detect negative sizes which got a very large value when casting to (unsigned) size_t */ 122 #define MAXMEMSIZE SIZE_MAX / 2 123 #else 124 #define MAXMEMSIZE SCIP_MAXMEMSIZE 125 #endif 126 127 /* define inline (if not already defined) */ 128 #ifndef INLINE 129 #if defined(_WIN32) || defined(_WIN64) || defined(__STDC__) 130 #define INLINE __inline 131 #else 132 #define INLINE inline 133 #endif 134 #endif 135 136 /************************************************************************************* 137 * Standard Memory Management 138 * 139 * In debug mode, these methods extend malloc() and free() by logging all currently 140 * allocated memory elements in an allocation list. This can be used as a simple leak 141 * detection. 142 *************************************************************************************/ 143 #if !defined(NDEBUG) && defined(ENABLE_MEMLIST_CHECKS) 144 145 typedef struct Memlist MEMLIST; /**< memory list for debugging purposes */ 146 147 /** memory list for debugging purposes */ 148 struct Memlist 149 { 150 const void* ptr; /**< pointer to allocated memory */ 151 size_t size; /**< size of memory element */ 152 char* filename; /**< source file where the allocation was performed */ 153 int line; /**< line number in source file where the allocation was performed */ 154 MEMLIST* next; /**< next entry in the memory list */ 155 }; 156 157 static MEMLIST* memlist = NULL; /**< global memory list for debugging purposes */ 158 static size_t memused = 0; /**< number of allocated bytes */ 159 160 #ifdef CHECKMEM 161 /** checks, whether the number of allocated bytes match the entries in the memory list */ 162 static 163 void checkMemlist( 164 void 165 ) 166 { 167 MEMLIST* list = memlist; 168 size_t used = 0; 169 170 while( list != NULL ) 171 { 172 used += list->size; 173 list = list->next; 174 } 175 assert(used == memused); 176 } 177 #else 178 #define checkMemlist() /**/ 179 #endif 180 181 /** adds entry to list of allocated memory */ 182 static 183 void addMemlistEntry( 184 const void* ptr, /**< pointer to allocated memory */ 185 size_t size, /**< size of memory element */ 186 const char* filename, /**< source file where the allocation was performed */ 187 int line /**< line number in source file where the allocation was performed */ 188 ) 189 { 190 MEMLIST* list; 191 192 assert(ptr != NULL && size > 0); 193 194 list = (MEMLIST*)malloc(sizeof(MEMLIST)); 195 assert(list != NULL); 196 197 list->ptr = ptr; 198 list->size = size; 199 list->filename = strdup(filename); 200 assert(list->filename != NULL); 201 list->line = line; 202 list->next = memlist; 203 memlist = list; 204 memused += size; 205 checkMemlist(); 206 } 207 208 /** removes entry from the list of allocated memory */ 209 static 210 void removeMemlistEntry( 211 const void* ptr, /**< pointer to allocated memory */ 212 const char* filename, /**< source file where the deallocation was performed */ 213 int line /**< line number in source file where the deallocation was performed */ 214 ) 215 { 216 MEMLIST* list; 217 MEMLIST** listptr; 218 219 assert(ptr != NULL); 220 221 list = memlist; 222 listptr = &memlist; 223 while( list != NULL && ptr != list->ptr ) 224 { 225 listptr = &(list->next); 226 list = list->next; 227 } 228 if( list != NULL ) 229 { 230 assert(ptr == list->ptr); 231 232 *listptr = list->next; 233 assert( list->size <= memused ); 234 memused -= list->size; 235 free(list->filename); 236 free(list); 237 } 238 else 239 { 240 printErrorHeader(filename, line); 241 printError("Tried to free unknown pointer <%p>.\n", ptr); 242 } 243 checkMemlist(); 244 } 245 246 /** returns the size of an allocated memory element */ 247 size_t BMSgetPointerSize_call( 248 const void* ptr /**< pointer to allocated memory */ 249 ) 250 { 251 MEMLIST* list; 252 253 list = memlist; 254 while( list != NULL && ptr != list->ptr ) 255 list = list->next; 256 if( list != NULL ) 257 return list->size; 258 else 259 return 0; 260 } 261 262 /** outputs information about currently allocated memory to the screen */ 263 void BMSdisplayMemory_call( 264 void 265 ) 266 { 267 MEMLIST* list; 268 size_t used = 0; 269 270 printInfo("Allocated memory:\n"); 271 list = memlist; 272 while( list != NULL ) 273 { 274 printInfo("%12p %8llu %s:%d\n", list->ptr, (unsigned long long) list->size, list->filename, list->line); 275 used += list->size; 276 list = list->next; 277 } 278 printInfo("Total: %8llu\n", (unsigned long long) memused); 279 if( used != memused ) 280 { 281 errorMessage("Used memory in list sums up to %llu instead of %llu\n", (unsigned long long)used, (unsigned long long)memused); 282 } 283 checkMemlist(); 284 } 285 286 /** displays a warning message on the screen, if allocated memory exists */ 287 void BMScheckEmptyMemory_call( 288 void 289 ) 290 { 291 if( memlist != NULL || memused > 0 ) 292 { 293 warningMessage("Memory list not empty.\n"); 294 BMSdisplayMemory_call(); 295 } 296 } 297 298 /** returns total number of allocated bytes */ 299 long long BMSgetMemoryUsed_call( 300 void 301 ) 302 { 303 return (long long) memused; 304 } 305 306 #else 307 308 #define addMemlistEntry(ptr, size, filename, line) do { (void) (ptr); (void) (size); (void) (filename); (void) (line); } while(0) 309 #define removeMemlistEntry(ptr, filename, line) do { (void) (ptr); (void) (filename); (void) (line); } while(0) 310 311 /* these methods are implemented even in optimized mode, such that a program, that includes memory.h in debug mode 312 * but links the optimized version compiles 313 */ 314 315 /** returns the size of an allocated memory element */ 316 size_t BMSgetPointerSize_call( 317 const void* ptr /**< pointer to allocated memory */ 318 ) 319 { 320 (void) ptr; 321 return 0; 322 } 323 324 /** outputs information about currently allocated memory to the screen */ 325 void BMSdisplayMemory_call( 326 void 327 ) 328 { 329 printInfo("Optimized, threadsafe version of memory shell linked - no memory diagnostics available.\n"); 330 } 331 332 /** displays a warning message on the screen, if allocated memory exists */ 333 void BMScheckEmptyMemory_call( 334 void 335 ) 336 { 337 } 338 339 /** returns total number of allocated bytes */ 340 long long BMSgetMemoryUsed_call( 341 void 342 ) 343 { 344 return 0; 345 } 346 347 #endif 348 349 /** allocates array and initializes it with 0; returns NULL if memory allocation failed */ 350 void* BMSallocClearMemory_call( 351 size_t num, /**< number of memory element to allocate */ 352 size_t typesize, /**< size of one memory element to allocate */ 353 const char* filename, /**< source file where the allocation is performed */ 354 int line /**< line number in source file where the allocation is performed */ 355 ) 356 { 357 void* ptr; 358 359 assert(typesize > 0); 360 361 debugMessage("calloc %llu elements of %llu bytes [%s:%d]\n", (unsigned long long)num, (unsigned long long)typesize, 362 filename, line); 363 364 #ifndef NDEBUG 365 if ( num > (MAXMEMSIZE / typesize) ) 366 { 367 printErrorHeader(filename, line); 368 printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE); 369 return NULL; 370 } 371 #endif 372 373 num = MAX(num, 1); 374 typesize = MAX(typesize, 1); 375 ptr = calloc(num, typesize); 376 377 if( ptr == NULL ) 378 { 379 printErrorHeader(filename, line); 380 printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)(num) * (typesize)); 381 } 382 else 383 addMemlistEntry(ptr, num*typesize, filename, line); 384 385 return ptr; 386 } 387 388 /** allocates memory; returns NULL if memory allocation failed */ 389 void* BMSallocMemory_call( 390 size_t size, /**< size of memory element to allocate */ 391 const char* filename, /**< source file where the allocation is performed */ 392 int line /**< line number in source file where the allocation is performed */ 393 ) 394 { 395 void* ptr; 396 397 debugMessage("malloc %llu bytes [%s:%d]\n", (unsigned long long)size, filename, line); 398 399 #ifndef NDEBUG 400 if ( size > MAXMEMSIZE ) 401 { 402 printErrorHeader(filename, line); 403 printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE); 404 return NULL; 405 } 406 #endif 407 408 size = MAX(size, 1); 409 ptr = malloc(size); 410 411 if( ptr == NULL ) 412 { 413 printErrorHeader(filename, line); 414 printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)size); 415 } 416 else 417 addMemlistEntry(ptr, size, filename, line); 418 419 return ptr; 420 } 421 422 /** allocates array; returns NULL if memory allocation failed */ 423 void* BMSallocMemoryArray_call( 424 size_t num, /**< number of components of array to allocate */ 425 size_t typesize, /**< size of each component */ 426 const char* filename, /**< source file where the allocation is performed */ 427 int line /**< line number in source file where the allocation is performed */ 428 ) 429 { 430 void* ptr; 431 size_t size; 432 433 debugMessage("malloc %llu elements of %llu bytes [%s:%d]\n", 434 (unsigned long long)num, (unsigned long long)typesize, filename, line); 435 436 #ifndef NDEBUG 437 if ( num > (MAXMEMSIZE / typesize) ) 438 { 439 printErrorHeader(filename, line); 440 printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE); 441 return NULL; 442 } 443 #endif 444 445 size = num * typesize; 446 size = MAX(size, 1); 447 ptr = malloc(size); 448 449 if( ptr == NULL ) 450 { 451 printErrorHeader(filename, line); 452 printError("Insufficient memory for allocation of %llu bytes.\n", (unsigned long long)size); 453 } 454 else 455 addMemlistEntry(ptr, size, filename, line); 456 457 return ptr; 458 } 459 460 /** allocates memory; returns NULL if memory allocation failed */ 461 void* BMSreallocMemory_call( 462 void* ptr, /**< pointer to memory to reallocate */ 463 size_t size, /**< new size of memory element */ 464 const char* filename, /**< source file where the reallocation is performed */ 465 int line /**< line number in source file where the reallocation is performed */ 466 ) 467 { 468 void* newptr; 469 470 if( ptr != NULL ) 471 removeMemlistEntry(ptr, filename, line); 472 473 #ifndef NDEBUG 474 if ( size > MAXMEMSIZE ) 475 { 476 printErrorHeader(filename, line); 477 printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE); 478 return NULL; 479 } 480 #endif 481 482 size = MAX(size, 1); 483 newptr = realloc(ptr, size); 484 485 if( newptr == NULL ) 486 { 487 printErrorHeader(filename, line); 488 printError("Insufficient memory for reallocation of %llu bytes.\n", (unsigned long long)size); 489 } 490 else 491 addMemlistEntry(newptr, size, filename, line); 492 493 return newptr; 494 } 495 496 /** reallocates array; returns NULL if memory allocation failed */ 497 void* BMSreallocMemoryArray_call( 498 void* ptr, /**< pointer to memory to reallocate */ 499 size_t num, /**< number of components of array to allocate */ 500 size_t typesize, /**< size of each component */ 501 const char* filename, /**< source file where the reallocation is performed */ 502 int line /**< line number in source file where the reallocation is performed */ 503 ) 504 { 505 void* newptr; 506 size_t size; 507 508 if( ptr != NULL ) 509 removeMemlistEntry(ptr, filename, line); 510 511 #ifndef NDEBUG 512 if ( num > (MAXMEMSIZE / typesize) ) 513 { 514 printErrorHeader(filename, line); 515 printError("Tried to allocate standard memory of size exceeding %lu.\n", MAXMEMSIZE); 516 return NULL; 517 } 518 #endif 519 520 size = num * typesize; 521 size = MAX(size, 1); 522 newptr = realloc(ptr, size); 523 524 if( newptr == NULL ) 525 { 526 printErrorHeader(filename, line); 527 printError("Insufficient memory for reallocation of %llu bytes.\n", (unsigned long long)size); 528 } 529 else 530 addMemlistEntry(newptr, size, filename, line); 531 532 return newptr; 533 } 534 535 /** clears a memory element (i.e. fills it with zeros) */ 536 void BMSclearMemory_call( 537 void* ptr, /**< pointer to memory element */ 538 size_t size /**< size of memory element */ 539 ) 540 { 541 if( size > 0 ) 542 { 543 assert(ptr != NULL); 544 memset(ptr, 0, size); 545 } 546 } 547 548 /** copies the contents of one memory element into another memory element */ 549 void BMScopyMemory_call( 550 void* ptr, /**< pointer to target memory element */ 551 const void* source, /**< pointer to source memory element */ 552 size_t size /**< size of memory element to copy */ 553 ) 554 { 555 if( size > 0 ) 556 { 557 assert(ptr != NULL); 558 assert(source != NULL); 559 memcpy(ptr, source, size); 560 } 561 } 562 563 /** moves the contents of one memory element into another memory element, should be used if both elements overlap, 564 * otherwise BMScopyMemory is faster 565 */ 566 void BMSmoveMemory_call( 567 void* ptr, /**< pointer to target memory element */ 568 const void* source, /**< pointer to source memory element */ 569 size_t size /**< size of memory element to copy */ 570 ) 571 { 572 if( size > 0 ) 573 { 574 assert(ptr != NULL); 575 assert(source != NULL); 576 memmove(ptr, source, size); 577 } 578 } 579 580 /** allocates memory and copies the contents of the given memory element into the new memory element */ 581 void* BMSduplicateMemory_call( 582 const void* source, /**< pointer to source memory element */ 583 size_t size, /**< size of memory element to copy */ 584 const char* filename, /**< source file where the duplication is performed */ 585 int line /**< line number in source file where the duplication is performed */ 586 ) 587 { 588 void* ptr; 589 590 assert(source != NULL || size == 0); 591 592 ptr = BMSallocMemory_call(size, filename, line); 593 if( ptr != NULL ) 594 BMScopyMemory_call(ptr, source, size); 595 596 return ptr; 597 } 598 599 /** allocates array and copies the contents of the given source array into the new array */ 600 void* BMSduplicateMemoryArray_call( 601 const void* source, /**< pointer to source memory element */ 602 size_t num, /**< number of components of array to allocate */ 603 size_t typesize, /**< size of each component */ 604 const char* filename, /**< source file where the duplication is performed */ 605 int line /**< line number in source file where the duplication is performed */ 606 ) 607 { 608 void* ptr; 609 610 assert(source != NULL || num == 0); 611 612 ptr = BMSallocMemoryArray_call(num, typesize, filename, line); 613 if( ptr != NULL ) 614 BMScopyMemory_call(ptr, source, num * typesize); 615 616 return ptr; 617 } 618 619 /** frees an allocated memory element and sets pointer to NULL */ 620 void BMSfreeMemory_call( 621 void** ptr, /**< pointer to pointer to memory element */ 622 const char* filename, /**< source file where the deallocation is performed */ 623 int line /**< line number in source file where the deallocation is performed */ 624 ) 625 { 626 assert( ptr != NULL ); 627 if( *ptr != NULL ) 628 { 629 removeMemlistEntry(*ptr, filename, line); 630 631 free(*ptr); 632 *ptr = NULL; 633 } 634 else 635 { 636 printErrorHeader(filename, line); 637 printError("Tried to free null pointer.\n"); 638 } 639 } 640 641 /** frees an allocated memory element if pointer is not NULL and sets pointer to NULL */ 642 void BMSfreeMemoryNull_call( 643 void** ptr, /**< pointer to pointer to memory element */ 644 const char* filename, /**< source file where the deallocation is performed */ 645 int line /**< line number in source file where the deallocation is performed */ 646 ) 647 { 648 assert( ptr != NULL ); 649 if ( *ptr != NULL ) 650 { 651 removeMemlistEntry(*ptr, filename, line); 652 653 free(*ptr); 654 *ptr = NULL; 655 } 656 } 657 658 659 /*********************************************************** 660 * Block Memory Management (forward declaration) 661 * 662 * Efficient memory management for objects of varying sizes 663 ***********************************************************/ 664 665 #define CHKHASH_POWER 10 /**< power for size of chunk block hash table */ 666 #define CHKHASH_SIZE (1<<CHKHASH_POWER) /**< size of chunk block hash table is 2^CHKHASH_POWER */ 667 668 /** collection of chunk blocks */ 669 struct BMS_BlkMem 670 { 671 BMS_CHKMEM* chkmemhash[CHKHASH_SIZE]; /**< hash table with chunk blocks */ 672 long long memused; /**< total number of used bytes in the memory header */ 673 long long memallocated; /**< total number of allocated bytes in the memory header */ 674 long long maxmemused; /**< maximal number of used bytes in the memory header */ 675 long long maxmemunused; /**< maximal number of allocated but not used bytes in the memory header */ 676 long long maxmemallocated; /**< maximal number of allocated bytes in the memory header */ 677 int initchunksize; /**< number of elements in the first chunk of each chunk block */ 678 int garbagefactor; /**< garbage collector is called, if at least garbagefactor * avg. chunksize 679 * elements are free (-1: disable garbage collection) */ 680 }; 681 682 683 /******************************************************************** 684 * Chunk Memory Management 685 * 686 * Efficient memory management for multiple objects of the same size 687 ********************************************************************/ 688 689 /* 690 * block memory methods for faster memory access 691 */ 692 693 #define CHUNKLENGTH_MIN 1024 /**< minimal size of a chunk (in bytes) */ 694 #define CHUNKLENGTH_MAX 1048576 /**< maximal size of a chunk (in bytes) */ 695 #define STORESIZE_MAX 8192 /**< maximal number of elements in one chunk */ 696 #define GARBAGE_SIZE 256 /**< size of lazy free list to start garbage collection */ 697 #define ALIGNMENT (sizeof(FREELIST)) /**< minimal alignment of chunks */ 698 699 typedef struct Freelist FREELIST; /**< linked list of free memory elements */ 700 typedef struct Chunk CHUNK; /**< chunk of memory elements */ 701 702 /** linked list of free memory elements */ 703 struct Freelist 704 { 705 FREELIST* next; /**< pointer to the next free element */ 706 }; 707 708 /** chunk of memory elements */ 709 struct Chunk 710 { 711 SCIP_RBTREE_HOOKS; /**< organize chunks in a red black tree */ /*lint !e768 */ 712 void* store; /**< data storage */ 713 void* storeend; /**< points to the first byte in memory not belonging to the chunk */ 714 FREELIST* eagerfree; /**< eager free list */ 715 CHUNK* nexteager; /**< next chunk, that has a non-empty eager free list */ 716 CHUNK* preveager; /**< previous chunk, that has a non-empty eager free list */ 717 BMS_CHKMEM* chkmem; /**< chunk memory collection, this chunk belongs to */ 718 int elemsize; /**< size of each element in the chunk */ 719 int storesize; /**< number of elements in this chunk */ 720 int eagerfreesize; /**< number of elements in the eager free list */ 721 }; /* the chunk data structure must be aligned, because the storage is allocated directly behind the chunk header! */ 722 723 /** collection of memory chunks of the same element size */ 724 struct BMS_ChkMem 725 { 726 CHUNK* rootchunk; /**< array with the chunks of the chunk header */ 727 FREELIST* lazyfree; /**< lazy free list of unused memory elements of all chunks of this chunk block */ 728 CHUNK* firsteager; /**< first chunk with a non-empty eager free list */ 729 BMS_CHKMEM* nextchkmem; /**< next chunk block in the block memory's hash list */ 730 int elemsize; /**< size of each memory element in the chunk memory */ 731 int nchunks; /**< number of chunks in this chunk block (used slots of the chunk array) */ 732 int lastchunksize; /**< number of elements in the last allocated chunk */ 733 int storesize; /**< total number of elements in this chunk block */ 734 int lazyfreesize; /**< number of elements in the lazy free list of the chunk block */ 735 int eagerfreesize; /**< total number of elements of all eager free lists of the block's chunks */ 736 int initchunksize; /**< number of elements in the first chunk */ 737 int garbagefactor; /**< garbage collector is called, if at least garbagefactor * avg. chunksize 738 * elements are free (-1: disable garbage collection) */ 739 #ifndef NDEBUG 740 char* filename; /**< source file, where this chunk block was created */ 741 int line; /**< source line, where this chunk block was created */ 742 int ngarbagecalls; /**< number of times, the garbage collector was called */ 743 int ngarbagefrees; /**< number of chunks, the garbage collector freed */ 744 #endif 745 }; 746 747 /* define a find function to find a chunk in a red black tree of chunks */ 748 #define CHUNK_LT(ptr,chunk) ptr < chunk->store 749 #define CHUNK_GT(ptr,chunk) ptr >= chunk->storeend 750 751 static 752 SCIP_DEF_RBTREE_FIND(rbTreeFindChunk, const void*, CHUNK, CHUNK_LT, CHUNK_GT) /*lint !e123*/ 753 754 755 /** aligns the given byte size corresponding to the minimal alignment */ 756 static 757 void alignSize( 758 size_t* size /**< pointer to the size to align */ 759 ) 760 { 761 if( *size < ALIGNMENT ) 762 *size = ALIGNMENT; 763 else 764 *size = ((*size + ALIGNMENT - 1) / ALIGNMENT) * ALIGNMENT; 765 } 766 767 /** aligns the given byte size corresponding to the minimal alignment for chunk and block memory */ 768 void BMSalignMemsize( 769 size_t* size /**< pointer to the size to align */ 770 ) 771 { 772 assert(ALIGNMENT == sizeof(void*)); /*lint !e506*/ 773 alignSize(size); 774 } 775 776 /** checks whether the given size meets the alignment conditions for chunk and block memory */ 777 int BMSisAligned( 778 size_t size /**< size to check for alignment */ 779 ) 780 { 781 assert(ALIGNMENT == sizeof(void*)); /*lint !e506*/ 782 return( size >= ALIGNMENT && size % ALIGNMENT == 0 ); 783 } 784 785 #ifndef NDEBUG 786 /** checks, if the given pointer belongs to the given chunk */ 787 static 788 int isPtrInChunk( 789 const CHUNK* chunk, /**< memory chunk */ 790 const void* ptr /**< pointer */ 791 ) 792 { 793 assert(chunk != NULL); 794 assert(chunk->store <= chunk->storeend); 795 796 return (ptr >= (void*)(chunk->store) && ptr < (void*)(chunk->storeend)); 797 } 798 #endif 799 800 /** given a pointer, finds the chunk this pointer points to in the chunk array of the given chunk block; 801 * binary search is used; 802 * returns NULL if the pointer does not belong to the chunk block 803 */ 804 static 805 CHUNK* findChunk( 806 const BMS_CHKMEM* chkmem, /**< chunk block */ 807 const void* ptr /**< pointer */ 808 ) 809 { 810 CHUNK* chunk; 811 812 assert(chkmem != NULL); 813 assert(ptr != NULL); 814 815 if( rbTreeFindChunk(chkmem->rootchunk, ptr, &chunk) == 0 ) 816 return chunk; 817 818 /* ptr was not found in chunk */ 819 return NULL; 820 } 821 822 /** checks, if a pointer belongs to a chunk of the given chunk block */ 823 static 824 int isPtrInChkmem( 825 const BMS_CHKMEM* chkmem, /**< chunk block */ 826 const void* ptr /**< pointer */ 827 ) 828 { 829 assert(chkmem != NULL); 830 831 return (findChunk(chkmem, ptr) != NULL); 832 } 833 834 835 836 /* 837 * debugging methods 838 */ 839 840 #ifdef CHECKMEM 841 /** sanity check for a memory chunk */ 842 static 843 void checkChunk( 844 const CHUNK* chunk /**< memory chunk */ 845 ) 846 { 847 FREELIST* eager; 848 int eagerfreesize; 849 850 assert(chunk != NULL); 851 assert(chunk->store != NULL); 852 assert(chunk->storeend == (void*)((char*)(chunk->store) + chunk->elemsize * chunk->storesize)); 853 assert(chunk->chkmem != NULL); 854 assert(chunk->chkmem->elemsize == chunk->elemsize); 855 856 if( chunk->eagerfree == NULL ) 857 assert(chunk->nexteager == NULL && chunk->preveager == NULL); 858 else if( chunk->preveager == NULL ) 859 assert(chunk->chkmem->firsteager == chunk); 860 861 if( chunk->nexteager != NULL ) 862 assert(chunk->nexteager->preveager == chunk); 863 if( chunk->preveager != NULL ) 864 assert(chunk->preveager->nexteager == chunk); 865 866 eagerfreesize = 0; 867 eager = chunk->eagerfree; 868 while( eager != NULL ) 869 { 870 assert(isPtrInChunk(chunk, eager)); 871 eagerfreesize++; 872 eager = eager->next; 873 } 874 assert(chunk->eagerfreesize == eagerfreesize); 875 } 876 877 /** sanity check for a chunk block */ 878 static 879 void checkChkmem( 880 const BMS_CHKMEM* chkmem /**< chunk block */ 881 ) 882 { 883 FREELIST* lazy; 884 int nchunks; 885 int storesize; 886 int lazyfreesize; 887 int eagerfreesize; 888 889 assert(chkmem != NULL); 890 891 nchunks = 0; 892 storesize = 0; 893 lazyfreesize = 0; 894 eagerfreesize = 0; 895 896 FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk, 897 { 898 checkChunk(chunk); 899 nchunks++; 900 storesize += chunk->storesize; 901 eagerfreesize += chunk->eagerfreesize; 902 }) 903 904 assert(chkmem->nchunks == nchunks); 905 assert(chkmem->storesize == storesize); 906 assert(chkmem->eagerfreesize == eagerfreesize); 907 908 assert(((unsigned int) (chkmem->eagerfreesize == 0)) ^ ( (unsigned int) (chkmem->firsteager != NULL))); 909 910 if( chkmem->firsteager != NULL ) 911 assert(chkmem->firsteager->preveager == NULL); 912 913 lazy = chkmem->lazyfree; 914 while( lazy != NULL ) 915 { 916 CHUNK* chunk = findChunk(chkmem, lazy); 917 assert(chunk != NULL); 918 assert(chunk->chkmem == chkmem); 919 lazyfreesize++; 920 lazy = lazy->next; 921 } 922 assert(chkmem->lazyfreesize == lazyfreesize); 923 } 924 #else 925 #define checkChunk(chunk) /**/ 926 #define checkChkmem(chkmem) /**/ 927 #endif 928 929 930 /** links chunk to the block's chunk array, sort it by store pointer; 931 * returns TRUE if successful, FALSE otherwise 932 */ 933 static 934 int linkChunk( 935 BMS_CHKMEM* chkmem, /**< chunk block */ 936 CHUNK* chunk /**< memory chunk */ 937 ) 938 { 939 CHUNK* parent; 940 int pos; 941 942 assert(chkmem != NULL); 943 assert(chunk != NULL); 944 assert(chunk->store != NULL); 945 946 debugMessage("linking chunk %p to chunk block %p [elemsize:%d, %d chunks]\n", 947 (void*)chunk, (void*)chkmem, chkmem->elemsize, chkmem->nchunks); 948 949 pos = rbTreeFindChunk(chkmem->rootchunk, chunk->store, &parent); 950 assert(pos != 0); 951 952 SCIPrbtreeInsert(&chkmem->rootchunk, parent, pos, chunk); 953 954 chkmem->nchunks++; 955 chkmem->storesize += chunk->storesize; 956 957 return TRUE; 958 } 959 960 /** unlinks chunk from the chunk block's chunk list */ 961 static 962 void unlinkChunk( 963 CHUNK* chunk /**< memory chunk */ 964 ) 965 { 966 BMS_CHKMEM* chkmem; 967 968 assert(chunk != NULL); 969 assert(chunk->eagerfree == NULL); 970 assert(chunk->nexteager == NULL); 971 assert(chunk->preveager == NULL); 972 973 chkmem = chunk->chkmem; 974 assert(chkmem != NULL); 975 assert(chkmem->elemsize == chunk->elemsize); 976 977 debugMessage("unlinking chunk %p from chunk block %p [elemsize:%d, %d chunks]\n", 978 (void*)chunk, (void*)chkmem, chkmem->elemsize, chkmem->nchunks); 979 980 /* remove the chunk from the chunks of the chunk block */ 981 SCIPrbtreeDelete(&chkmem->rootchunk, chunk); 982 983 chkmem->nchunks--; 984 chkmem->storesize -= chunk->storesize; 985 } 986 987 /** links chunk to the chunk block's eager chunk list */ 988 static 989 void linkEagerChunk( 990 BMS_CHKMEM* chkmem, /**< chunk block */ 991 CHUNK* chunk /**< memory chunk */ 992 ) 993 { 994 assert(chunk->chkmem == chkmem); 995 assert(chunk->nexteager == NULL); 996 assert(chunk->preveager == NULL); 997 998 chunk->nexteager = chkmem->firsteager; 999 chunk->preveager = NULL; 1000 if( chkmem->firsteager != NULL ) 1001 { 1002 assert(chkmem->firsteager->preveager == NULL); 1003 chkmem->firsteager->preveager = chunk; 1004 } 1005 chkmem->firsteager = chunk; 1006 } 1007 1008 /** unlinks chunk from the chunk block's eager chunk list */ 1009 static 1010 void unlinkEagerChunk( 1011 CHUNK* chunk /**< memory chunk */ 1012 ) 1013 { 1014 assert(chunk != NULL); 1015 assert(chunk->eagerfreesize == 0 || chunk->eagerfreesize == chunk->storesize); 1016 1017 if( chunk->nexteager != NULL ) 1018 chunk->nexteager->preveager = chunk->preveager; 1019 if( chunk->preveager != NULL ) 1020 chunk->preveager->nexteager = chunk->nexteager; 1021 else 1022 { 1023 assert(chunk->chkmem->firsteager == chunk); 1024 chunk->chkmem->firsteager = chunk->nexteager; 1025 } 1026 chunk->nexteager = NULL; 1027 chunk->preveager = NULL; 1028 chunk->eagerfree = NULL; 1029 } 1030 1031 /** creates a new memory chunk in the given chunk block and adds memory elements to the lazy free list; 1032 * returns TRUE if successful, FALSE otherwise 1033 */ 1034 static 1035 int createChunk( 1036 BMS_CHKMEM* chkmem, /**< chunk block */ 1037 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1038 ) 1039 { 1040 CHUNK *newchunk; 1041 FREELIST *freelist; 1042 int i; 1043 int storesize; 1044 int retval; 1045 1046 assert(chkmem != NULL); 1047 1048 debugMessage("creating new chunk in chunk block %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize); 1049 1050 /* calculate store size */ 1051 if( chkmem->nchunks == 0 ) 1052 storesize = chkmem->initchunksize; 1053 else 1054 storesize = 2 * chkmem->lastchunksize; 1055 assert(storesize > 0); 1056 storesize = MAX(storesize, CHUNKLENGTH_MIN / chkmem->elemsize); 1057 storesize = MIN(storesize, CHUNKLENGTH_MAX / chkmem->elemsize); 1058 storesize = MIN(storesize, STORESIZE_MAX); 1059 storesize = MAX(storesize, 1); 1060 chkmem->lastchunksize = storesize; 1061 1062 /* create new chunk */ 1063 assert(BMSisAligned(sizeof(CHUNK))); 1064 assert( chkmem->elemsize < INT_MAX / storesize ); 1065 assert( sizeof(CHUNK) < MAXMEMSIZE - (size_t)(storesize * chkmem->elemsize) ); /*lint !e571 !e647*/ 1066 BMSallocMemorySize(&newchunk, sizeof(CHUNK) + storesize * chkmem->elemsize); 1067 if( newchunk == NULL ) 1068 return FALSE; 1069 1070 /* the store is allocated directly behind the chunk header */ 1071 newchunk->store = (void*) ((char*) newchunk + sizeof(CHUNK)); 1072 newchunk->storeend = (void*) ((char*) newchunk->store + (ptrdiff_t)storesize * chkmem->elemsize); 1073 newchunk->eagerfree = NULL; 1074 newchunk->nexteager = NULL; 1075 newchunk->preveager = NULL; 1076 newchunk->chkmem = chkmem; 1077 newchunk->elemsize = chkmem->elemsize; 1078 newchunk->storesize = storesize; 1079 newchunk->eagerfreesize = 0; 1080 1081 if( memsize != NULL ) 1082 (*memsize) += ((long long)((long long)sizeof(CHUNK) + (long long)storesize * chkmem->elemsize)); 1083 1084 debugMessage("allocated new chunk %p: %d elements with size %d\n", (void*)newchunk, newchunk->storesize, newchunk->elemsize); 1085 1086 /* add new memory to the lazy free list 1087 * (due to the BMSisAligned assert above, we know that elemsize is divisible by the size of pointers) 1088 */ 1089 for( i = 0; i < newchunk->storesize - 1; ++i ) 1090 { 1091 freelist = (FREELIST*) newchunk->store + (ptrdiff_t)i * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/ 1092 freelist->next = (FREELIST*) newchunk->store + ((ptrdiff_t)i + 1) * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/ 1093 } 1094 1095 freelist = (FREELIST*) newchunk->store + ((ptrdiff_t) newchunk->storesize - 1) * chkmem->elemsize / (ptrdiff_t)sizeof(FREELIST*); /*lint !e573 !e647*/ 1096 freelist->next = chkmem->lazyfree; 1097 chkmem->lazyfree = (FREELIST*) (newchunk->store); 1098 chkmem->lazyfreesize += newchunk->storesize; 1099 1100 /* link chunk into chunk block */ 1101 retval = linkChunk(chkmem, newchunk); 1102 1103 checkChkmem(chkmem); 1104 1105 return retval; 1106 } 1107 1108 /** destroys a chunk without updating the chunk lists */ 1109 static 1110 void destroyChunk( 1111 CHUNK** chunk, /**< memory chunk */ 1112 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1113 ) 1114 { 1115 assert(chunk != NULL); 1116 assert(*chunk != NULL); 1117 1118 debugMessage("destroying chunk %p\n", (void*)*chunk); 1119 1120 if( memsize != NULL ) 1121 (*memsize) -= ((long long)sizeof(CHUNK) + (long long)(*chunk)->storesize * (*chunk)->elemsize); 1122 1123 /* free chunk header and store (allocated in one call) */ 1124 BMSfreeMemory(chunk); 1125 } 1126 1127 /** removes a completely unused chunk, i.e. a chunk with all elements in the eager free list */ 1128 static 1129 void freeChunk( 1130 CHUNK** chunk, /**< memory chunk */ 1131 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1132 ) 1133 { 1134 assert(chunk != NULL); 1135 assert(*chunk != NULL); 1136 assert((*chunk)->store != NULL); 1137 assert((*chunk)->eagerfree != NULL); 1138 assert((*chunk)->chkmem != NULL); 1139 assert((*chunk)->chkmem->rootchunk != NULL); 1140 assert((*chunk)->chkmem->firsteager != NULL); 1141 assert((*chunk)->eagerfreesize == (*chunk)->storesize); 1142 1143 debugMessage("freeing chunk %p of chunk block %p [elemsize: %d]\n", (void*)*chunk, (void*)(*chunk)->chkmem, (*chunk)->chkmem->elemsize); 1144 1145 /* count the deleted eager free slots */ 1146 (*chunk)->chkmem->eagerfreesize -= (*chunk)->eagerfreesize; 1147 assert((*chunk)->chkmem->eagerfreesize >= 0); 1148 1149 /* remove chunk from eager chunk list */ 1150 unlinkEagerChunk(*chunk); 1151 1152 /* remove chunk from chunk list */ 1153 unlinkChunk(*chunk); 1154 1155 /* destroy the chunk */ 1156 destroyChunk(chunk, memsize); 1157 } 1158 1159 /** returns an element of the eager free list and removes it from the list */ 1160 static 1161 void* allocChunkElement( 1162 CHUNK* chunk /**< memory chunk */ 1163 ) 1164 { 1165 FREELIST* ptr; 1166 1167 assert(chunk != NULL); 1168 assert(chunk->eagerfree != NULL); 1169 assert(chunk->eagerfreesize > 0); 1170 assert(chunk->chkmem != NULL); 1171 1172 debugMessage("allocating chunk element in chunk %p [elemsize: %d]\n", (void*)chunk, chunk->chkmem->elemsize); 1173 1174 /* unlink first element in the eager free list */ 1175 ptr = chunk->eagerfree; 1176 chunk->eagerfree = ptr->next; 1177 chunk->eagerfreesize--; 1178 chunk->chkmem->eagerfreesize--; 1179 1180 assert((chunk->eagerfreesize == 0 && chunk->eagerfree == NULL) 1181 || (chunk->eagerfreesize != 0 && chunk->eagerfree != NULL)); 1182 assert(chunk->chkmem->eagerfreesize >= 0); 1183 1184 /* unlink chunk from eager chunk list if necessary */ 1185 if( chunk->eagerfree == NULL ) 1186 { 1187 assert(chunk->eagerfreesize == 0); 1188 unlinkEagerChunk(chunk); 1189 } 1190 1191 checkChunk(chunk); 1192 1193 return (void*) ptr; 1194 } 1195 1196 /** puts given pointer into the eager free list and adds the chunk to the eager list of its chunk block, if necessary */ 1197 static 1198 void freeChunkElement( 1199 CHUNK* chunk, /**< memory chunk */ 1200 void* ptr /**< pointer */ 1201 ) 1202 { 1203 assert(chunk != NULL); 1204 assert(chunk->chkmem != NULL); 1205 assert(isPtrInChunk(chunk, ptr)); 1206 1207 debugMessage("freeing chunk element %p of chunk %p [elemsize: %d]\n", (void*)ptr, (void*)chunk, chunk->chkmem->elemsize); 1208 1209 /* link chunk to the eager chunk list if necessary */ 1210 if( chunk->eagerfree == NULL ) 1211 { 1212 assert(chunk->eagerfreesize == 0); 1213 linkEagerChunk(chunk->chkmem, chunk); 1214 } 1215 1216 /* add ptr to the chunks eager free list */ 1217 ((FREELIST*)ptr)->next = chunk->eagerfree; 1218 chunk->eagerfree = (FREELIST*)ptr; 1219 chunk->eagerfreesize++; 1220 chunk->chkmem->eagerfreesize++; 1221 1222 checkChunk(chunk); 1223 } 1224 1225 /** creates a new chunk block data structure */ 1226 static 1227 BMS_CHKMEM* createChkmem( 1228 int size, /**< element size of the chunk block */ 1229 int initchunksize, /**< number of elements in the first chunk of the chunk block */ 1230 int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize 1231 * elements are free (-1: disable garbage collection) */ 1232 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1233 ) 1234 { 1235 BMS_CHKMEM* chkmem; 1236 1237 assert(size >= 0); 1238 assert(BMSisAligned((size_t)size)); /*lint !e571*/ 1239 1240 BMSallocMemory(&chkmem); 1241 if( chkmem == NULL ) 1242 return NULL; 1243 1244 chkmem->lazyfree = NULL; 1245 chkmem->rootchunk = NULL; 1246 chkmem->firsteager = NULL; 1247 chkmem->nextchkmem = NULL; 1248 chkmem->elemsize = size; 1249 chkmem->nchunks = 0; 1250 chkmem->lastchunksize = 0; 1251 chkmem->storesize = 0; 1252 chkmem->lazyfreesize = 0; 1253 chkmem->eagerfreesize = 0; 1254 chkmem->initchunksize = initchunksize; 1255 chkmem->garbagefactor = garbagefactor; 1256 #ifndef NDEBUG 1257 chkmem->filename = NULL; 1258 chkmem->line = 0; 1259 chkmem->ngarbagecalls = 0; 1260 chkmem->ngarbagefrees = 0; 1261 #endif 1262 1263 if( memsize != NULL ) 1264 (*memsize) += (long long)sizeof(BMS_CHKMEM); 1265 1266 return chkmem; 1267 } 1268 1269 /** destroys all chunks of the chunk block, but keeps the chunk block header structure */ 1270 static 1271 void clearChkmem( 1272 BMS_CHKMEM* chkmem, /**< chunk block */ 1273 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1274 ) 1275 { 1276 assert(chkmem != NULL); 1277 1278 /* destroy all chunks of the chunk block */ 1279 FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk, 1280 { 1281 SCIPrbtreeDelete(&chkmem->rootchunk, chunk); 1282 destroyChunk(&chunk, memsize); 1283 }) 1284 1285 chkmem->lazyfree = NULL; 1286 chkmem->firsteager = NULL; 1287 chkmem->nchunks = 0; 1288 chkmem->lastchunksize = 0; 1289 chkmem->storesize = 0; 1290 chkmem->lazyfreesize = 0; 1291 chkmem->eagerfreesize = 0; 1292 } 1293 1294 /** deletes chunk block and frees all associated memory chunks */ 1295 static 1296 void destroyChkmem( 1297 BMS_CHKMEM** chkmem, /**< pointer to chunk block */ 1298 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1299 ) 1300 { 1301 assert(chkmem != NULL); 1302 assert(*chkmem != NULL); 1303 1304 clearChkmem(*chkmem, memsize); 1305 1306 #ifndef NDEBUG 1307 BMSfreeMemoryArrayNull(&(*chkmem)->filename); 1308 #endif 1309 1310 if( memsize != NULL ) 1311 (*memsize) -= (long long)(sizeof(BMS_CHKMEM)); 1312 1313 BMSfreeMemory(chkmem); 1314 } 1315 1316 /** allocates a new memory element from the chunk block */ 1317 static 1318 void* allocChkmemElement( 1319 BMS_CHKMEM* chkmem, /**< chunk block */ 1320 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1321 ) 1322 { 1323 FREELIST* ptr; 1324 1325 assert(chkmem != NULL); 1326 1327 /* if the lazy freelist is empty, we have to find the memory element somewhere else */ 1328 if( chkmem->lazyfree == NULL ) 1329 { 1330 assert(chkmem->lazyfreesize == 0); 1331 1332 /* check for a free element in the eager freelists */ 1333 if( chkmem->firsteager != NULL ) 1334 return allocChunkElement(chkmem->firsteager); 1335 1336 /* allocate a new chunk */ 1337 if( !createChunk(chkmem, memsize) ) 1338 return NULL; 1339 } 1340 1341 /* now the lazy freelist should contain an element */ 1342 assert(chkmem->lazyfree != NULL); 1343 assert(chkmem->lazyfreesize > 0); 1344 1345 ptr = chkmem->lazyfree; 1346 chkmem->lazyfree = ptr->next; 1347 chkmem->lazyfreesize--; 1348 1349 checkChkmem(chkmem); 1350 1351 return (void*) ptr; 1352 } 1353 1354 /** sorts the lazy free list of the chunk block into the eager free lists of the chunks, and removes completely 1355 * unused chunks 1356 */ 1357 static 1358 void garbagecollectChkmem( 1359 BMS_CHKMEM* chkmem, /**< chunk block */ 1360 long long* memsize /**< pointer to total size of allocated memory (or NULL) */ 1361 ) 1362 { 1363 CHUNK* chunk; 1364 CHUNK* nexteager; 1365 FREELIST* lazyfree; 1366 1367 assert(chkmem != NULL); 1368 1369 debugMessage("garbage collection for chunk block %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize); 1370 1371 /* check, if the chunk block is completely unused */ 1372 if( chkmem->lazyfreesize + chkmem->eagerfreesize == chkmem->storesize ) 1373 { 1374 clearChkmem(chkmem, memsize); 1375 return; 1376 } 1377 1378 #ifndef NDEBUG 1379 chkmem->ngarbagecalls++; 1380 #endif 1381 1382 /* put the lazy free elements into the eager free lists */ 1383 while( chkmem->lazyfree != NULL ) 1384 { 1385 /* unlink first element from the lazy free list */ 1386 lazyfree = chkmem->lazyfree; 1387 chkmem->lazyfree = chkmem->lazyfree->next; 1388 chkmem->lazyfreesize--; 1389 1390 /* identify the chunk of the element */ 1391 chunk = findChunk(chkmem, (void*)lazyfree); 1392 #ifndef NDEBUG 1393 if( chunk == NULL ) 1394 { 1395 errorMessage("chunk for lazy free chunk %p not found in chunk block %p\n", (void*)lazyfree, (void*)chkmem); 1396 } 1397 #endif 1398 assert(chunk != NULL); 1399 1400 /* add the element to the chunk's eager free list */ 1401 freeChunkElement(chunk, (void*)lazyfree); 1402 assert(chunk->eagerfreesize > 0); 1403 } 1404 assert(chkmem->lazyfreesize == 0); 1405 1406 /* delete completely unused chunks, but keep at least one */ 1407 chunk = chkmem->firsteager; 1408 while( chunk != NULL && chkmem->nchunks > 1 ) 1409 { 1410 nexteager = chunk->nexteager; 1411 if( chunk->eagerfreesize == chunk->storesize ) 1412 { 1413 #ifndef NDEBUG 1414 chkmem->ngarbagefrees++; 1415 #endif 1416 freeChunk(&chunk, memsize); 1417 } 1418 chunk = nexteager; 1419 } 1420 1421 checkChkmem(chkmem); 1422 } 1423 1424 /** frees a memory element and returns it to the lazy freelist of the chunk block */ /*lint -e715*/ 1425 static 1426 void freeChkmemElement( 1427 BMS_CHKMEM* chkmem, /**< chunk block */ 1428 void* ptr, /**< memory element */ 1429 long long* memsize, /**< pointer to total size of allocated memory (or NULL) */ 1430 const char* filename, /**< source file of the function call */ 1431 int line /**< line number in source file of the function call */ 1432 ) 1433 { /*lint --e{715}*/ 1434 assert(chkmem != NULL); 1435 assert(ptr != NULL); 1436 1437 #if ( defined(CHECKMEM) || defined(CHECKCHKFREE) ) 1438 /* check, if ptr belongs to the chunk block */ 1439 if( !isPtrInChkmem(chkmem, ptr) ) 1440 { 1441 printErrorHeader(filename, line); 1442 printError("Pointer %p does not belong to chunk block %p (size: %d).\n", ptr, chkmem, chkmem->elemsize); 1443 } 1444 #endif 1445 1446 /* put ptr in lazy free list */ 1447 ((FREELIST*)ptr)->next = chkmem->lazyfree; 1448 chkmem->lazyfree = (FREELIST*)ptr; 1449 chkmem->lazyfreesize++; 1450 1451 /* check if we want to apply garbage collection */ 1452 if( chkmem->garbagefactor >= 0 && chkmem->nchunks > 0 && chkmem->lazyfreesize >= GARBAGE_SIZE 1453 && chkmem->lazyfreesize + chkmem->eagerfreesize 1454 > chkmem->garbagefactor * (double)(chkmem->storesize) / (double)(chkmem->nchunks) ) 1455 { 1456 garbagecollectChkmem(chkmem, memsize); 1457 } 1458 1459 checkChkmem(chkmem); 1460 } 1461 1462 /** creates a new chunk block data structure */ 1463 BMS_CHKMEM* BMScreateChunkMemory_call( 1464 size_t size, /**< element size of the chunk block */ 1465 int initchunksize, /**< number of elements in the first chunk of the chunk block */ 1466 int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize 1467 * elements are free (-1: disable garbage collection) */ 1468 const char* filename, /**< source file of the function call */ 1469 int line /**< line number in source file of the function call */ 1470 ) 1471 { 1472 BMS_CHKMEM* chkmem; 1473 1474 alignSize(&size); 1475 chkmem = createChkmem((int) size, initchunksize, garbagefactor, NULL); 1476 if( chkmem == NULL ) 1477 { 1478 printErrorHeader(filename, line); 1479 printError("Insufficient memory for chunk block.\n"); 1480 } 1481 debugMessage("created chunk memory %p [elemsize: %d]\n", (void*)chkmem, (int)size); 1482 1483 return chkmem; 1484 } 1485 1486 /** clears a chunk block data structure */ 1487 void BMSclearChunkMemory_call( 1488 BMS_CHKMEM* chkmem, /**< chunk block */ 1489 const char* filename, /**< source file of the function call */ 1490 int line /**< line number in source file of the function call */ 1491 ) 1492 { 1493 debugMessage("clearing chunk memory %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize); 1494 1495 if( chkmem != NULL ) 1496 clearChkmem(chkmem, NULL); 1497 else 1498 { 1499 printErrorHeader(filename, line); 1500 printError("Tried to clear null chunk block.\n"); 1501 } 1502 } 1503 1504 /** destroys and frees a chunk block data structure */ 1505 void BMSdestroyChunkMemory_call( 1506 BMS_CHKMEM** chkmem, /**< pointer to chunk block */ 1507 const char* filename, /**< source file of the function call */ 1508 int line /**< line number in source file of the function call */ 1509 ) 1510 { 1511 assert(chkmem != NULL); 1512 1513 debugMessage("destroying chunk memory %p [elemsize: %d]\n", (void*)*chkmem, (*chkmem)->elemsize); 1514 1515 if( *chkmem != NULL ) 1516 destroyChkmem(chkmem, NULL); 1517 else 1518 { 1519 printErrorHeader(filename, line); 1520 printError("Tried to destroy null chunk block.\n"); 1521 } 1522 } 1523 1524 /** allocates a memory element of the given chunk block */ 1525 void* BMSallocChunkMemory_call( 1526 BMS_CHKMEM* chkmem, /**< chunk block */ 1527 size_t size, /**< size of memory element to allocate (only needed for sanity check) */ 1528 const char* filename, /**< source file of the function call */ 1529 int line /**< line number in source file of the function call */ 1530 ) 1531 { 1532 void* ptr; 1533 1534 assert(chkmem != NULL); 1535 assert((int)size == chkmem->elemsize); 1536 1537 /* get memory inside the chunk block */ 1538 ptr = allocChkmemElement(chkmem, NULL); 1539 if( ptr == NULL ) 1540 { 1541 printErrorHeader(filename, line); 1542 printError("Insufficient memory for new chunk.\n"); 1543 } 1544 debugMessage("alloced %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, (void*)ptr, filename, line); 1545 1546 checkChkmem(chkmem); 1547 1548 return ptr; 1549 } 1550 1551 /** duplicates a given memory element by allocating a new element of the same chunk block and copying the data */ 1552 void* BMSduplicateChunkMemory_call( 1553 BMS_CHKMEM* chkmem, /**< chunk block */ 1554 const void* source, /**< source memory element */ 1555 size_t size, /**< size of memory element to allocate (only needed for sanity check) */ 1556 const char* filename, /**< source file of the function call */ 1557 int line /**< line number in source file of the function call */ 1558 ) 1559 { 1560 void* ptr; 1561 1562 assert(chkmem != NULL); 1563 assert(source != NULL); 1564 assert((int)size == chkmem->elemsize); 1565 1566 ptr = BMSallocChunkMemory_call(chkmem, size, filename, line); 1567 if( ptr != NULL ) 1568 BMScopyMemorySize(ptr, source, chkmem->elemsize); 1569 1570 return ptr; 1571 } 1572 1573 /** frees a memory element of the given chunk block and sets pointer to NULL */ 1574 void BMSfreeChunkMemory_call( 1575 BMS_CHKMEM* chkmem, /**< chunk block */ 1576 void** ptr, /**< pointer to pointer to memory element to free */ 1577 size_t size, /**< size of memory element to allocate (only needed for sanity check) */ 1578 const char* filename, /**< source file of the function call */ 1579 int line /**< line number in source file of the function call */ 1580 ) 1581 { 1582 assert(chkmem != NULL); 1583 assert((int)size == chkmem->elemsize); 1584 assert( ptr != NULL ); 1585 1586 if ( *ptr != NULL ) 1587 { 1588 debugMessage("free %8d bytes in %p [%s:%d]\n", chkmem->elemsize, *ptr, filename, line); 1589 1590 /* free memory in chunk block */ 1591 freeChkmemElement(chkmem, *ptr, NULL, filename, line); 1592 checkChkmem(chkmem); 1593 *ptr = NULL; 1594 } 1595 else 1596 { 1597 printErrorHeader(filename, line); 1598 printError("Tried to free null chunk pointer.\n"); 1599 } 1600 } 1601 1602 /** frees a memory element of the given chunk block if pointer is not NULL and sets pointer to NULL */ 1603 void BMSfreeChunkMemoryNull_call( 1604 BMS_CHKMEM* chkmem, /**< chunk block */ 1605 void** ptr, /**< pointer to pointer to memory element to free */ 1606 size_t size, /**< size of memory element to allocate (only needed for sanity check) */ 1607 const char* filename, /**< source file of the function call */ 1608 int line /**< line number in source file of the function call */ 1609 ) 1610 { 1611 assert(chkmem != NULL); 1612 assert((int)size == chkmem->elemsize); 1613 assert( ptr != NULL ); 1614 1615 if ( *ptr != NULL ) 1616 { 1617 debugMessage("free %8d bytes in %p [%s:%d]\n", chkmem->elemsize, *ptr, filename, line); 1618 1619 /* free memory in chunk block */ 1620 freeChkmemElement(chkmem, *ptr, NULL, filename, line); 1621 checkChkmem(chkmem); 1622 *ptr = NULL; 1623 } 1624 } 1625 1626 /** calls garbage collection of chunk block and frees chunks without allocated memory elements */ 1627 void BMSgarbagecollectChunkMemory_call( 1628 BMS_CHKMEM* chkmem /**< chunk block */ 1629 ) 1630 { 1631 debugMessage("garbage collection on chunk memory %p [elemsize: %d]\n", (void*)chkmem, chkmem->elemsize); 1632 1633 garbagecollectChkmem(chkmem, NULL); 1634 } 1635 1636 /** returns the number of allocated bytes in the chunk block */ 1637 long long BMSgetChunkMemoryUsed_call( 1638 const BMS_CHKMEM* chkmem /**< chunk block */ 1639 ) 1640 { 1641 assert(chkmem != NULL); 1642 1643 return ((long long)(chkmem->elemsize) * (long long)(chkmem->storesize)); 1644 } 1645 1646 1647 1648 1649 /*********************************************************** 1650 * Block Memory Management 1651 * 1652 * Efficient memory management for objects of varying sizes 1653 ***********************************************************/ 1654 1655 /* for a definition of the struct, see above */ 1656 1657 1658 /* 1659 * debugging methods 1660 */ 1661 1662 #ifdef CHECKMEM 1663 static 1664 void checkBlkmem( 1665 const BMS_BLKMEM* blkmem /**< block memory */ 1666 ) 1667 { 1668 const BMS_CHKMEM* chkmem; 1669 long long tmpmemalloc = 0LL; 1670 long long tmpmemused = 0LL; 1671 int i; 1672 1673 assert(blkmem != NULL); 1674 assert(blkmem->chkmemhash != NULL); 1675 1676 for( i = 0; i < CHKHASH_SIZE; ++i ) 1677 { 1678 chkmem = blkmem->chkmemhash[i]; 1679 while( chkmem != NULL ) 1680 { 1681 checkChkmem(chkmem); 1682 tmpmemalloc += ((chkmem->elemsize * chkmem->storesize) + chkmem->nchunks * sizeof(CHUNK) + sizeof(BMS_CHKMEM)); 1683 tmpmemused += (chkmem->elemsize * (chkmem->storesize - chkmem->eagerfreesize - chkmem->lazyfreesize)); 1684 chkmem = chkmem->nextchkmem; 1685 } 1686 } 1687 assert(tmpmemalloc == blkmem->memallocated); 1688 assert(tmpmemused == blkmem->memused); 1689 } 1690 #else 1691 #define checkBlkmem(blkmem) /**/ 1692 #endif 1693 1694 1695 /** finds the chunk block, to whick the given pointer belongs to 1696 * 1697 * This could be done by selecting the chunk block of the corresponding element size, but in a case of an 1698 * error (free gives an incorrect element size), we want to identify and output the correct element size. 1699 */ 1700 static 1701 BMS_CHKMEM* findChkmem( 1702 const BMS_BLKMEM* blkmem, /**< block memory */ 1703 const void* ptr /**< memory element to search */ 1704 ) 1705 { 1706 BMS_CHKMEM* chkmem; 1707 int i; 1708 1709 assert(blkmem != NULL); 1710 1711 chkmem = NULL; 1712 for( i = 0; chkmem == NULL && i < CHKHASH_SIZE; ++i ) 1713 { 1714 chkmem = blkmem->chkmemhash[i]; 1715 while( chkmem != NULL && !isPtrInChkmem(chkmem, ptr) ) 1716 chkmem = chkmem->nextchkmem; 1717 } 1718 1719 return chkmem; 1720 } 1721 1722 /** calculates hash number of memory size */ 1723 static 1724 int getHashNumber( 1725 int size /**< element size */ 1726 ) 1727 { 1728 assert(size >= 0); 1729 assert(BMSisAligned((size_t)size)); /*lint !e571*/ 1730 1731 return (int) (((uint32_t)size * UINT32_C(0x9e3779b9))>>(32-CHKHASH_POWER)); 1732 } 1733 1734 /** creates a block memory allocation data structure */ 1735 BMS_BLKMEM* BMScreateBlockMemory_call( 1736 int initchunksize, /**< number of elements in the first chunk of each chunk block */ 1737 int garbagefactor, /**< garbage collector is called, if at least garbagefactor * avg. chunksize 1738 * elements are free (-1: disable garbage collection) */ 1739 const char* filename, /**< source file of the function call */ 1740 int line /**< line number in source file of the function call */ 1741 ) 1742 { 1743 BMS_BLKMEM* blkmem; 1744 int i; 1745 1746 BMSallocMemory(&blkmem); 1747 if( blkmem != NULL ) 1748 { 1749 for( i = 0; i < CHKHASH_SIZE; ++i ) 1750 blkmem->chkmemhash[i] = NULL; 1751 blkmem->initchunksize = initchunksize; 1752 blkmem->garbagefactor = garbagefactor; 1753 blkmem->memused = 0; 1754 blkmem->memallocated = 0; 1755 blkmem->maxmemused = 0; 1756 blkmem->maxmemunused = 0; 1757 blkmem->maxmemallocated = 0; 1758 } 1759 else 1760 { 1761 printErrorHeader(filename, line); 1762 printError("Insufficient memory for block memory header.\n"); 1763 } 1764 1765 return blkmem; 1766 } 1767 1768 /** frees all chunk blocks in the block memory */ 1769 void BMSclearBlockMemory_call( 1770 BMS_BLKMEM* blkmem, /**< block memory */ 1771 const char* filename, /**< source file of the function call */ 1772 int line /**< line number in source file of the function call */ 1773 ) 1774 { 1775 BMS_CHKMEM* chkmem; 1776 BMS_CHKMEM* nextchkmem; 1777 int i; 1778 1779 if( blkmem != NULL ) 1780 { 1781 for( i = 0; i < CHKHASH_SIZE; ++i ) 1782 { 1783 chkmem = blkmem->chkmemhash[i]; 1784 while( chkmem != NULL ) 1785 { 1786 nextchkmem = chkmem->nextchkmem; 1787 destroyChkmem(&chkmem, &blkmem->memallocated); 1788 chkmem = nextchkmem; 1789 } 1790 blkmem->chkmemhash[i] = NULL; 1791 } 1792 blkmem->memused = 0; 1793 assert(blkmem->memallocated == 0); 1794 } 1795 else 1796 { 1797 printErrorHeader(filename, line); 1798 printError("Tried to clear null block memory.\n"); 1799 } 1800 } 1801 1802 /** clears and deletes block memory */ 1803 void BMSdestroyBlockMemory_call( 1804 BMS_BLKMEM** blkmem, /**< pointer to block memory */ 1805 const char* filename, /**< source file of the function call */ 1806 int line /**< line number in source file of the function call */ 1807 ) 1808 { 1809 assert(blkmem != NULL); 1810 1811 if( *blkmem != NULL ) 1812 { 1813 BMSclearBlockMemory_call(*blkmem, filename, line); 1814 BMSfreeMemory(blkmem); 1815 assert(*blkmem == NULL); 1816 } 1817 else 1818 { 1819 printErrorHeader(filename, line); 1820 printError("Tried to destroy null block memory.\n"); 1821 } 1822 } 1823 1824 /** work for allocating memory in the block memory pool */ 1825 INLINE static 1826 void* BMSallocBlockMemory_work( 1827 BMS_BLKMEM* blkmem, /**< block memory */ 1828 size_t size, /**< size of memory element to allocate */ 1829 const char* filename, /**< source file of the function call */ 1830 int line /**< line number in source file of the function call */ 1831 ) 1832 { 1833 BMS_CHKMEM** chkmemptr; 1834 int hashnumber; 1835 void* ptr; 1836 1837 assert( blkmem != NULL ); 1838 1839 /* calculate hash number of given size */ 1840 alignSize(&size); 1841 hashnumber = getHashNumber((int)size); 1842 1843 /* find correspoding chunk block */ 1844 chkmemptr = &(blkmem->chkmemhash[hashnumber]); 1845 while( *chkmemptr != NULL && (*chkmemptr)->elemsize != (int)size ) 1846 chkmemptr = &((*chkmemptr)->nextchkmem); 1847 1848 /* create new chunk block if necessary */ 1849 if( *chkmemptr == NULL ) 1850 { 1851 *chkmemptr = createChkmem((int)size, blkmem->initchunksize, blkmem->garbagefactor, &blkmem->memallocated); 1852 if( *chkmemptr == NULL ) 1853 { 1854 printErrorHeader(filename, line); 1855 printError("Insufficient memory for chunk block.\n"); 1856 return NULL; 1857 } 1858 #ifndef NDEBUG 1859 BMSduplicateMemoryArray(&(*chkmemptr)->filename, filename, strlen(filename) + 1); 1860 (*chkmemptr)->line = line; 1861 #endif 1862 } 1863 1864 /* get memory inside the chunk block */ 1865 ptr = allocChkmemElement(*chkmemptr, &blkmem->memallocated); 1866 1867 if( ptr == NULL ) 1868 { 1869 printErrorHeader(filename, line); 1870 printError("Insufficient memory for new chunk.\n"); 1871 } 1872 debugMessage("alloced %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, ptr, filename, line); 1873 1874 /* add the used memory */ 1875 blkmem->memused += (long long) size; 1876 blkmem->maxmemused = MAX(blkmem->maxmemused, blkmem->memused); 1877 blkmem->maxmemunused = MAX(blkmem->maxmemunused, blkmem->memallocated - blkmem->memused); 1878 blkmem->maxmemallocated = MAX(blkmem->maxmemallocated, blkmem->memallocated); 1879 1880 assert(blkmem->memused >= 0); 1881 assert(blkmem->memallocated >= 0); 1882 1883 checkBlkmem(blkmem); 1884 1885 return ptr; 1886 } 1887 1888 /** allocates memory in the block memory pool */ 1889 void* BMSallocBlockMemory_call( 1890 BMS_BLKMEM* blkmem, /**< block memory */ 1891 size_t size, /**< size of memory element to allocate */ 1892 const char* filename, /**< source file of the function call */ 1893 int line /**< line number in source file of the function call */ 1894 ) 1895 { 1896 #ifndef NDEBUG 1897 if ( size > MAXMEMSIZE ) 1898 { 1899 printErrorHeader(filename, line); 1900 printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE); 1901 return NULL; 1902 } 1903 #endif 1904 1905 return BMSallocBlockMemory_work(blkmem, size, filename, line); 1906 } 1907 1908 /** allocates memory in the block memory pool and clears it */ 1909 void* BMSallocClearBlockMemory_call( 1910 BMS_BLKMEM* blkmem, /**< block memory */ 1911 size_t size, /**< size of memory element to allocate */ 1912 const char* filename, /**< source file of the function call */ 1913 int line /**< line number in source file of the function call */ 1914 ) 1915 { 1916 void* ptr; 1917 1918 ptr = BMSallocBlockMemory_call(blkmem, size, filename, line); 1919 if( ptr != NULL ) 1920 BMSclearMemorySize(ptr, size); 1921 1922 return ptr; 1923 } 1924 1925 /** allocates array in the block memory pool */ 1926 void* BMSallocBlockMemoryArray_call( 1927 BMS_BLKMEM* blkmem, /**< block memory */ 1928 size_t num, /**< size of array to be allocated */ 1929 size_t typesize, /**< size of each component */ 1930 const char* filename, /**< source file of the function call */ 1931 int line /**< line number in source file of the function call */ 1932 ) 1933 { 1934 #ifndef NDEBUG 1935 if ( num > (MAXMEMSIZE / typesize) ) 1936 { 1937 printErrorHeader(filename, line); 1938 printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE); 1939 return NULL; 1940 } 1941 #endif 1942 1943 return BMSallocBlockMemory_work(blkmem, num * typesize, filename, line); 1944 } 1945 1946 /** allocates array in the block memory pool and clears it */ 1947 void* BMSallocClearBlockMemoryArray_call( 1948 BMS_BLKMEM* blkmem, /**< block memory */ 1949 size_t num, /**< size of array to be allocated */ 1950 size_t typesize, /**< size of each component */ 1951 const char* filename, /**< source file of the function call */ 1952 int line /**< line number in source file of the function call */ 1953 ) 1954 { 1955 void* ptr; 1956 1957 ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line); 1958 if ( ptr != NULL ) 1959 BMSclearMemorySize(ptr, num * typesize); 1960 1961 return ptr; 1962 } 1963 1964 /** resizes memory element in the block memory pool and copies the data */ 1965 void* BMSreallocBlockMemory_call( 1966 BMS_BLKMEM* blkmem, /**< block memory */ 1967 void* ptr, /**< memory element to reallocated */ 1968 size_t oldsize, /**< old size of memory element */ 1969 size_t newsize, /**< new size of memory element */ 1970 const char* filename, /**< source file of the function call */ 1971 int line /**< line number in source file of the function call */ 1972 ) 1973 { 1974 void* newptr; 1975 1976 if( ptr == NULL ) 1977 { 1978 assert(oldsize == 0); 1979 return BMSallocBlockMemory_call(blkmem, newsize, filename, line); 1980 } 1981 1982 #ifndef NDEBUG 1983 if ( newsize > MAXMEMSIZE ) 1984 { 1985 printErrorHeader(filename, line); 1986 printError("Tried to allocate block of size exceeding %lu.\n", MAXMEMSIZE); 1987 return NULL; 1988 } 1989 #endif 1990 1991 alignSize(&oldsize); 1992 alignSize(&newsize); 1993 if( oldsize == newsize ) 1994 return ptr; 1995 1996 newptr = BMSallocBlockMemory_call(blkmem, newsize, filename, line); 1997 if( newptr != NULL ) 1998 BMScopyMemorySize(newptr, ptr, MIN(oldsize, newsize)); 1999 BMSfreeBlockMemory_call(blkmem, &ptr, oldsize, filename, line); 2000 2001 return newptr; 2002 } 2003 2004 /** resizes array in the block memory pool and copies the data */ 2005 void* BMSreallocBlockMemoryArray_call( 2006 BMS_BLKMEM* blkmem, /**< block memory */ 2007 void* ptr, /**< memory element to reallocated */ 2008 size_t oldnum, /**< old size of array */ 2009 size_t newnum, /**< new size of array */ 2010 size_t typesize, /**< size of each component */ 2011 const char* filename, /**< source file of the function call */ 2012 int line /**< line number in source file of the function call */ 2013 ) 2014 { 2015 void* newptr; 2016 2017 if( ptr == NULL ) 2018 { 2019 assert(oldnum == 0); 2020 return BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line); 2021 } 2022 2023 #ifndef NDEBUG 2024 if ( newnum > (MAXMEMSIZE / typesize) ) 2025 { 2026 printErrorHeader(filename, line); 2027 printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE); 2028 return NULL; 2029 } 2030 #endif 2031 2032 if ( oldnum == newnum ) 2033 return ptr; 2034 2035 newptr = BMSallocBlockMemoryArray_call(blkmem, newnum, typesize, filename, line); 2036 if ( newptr != NULL ) 2037 BMScopyMemorySize(newptr, ptr, MIN(oldnum, newnum) * typesize); 2038 BMSfreeBlockMemory_call(blkmem, &ptr, oldnum * typesize, filename, line); 2039 2040 return newptr; 2041 } 2042 2043 /** duplicates memory element in the block memory pool and copies the data */ 2044 void* BMSduplicateBlockMemory_call( 2045 BMS_BLKMEM* blkmem, /**< block memory */ 2046 const void* source, /**< memory element to duplicate */ 2047 size_t size, /**< size of memory elements */ 2048 const char* filename, /**< source file of the function call */ 2049 int line /**< line number in source file of the function call */ 2050 ) 2051 { 2052 void* ptr; 2053 2054 assert(source != NULL); 2055 2056 ptr = BMSallocBlockMemory_call(blkmem, size, filename, line); 2057 if( ptr != NULL ) 2058 BMScopyMemorySize(ptr, source, size); 2059 2060 return ptr; 2061 } 2062 2063 /** duplicates array in the block memory pool and copies the data */ 2064 void* BMSduplicateBlockMemoryArray_call( 2065 BMS_BLKMEM* blkmem, /**< block memory */ 2066 const void* source, /**< memory element to duplicate */ 2067 size_t num, /**< size of array to be duplicated */ 2068 size_t typesize, /**< size of each component */ 2069 const char* filename, /**< source file of the function call */ 2070 int line /**< line number in source file of the function call */ 2071 ) 2072 { 2073 void* ptr; 2074 2075 assert(source != NULL); 2076 2077 ptr = BMSallocBlockMemoryArray_call(blkmem, num, typesize, filename, line); 2078 if( ptr != NULL ) 2079 BMScopyMemorySize(ptr, source, num * typesize); 2080 2081 return ptr; 2082 } 2083 2084 /** common work for freeing block memory */ 2085 INLINE static 2086 void BMSfreeBlockMemory_work( 2087 BMS_BLKMEM* blkmem, /**< block memory */ 2088 void** ptr, /**< pointer to pointer to memory element to free */ 2089 size_t size, /**< size of memory element */ 2090 const char* filename, /**< source file of the function call */ 2091 int line /**< line number in source file of the function call */ 2092 ) 2093 { 2094 BMS_CHKMEM* chkmem; 2095 int hashnumber; 2096 2097 assert(ptr != NULL); 2098 assert(*ptr != NULL); 2099 2100 /* calculate hash number of given size */ 2101 alignSize(&size); 2102 hashnumber = getHashNumber((int)size); 2103 2104 debugMessage("free %8llu bytes in %p [%s:%d]\n", (unsigned long long)size, *ptr, filename, line); 2105 2106 /* find correspoding chunk block */ 2107 assert( blkmem->chkmemhash != NULL ); 2108 chkmem = blkmem->chkmemhash[hashnumber]; 2109 while( chkmem != NULL && chkmem->elemsize != (int)size ) 2110 chkmem = chkmem->nextchkmem; 2111 if( chkmem == NULL ) 2112 { 2113 printErrorHeader(filename, line); 2114 printError("Tried to free pointer <%p> in block memory <%p> of unknown size %llu.\n", *ptr, (void*)blkmem, (unsigned long long)size); 2115 return; 2116 } 2117 assert(chkmem->elemsize == (int)size); 2118 2119 /* free memory in chunk block */ 2120 freeChkmemElement(chkmem, *ptr, &blkmem->memallocated, filename, line); 2121 blkmem->memused -= (long long) size; 2122 2123 blkmem->maxmemunused = MAX(blkmem->maxmemunused, blkmem->memallocated - blkmem->memused); 2124 2125 assert(blkmem->memused >= 0); 2126 assert(blkmem->memallocated >= 0); 2127 2128 checkBlkmem(blkmem); 2129 2130 *ptr = NULL; 2131 } 2132 2133 /** frees memory element in the block memory pool and sets pointer to NULL */ 2134 void BMSfreeBlockMemory_call( 2135 BMS_BLKMEM* blkmem, /**< block memory */ 2136 void** ptr, /**< pointer to pointer to memory element to free */ 2137 size_t size, /**< size of memory element */ 2138 const char* filename, /**< source file of the function call */ 2139 int line /**< line number in source file of the function call */ 2140 ) 2141 { 2142 assert( blkmem != NULL ); 2143 assert( ptr != NULL ); 2144 2145 if( *ptr != NULL ) 2146 BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line); 2147 else if( size != 0 ) 2148 { 2149 printErrorHeader(filename, line); 2150 printError("Tried to free null block pointer.\n"); 2151 } 2152 checkBlkmem(blkmem); 2153 } 2154 2155 /** frees memory element in the block memory pool if pointer is not NULL and sets pointer to NULL */ 2156 void BMSfreeBlockMemoryNull_call( 2157 BMS_BLKMEM* blkmem, /**< block memory */ 2158 void** ptr, /**< pointer to pointer to memory element to free */ 2159 size_t size, /**< size of memory element */ 2160 const char* filename, /**< source file of the function call */ 2161 int line /**< line number in source file of the function call */ 2162 ) 2163 { 2164 assert( blkmem != NULL ); 2165 assert( ptr != NULL ); 2166 2167 if( *ptr != NULL ) 2168 { 2169 BMSfreeBlockMemory_work(blkmem, ptr, size, filename, line); 2170 } 2171 checkBlkmem(blkmem); 2172 } 2173 2174 /** calls garbage collection of block memory, frees chunks without allocated memory elements, and frees 2175 * chunk blocks without any chunks 2176 */ 2177 void BMSgarbagecollectBlockMemory_call( 2178 BMS_BLKMEM* blkmem /**< block memory */ 2179 ) 2180 { 2181 int i; 2182 2183 assert(blkmem != NULL); 2184 2185 for( i = 0; i < CHKHASH_SIZE; ++i ) 2186 { 2187 BMS_CHKMEM** chkmemptr; 2188 2189 chkmemptr = &blkmem->chkmemhash[i]; 2190 while( *chkmemptr != NULL ) 2191 { 2192 garbagecollectChkmem(*chkmemptr, &blkmem->memallocated); 2193 checkBlkmem(blkmem); 2194 if( (*chkmemptr)->nchunks == 0 ) 2195 { 2196 BMS_CHKMEM* nextchkmem; 2197 2198 assert((*chkmemptr)->lazyfreesize == 0); 2199 nextchkmem = (*chkmemptr)->nextchkmem; 2200 destroyChkmem(chkmemptr, &blkmem->memallocated); 2201 *chkmemptr = nextchkmem; 2202 checkBlkmem(blkmem); 2203 } 2204 else 2205 chkmemptr = &(*chkmemptr)->nextchkmem; 2206 } 2207 } 2208 } 2209 2210 /** returns the number of allocated bytes in the block memory */ 2211 long long BMSgetBlockMemoryAllocated_call( 2212 const BMS_BLKMEM* blkmem /**< block memory */ 2213 ) 2214 { 2215 assert( blkmem != NULL ); 2216 2217 return blkmem->memallocated; 2218 } 2219 2220 /** returns the number of used bytes in the block memory */ 2221 long long BMSgetBlockMemoryUsed_call( 2222 const BMS_BLKMEM* blkmem /**< block memory */ 2223 ) 2224 { 2225 assert( blkmem != NULL ); 2226 2227 return blkmem->memused; 2228 } 2229 2230 /** returns the number of allocated but not used bytes in the block memory */ 2231 long long BMSgetBlockMemoryUnused_call( 2232 const BMS_BLKMEM* blkmem /**< block memory */ 2233 ) 2234 { 2235 assert( blkmem != NULL ); 2236 2237 return blkmem->memallocated - blkmem->memused; 2238 } 2239 2240 /** returns the maximal number of used bytes in the block memory */ 2241 long long BMSgetBlockMemoryUsedMax_call( 2242 const BMS_BLKMEM* blkmem /**< block memory */ 2243 ) 2244 { 2245 assert( blkmem != NULL ); 2246 2247 return blkmem->maxmemused; 2248 } 2249 2250 /** returns the maximal number of allocated but not used bytes in the block memory */ 2251 long long BMSgetBlockMemoryUnusedMax_call( 2252 const BMS_BLKMEM* blkmem /**< block memory */ 2253 ) 2254 { 2255 assert( blkmem != NULL ); 2256 2257 return blkmem->maxmemunused; 2258 } 2259 2260 /** returns the maximal number of allocated bytes in the block memory */ 2261 long long BMSgetBlockMemoryAllocatedMax_call( 2262 const BMS_BLKMEM* blkmem /**< block memory */ 2263 ) 2264 { 2265 assert( blkmem != NULL ); 2266 2267 return blkmem->maxmemallocated; 2268 } 2269 2270 /** returns the size of the given memory element; returns 0, if the element is not member of the block memory */ 2271 size_t BMSgetBlockPointerSize_call( 2272 const BMS_BLKMEM* blkmem, /**< block memory */ 2273 const void* ptr /**< memory element */ 2274 ) 2275 { 2276 const BMS_CHKMEM* chkmem; 2277 2278 assert(blkmem != NULL); 2279 2280 if( ptr == NULL ) 2281 return 0; 2282 2283 chkmem = findChkmem(blkmem, ptr); 2284 if( chkmem == NULL ) 2285 return 0; 2286 2287 return (size_t)(chkmem->elemsize); /*lint !e571*/ 2288 } 2289 2290 /** outputs allocation diagnostics of block memory */ 2291 void BMSdisplayBlockMemory_call( 2292 const BMS_BLKMEM* blkmem /**< block memory */ 2293 ) 2294 { 2295 const BMS_CHKMEM* chkmem; 2296 int nblocks = 0; 2297 int nunusedblocks = 0; 2298 int totalnchunks = 0; 2299 int totalneagerchunks = 0; 2300 int totalnelems = 0; 2301 int totalneagerelems = 0; 2302 int totalnlazyelems = 0; 2303 #ifndef NDEBUG 2304 int totalngarbagecalls = 0; 2305 int totalngarbagefrees = 0; 2306 #endif 2307 long long allocedmem = 0; 2308 long long freemem = 0; 2309 int i; 2310 2311 #ifndef NDEBUG 2312 printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr #GCl #GFr Free MBytes First Allocator\n"); 2313 #else 2314 printInfo(" ElSize #Chunk #Eag #Elems #EagFr #LazFr Free MBytes\n"); 2315 #endif 2316 2317 assert(blkmem != NULL); 2318 2319 for( i = 0; i < CHKHASH_SIZE; ++i ) 2320 { 2321 chkmem = blkmem->chkmemhash[i]; 2322 while( chkmem != NULL ) 2323 { 2324 int nchunks = 0; 2325 int nelems = 0; 2326 int neagerchunks = 0; 2327 int neagerelems = 0; 2328 2329 FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk, 2330 { 2331 assert(chunk != NULL); 2332 assert(chunk->elemsize == chkmem->elemsize); 2333 assert(chunk->chkmem == chkmem); 2334 nchunks++; 2335 nelems += chunk->storesize; 2336 if( chunk->eagerfree != NULL ) 2337 { 2338 neagerchunks++; 2339 neagerelems += chunk->eagerfreesize; 2340 } 2341 }) 2342 2343 assert(nchunks == chkmem->nchunks); 2344 assert(nelems == chkmem->storesize); 2345 assert(neagerelems == chkmem->eagerfreesize); 2346 2347 if( nelems > 0 ) 2348 { 2349 nblocks++; 2350 allocedmem += (long long)chkmem->elemsize * (long long)nelems; 2351 freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize); 2352 2353 #ifndef NDEBUG 2354 printInfo("%7d %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f %s:%d\n", 2355 chkmem->elemsize, nchunks, neagerchunks, nelems, 2356 neagerelems, chkmem->lazyfreesize, chkmem->ngarbagecalls, chkmem->ngarbagefrees, 2357 100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems), 2358 (double)chkmem->elemsize * nelems / (1024.0*1024.0), 2359 chkmem->filename, chkmem->line); 2360 #else 2361 printInfo("%7d %6d %4d %7d %7d %7d %5.1f%% %6.1f\n", 2362 chkmem->elemsize, nchunks, neagerchunks, nelems, 2363 neagerelems, chkmem->lazyfreesize, 2364 100.0 * (double) (neagerelems + chkmem->lazyfreesize) / (double) (nelems), 2365 (double)chkmem->elemsize * nelems / (1024.0*1024.0)); 2366 #endif 2367 } 2368 else 2369 { 2370 #ifndef NDEBUG 2371 printInfo("%7d <unused> %5d %4d %s:%d\n", 2372 chkmem->elemsize, chkmem->ngarbagecalls, chkmem->ngarbagefrees, 2373 chkmem->filename, chkmem->line); 2374 #else 2375 printInfo("%7d <unused>\n", chkmem->elemsize); 2376 #endif 2377 nunusedblocks++; 2378 } 2379 totalnchunks += nchunks; 2380 totalneagerchunks += neagerchunks; 2381 totalnelems += nelems; 2382 totalneagerelems += neagerelems; 2383 totalnlazyelems += chkmem->lazyfreesize; 2384 #ifndef NDEBUG 2385 totalngarbagecalls += chkmem->ngarbagecalls; 2386 totalngarbagefrees += chkmem->ngarbagefrees; 2387 #endif 2388 chkmem = chkmem->nextchkmem; 2389 } 2390 } 2391 #ifndef NDEBUG 2392 printInfo(" Total %6d %4d %7d %7d %7d %5d %4d %5.1f%% %6.1f\n", 2393 totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems, 2394 totalngarbagecalls, totalngarbagefrees, 2395 totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0, 2396 (double)allocedmem/(1024.0*1024.0)); 2397 #else 2398 printInfo(" Total %6d %4d %7d %7d %7d %5.1f%% %6.1f\n", 2399 totalnchunks, totalneagerchunks, totalnelems, totalneagerelems, totalnlazyelems, 2400 totalnelems > 0 ? 100.0 * (double) (totalneagerelems + totalnlazyelems) / (double) (totalnelems) : 0.0, 2401 (double)allocedmem/(1024.0*1024.0)); 2402 #endif 2403 printInfo("%d blocks (%d unused), %" LONGINT_FORMAT " bytes allocated, %" LONGINT_FORMAT " bytes free", 2404 nblocks + nunusedblocks, nunusedblocks, allocedmem, freemem); 2405 if( allocedmem > 0 ) 2406 printInfo(" (%.1f%%)", 100.0 * (double) freemem / (double) allocedmem); 2407 printInfo("\n\n"); 2408 2409 printInfo("Memory Peaks: Used Lazy Total\n"); 2410 printInfo(" %6.1f %6.1f %6.1f MBytes\n", (double)blkmem->maxmemused / (1024.0 * 1024.0), 2411 (double)blkmem->maxmemunused / (1024.0 * 1024.0), (double)blkmem->maxmemallocated / (1024.0 * 1024.0)); 2412 } 2413 2414 /** outputs error messages, if there are allocated elements in the block memory and returns number of unfreed bytes */ 2415 long long BMScheckEmptyBlockMemory_call( 2416 const BMS_BLKMEM* blkmem /**< block memory */ 2417 ) 2418 { 2419 const BMS_CHKMEM* chkmem; 2420 long long allocedmem = 0; 2421 long long freemem = 0; 2422 int i; 2423 2424 assert(blkmem != NULL); 2425 2426 for( i = 0; i < CHKHASH_SIZE; ++i ) 2427 { 2428 chkmem = blkmem->chkmemhash[i]; 2429 while( chkmem != NULL ) 2430 { 2431 int nchunks = 0; 2432 int nelems = 0; 2433 int neagerelems = 0; 2434 2435 FOR_EACH_NODE(CHUNK*, chunk, chkmem->rootchunk, 2436 { 2437 assert(chunk != NULL); 2438 assert(chunk->elemsize == chkmem->elemsize); 2439 assert(chunk->chkmem == chkmem); 2440 nchunks++; 2441 nelems += chunk->storesize; 2442 if( chunk->eagerfree != NULL ) 2443 neagerelems += chunk->eagerfreesize; 2444 }) 2445 2446 assert(nchunks == chkmem->nchunks); 2447 SCIP_UNUSED(nchunks); 2448 assert(nelems == chkmem->storesize); 2449 assert(neagerelems == chkmem->eagerfreesize); 2450 2451 if( nelems > 0 ) 2452 { 2453 allocedmem += (long long)chkmem->elemsize * (long long)nelems; 2454 freemem += (long long)chkmem->elemsize * ((long long)neagerelems + (long long)chkmem->lazyfreesize); 2455 2456 if( nelems != neagerelems + chkmem->lazyfreesize ) 2457 { 2458 #ifndef NDEBUG 2459 errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed. First Allocator: %s:%d\n", 2460 (((long long)nelems - (long long)neagerelems) - (long long)chkmem->lazyfreesize) 2461 * (long long)(chkmem->elemsize), 2462 (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize), 2463 chkmem->filename, chkmem->line); 2464 #else 2465 errorMessage("%" LONGINT_FORMAT " bytes (%d elements of size %" LONGINT_FORMAT ") not freed.\n", 2466 ((nelems - neagerelems) - chkmem->lazyfreesize) * (long long)(chkmem->elemsize), 2467 (nelems - neagerelems) - chkmem->lazyfreesize, (long long)(chkmem->elemsize)); 2468 #endif 2469 } 2470 } 2471 chkmem = chkmem->nextchkmem; 2472 } 2473 } 2474 2475 if( allocedmem != freemem ) 2476 { 2477 errorMessage("%" LONGINT_FORMAT " bytes not freed in total.\n", allocedmem - freemem); 2478 } 2479 2480 return allocedmem - freemem; 2481 } 2482 2483 2484 2485 2486 2487 2488 /*********************************************************** 2489 * Buffer Memory Management 2490 * 2491 * Efficient memory management for temporary objects 2492 ***********************************************************/ 2493 2494 /** memory buffer storage for temporary objects */ 2495 struct BMS_BufMem 2496 { 2497 void** data; /**< allocated memory chunks for arbitrary data */ 2498 size_t* size; /**< sizes of buffers in bytes */ 2499 unsigned int* used; /**< 1 iff corresponding buffer is in use */ 2500 size_t totalmem; /**< total memory consumption of buffer */ 2501 unsigned int clean; /**< 1 iff the memory blocks in the buffer should be initialized to zero? */ 2502 size_t ndata; /**< number of memory chunks */ 2503 size_t firstfree; /**< first unused memory chunk */ 2504 double arraygrowfac; /**< memory growing factor for dynamically allocated arrays */ 2505 unsigned int arraygrowinit; /**< initial size of dynamically allocated arrays */ 2506 }; 2507 2508 2509 /** creates memory buffer storage */ 2510 BMS_BUFMEM* BMScreateBufferMemory_call( 2511 double arraygrowfac, /**< memory growing factor for dynamically allocated arrays */ 2512 int arraygrowinit, /**< initial size of dynamically allocated arrays */ 2513 unsigned int clean, /**< should the memory blocks in the buffer be initialized to zero? */ 2514 const char* filename, /**< source file of the function call */ 2515 int line /**< line number in source file of the function call */ 2516 ) 2517 { 2518 BMS_BUFMEM* buffer; 2519 2520 assert( arraygrowinit > 0 ); 2521 assert( arraygrowfac > 0.0 ); 2522 2523 BMSallocMemory(&buffer); 2524 if ( buffer != NULL ) 2525 { 2526 buffer->data = NULL; 2527 buffer->size = NULL; 2528 buffer->used = NULL; 2529 buffer->totalmem = 0UL; 2530 buffer->clean = clean; 2531 buffer->ndata = 0; 2532 buffer->firstfree = 0; 2533 buffer->arraygrowinit = (unsigned) arraygrowinit; 2534 buffer->arraygrowfac = arraygrowfac; 2535 } 2536 else 2537 { 2538 printErrorHeader(filename, line); 2539 printError("Insufficient memory for buffer memory header.\n"); 2540 } 2541 2542 return buffer; 2543 } 2544 2545 /** destroys buffer memory */ 2546 void BMSdestroyBufferMemory_call( 2547 BMS_BUFMEM** buffer, /**< pointer to memory buffer storage */ 2548 const char* filename, /**< source file of the function call */ 2549 int line /**< line number in source file of the function call */ 2550 ) 2551 { 2552 size_t i; 2553 2554 if ( *buffer != NULL ) 2555 { 2556 i = (*buffer)->ndata; 2557 if ( i > 0 ) { 2558 for (--i ; ; i--) 2559 { 2560 assert( ! (*buffer)->used[i] ); 2561 BMSfreeMemoryArrayNull(&(*buffer)->data[i]); 2562 if ( i == 0 ) 2563 break; 2564 } 2565 } 2566 BMSfreeMemoryArrayNull(&(*buffer)->data); 2567 BMSfreeMemoryArrayNull(&(*buffer)->size); 2568 BMSfreeMemoryArrayNull(&(*buffer)->used); 2569 BMSfreeMemory(buffer); 2570 } 2571 else 2572 { 2573 printErrorHeader(filename, line); 2574 printError("Tried to free null buffer memory.\n"); 2575 } 2576 } 2577 2578 /** set arraygrowfac */ 2579 void BMSsetBufferMemoryArraygrowfac( 2580 BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */ 2581 double arraygrowfac /**< memory growing factor for dynamically allocated arrays */ 2582 ) 2583 { 2584 assert( buffer != NULL ); 2585 assert( arraygrowfac > 0.0 ); 2586 2587 buffer->arraygrowfac = arraygrowfac; 2588 } 2589 2590 /** set arraygrowinit */ 2591 void BMSsetBufferMemoryArraygrowinit( 2592 BMS_BUFMEM* buffer, /**< pointer to memory buffer storage */ 2593 int arraygrowinit /**< initial size of dynamically allocated arrays */ 2594 ) 2595 { 2596 assert( buffer != NULL ); 2597 assert( arraygrowinit > 0 ); 2598 2599 buffer->arraygrowinit = (unsigned) arraygrowinit; 2600 } 2601 2602 #ifndef SCIP_NOBUFFERMEM 2603 /** calculate memory size for dynamically allocated arrays 2604 * 2605 * This function is a copy of the function in set.c in order to be able to use memory.? separately. 2606 */ 2607 static 2608 size_t calcMemoryGrowSize( 2609 size_t initsize, /**< initial size of array */ 2610 SCIP_Real growfac, /**< growing factor of array */ 2611 size_t num /**< minimum number of entries to store */ 2612 ) 2613 { 2614 size_t size; 2615 2616 assert( growfac >= 1.0 ); 2617 2618 if ( growfac == 1.0 ) 2619 size = MAX(initsize, num); 2620 else 2621 { 2622 size_t oldsize; 2623 2624 /* calculate the size with this loop, such that the resulting numbers are always the same */ 2625 initsize = MAX(initsize, 4); 2626 size = initsize; 2627 oldsize = size - 1; 2628 2629 /* second condition checks against overflow */ 2630 while ( size < num && size > oldsize ) 2631 { 2632 oldsize = size; 2633 size = (size_t)(growfac * size + initsize); 2634 } 2635 2636 /* if an overflow happened, set the correct value */ 2637 if ( size <= oldsize ) 2638 size = num; 2639 } 2640 2641 assert( size >= initsize ); 2642 assert( size >= num ); 2643 2644 return size; 2645 } 2646 #endif 2647 2648 /** work for allocating the next unused buffer */ 2649 INLINE static 2650 void* BMSallocBufferMemory_work( 2651 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2652 size_t size, /**< minimal required size of the buffer */ 2653 const char* filename, /**< source file of the function call */ 2654 int line /**< line number in source file of the function call */ 2655 ) 2656 { 2657 /* cppcheck-suppress unassignedVariable */ 2658 void* ptr; 2659 #ifndef SCIP_NOBUFFERMEM 2660 size_t bufnum; 2661 #endif 2662 2663 #ifndef SCIP_NOBUFFERMEM 2664 assert( buffer != NULL ); 2665 assert( buffer->firstfree <= buffer->ndata ); 2666 2667 /* allocate a minimum of 1 byte */ 2668 if ( size == 0 ) 2669 size = 1; 2670 2671 /* check, if we need additional buffers */ 2672 if ( buffer->firstfree == buffer->ndata ) 2673 { 2674 size_t newsize; 2675 size_t i; 2676 2677 /* create additional buffers */ 2678 newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, buffer->firstfree + 1); 2679 BMSreallocMemoryArray(&buffer->data, newsize); 2680 if ( buffer->data == NULL ) 2681 { 2682 printErrorHeader(filename, line); 2683 printError("Insufficient memory for reallocating buffer data storage.\n"); 2684 return NULL; 2685 } 2686 BMSreallocMemoryArray(&buffer->size, newsize); 2687 if ( buffer->size == NULL ) 2688 { 2689 printErrorHeader(filename, line); 2690 printError("Insufficient memory for reallocating buffer size storage.\n"); 2691 return NULL; 2692 } 2693 BMSreallocMemoryArray(&buffer->used, newsize); 2694 if ( buffer->used == NULL ) 2695 { 2696 printErrorHeader(filename, line); 2697 printError("Insufficient memory for reallocating buffer used storage.\n"); 2698 return NULL; 2699 } 2700 2701 /* init data */ 2702 for (i = buffer->ndata; i < newsize; ++i) 2703 { 2704 buffer->data[i] = NULL; 2705 buffer->size[i] = 0; 2706 buffer->used[i] = FALSE; 2707 } 2708 buffer->ndata = newsize; 2709 } 2710 assert(buffer->firstfree < buffer->ndata); 2711 2712 /* check, if the current buffer is large enough */ 2713 bufnum = buffer->firstfree; 2714 assert( ! buffer->used[bufnum] ); 2715 if ( buffer->size[bufnum] < size ) 2716 { 2717 size_t newsize; 2718 2719 /* enlarge buffer */ 2720 newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size); 2721 BMSreallocMemorySize(&buffer->data[bufnum], newsize); 2722 2723 /* clear new memory */ 2724 if( buffer->clean ) 2725 { 2726 char* tmpptr = (char*)(buffer->data[bufnum]); 2727 size_t inc = buffer->size[bufnum] / sizeof(*tmpptr); 2728 tmpptr += inc; 2729 2730 BMSclearMemorySize(tmpptr, newsize - buffer->size[bufnum]); 2731 } 2732 assert( newsize > buffer->size[bufnum] ); 2733 buffer->totalmem += newsize - buffer->size[bufnum]; 2734 buffer->size[bufnum] = newsize; 2735 2736 if ( buffer->data[bufnum] == NULL ) 2737 { 2738 printErrorHeader(filename, line); 2739 printError("Insufficient memory for reallocating buffer storage.\n"); 2740 return NULL; 2741 } 2742 } 2743 assert( buffer->size[bufnum] >= size ); 2744 2745 #ifdef CHECKCLEANBUFFER 2746 /* check that the memory is cleared */ 2747 if( buffer->clean ) 2748 { 2749 char* tmpptr = (char*)(buffer->data[bufnum]); 2750 unsigned int inc = buffer->size[bufnum] / sizeof(*tmpptr); 2751 tmpptr += inc; 2752 2753 while( --tmpptr >= (char*)(buffer->data[bufnum]) ) 2754 assert(*tmpptr == '\0'); 2755 } 2756 #endif 2757 2758 ptr = buffer->data[bufnum]; 2759 buffer->used[bufnum] = TRUE; 2760 buffer->firstfree++; 2761 2762 debugMessage("Allocated buffer %llu/%llu at %p of size %llu (required size: %llu) for pointer %p.\n", 2763 (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum], 2764 (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, ptr); 2765 2766 #else 2767 if( buffer->clean ) 2768 { 2769 /* we should allocate at least one byte, otherwise BMSallocMemorySize will fail */ 2770 size = MAX(size,1); 2771 2772 BMSallocClearMemorySize(&ptr, size); 2773 } 2774 else 2775 { 2776 BMSallocMemorySize(&ptr, size); 2777 } 2778 #endif 2779 2780 return ptr; 2781 } 2782 2783 /** allocates the next unused buffer */ 2784 void* BMSallocBufferMemory_call( 2785 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2786 size_t size, /**< minimal required size of the buffer */ 2787 const char* filename, /**< source file of the function call */ 2788 int line /**< line number in source file of the function call */ 2789 ) 2790 { 2791 #ifndef NDEBUG 2792 if ( size > MAXMEMSIZE ) 2793 { 2794 printErrorHeader(filename, line); 2795 printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE); 2796 return NULL; 2797 } 2798 #endif 2799 2800 return BMSallocBufferMemory_work(buffer, size, filename, line); 2801 } 2802 2803 /** allocates the next unused buffer array */ 2804 void* BMSallocBufferMemoryArray_call( 2805 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2806 size_t num, /**< size of array to be allocated */ 2807 size_t typesize, /**< size of components */ 2808 const char* filename, /**< source file of the function call */ 2809 int line /**< line number in source file of the function call */ 2810 ) 2811 { 2812 #ifndef NDEBUG 2813 if ( num > (MAXMEMSIZE / typesize) ) 2814 { 2815 printErrorHeader(filename, line); 2816 printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE); 2817 return NULL; 2818 } 2819 #endif 2820 2821 return BMSallocBufferMemory_work(buffer, num * typesize, filename, line); 2822 } 2823 2824 /** allocates the next unused buffer and clears it */ 2825 void* BMSallocClearBufferMemoryArray_call( 2826 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2827 size_t num, /**< size of array to be allocated */ 2828 size_t typesize, /**< size of components */ 2829 const char* filename, /**< source file of the function call */ 2830 int line /**< line number in source file of the function call */ 2831 ) 2832 { 2833 void* ptr; 2834 2835 ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line); 2836 if ( ptr != NULL ) 2837 BMSclearMemorySize(ptr, num * typesize); 2838 2839 return ptr; 2840 } 2841 2842 /** work for reallocating the buffer to at least the given size */ 2843 INLINE static 2844 void* BMSreallocBufferMemory_work( 2845 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2846 void* ptr, /**< pointer to the allocated memory buffer */ 2847 size_t size, /**< minimal required size of the buffer */ 2848 const char* filename, /**< source file of the function call */ 2849 int line /**< line number in source file of the function call */ 2850 ) 2851 { 2852 void* newptr; 2853 #ifndef SCIP_NOBUFFERMEM 2854 size_t bufnum; 2855 #endif 2856 2857 #ifndef SCIP_NOBUFFERMEM 2858 assert( buffer != NULL ); 2859 assert( buffer->firstfree <= buffer->ndata ); 2860 assert(!buffer->clean); /* reallocating clean buffer elements is not supported */ 2861 2862 /* if the pointer doesn't exist yet, allocate it */ 2863 if ( ptr == NULL ) 2864 return BMSallocBufferMemory_call(buffer, size, filename, line); 2865 2866 assert( buffer->firstfree >= 1 ); 2867 2868 /* Search the pointer in the buffer list: 2869 * Usually, buffers are allocated and freed like a stack, such that the currently used pointer is 2870 * most likely at the end of the buffer list. 2871 */ 2872 bufnum = buffer->firstfree - 1; 2873 while ( bufnum > 0 && buffer->data[bufnum] != ptr ) 2874 --bufnum; 2875 2876 newptr = ptr; 2877 assert( buffer->data[bufnum] == newptr ); 2878 assert( buffer->used[bufnum] ); 2879 assert( buffer->size[bufnum] >= 1 ); 2880 2881 /* check if the buffer has to be enlarged */ 2882 if ( size > buffer->size[bufnum] ) 2883 { 2884 size_t newsize; 2885 2886 /* enlarge buffer */ 2887 newsize = calcMemoryGrowSize((size_t)buffer->arraygrowinit, buffer->arraygrowfac, size); 2888 BMSreallocMemorySize(&buffer->data[bufnum], newsize); 2889 assert( newsize > buffer->size[bufnum] ); 2890 buffer->totalmem += newsize - buffer->size[bufnum]; 2891 buffer->size[bufnum] = newsize; 2892 if ( buffer->data[bufnum] == NULL ) 2893 { 2894 printErrorHeader(filename, line); 2895 printError("Insufficient memory for reallocating buffer storage.\n"); 2896 return NULL; 2897 } 2898 newptr = buffer->data[bufnum]; 2899 } 2900 assert( buffer->size[bufnum] >= size ); 2901 assert( newptr == buffer->data[bufnum] ); 2902 2903 debugMessage("Reallocated buffer %llu/%llu at %p to size %llu (required size: %llu) for pointer %p.\n", 2904 (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum], 2905 (unsigned long long)(buffer->size[bufnum]), (unsigned long long)size, newptr); 2906 2907 #else 2908 newptr = ptr; 2909 BMSreallocMemorySize(&newptr, size); 2910 #endif 2911 2912 return newptr; 2913 } 2914 2915 /** reallocates the buffer to at least the given size */ 2916 void* BMSreallocBufferMemory_call( 2917 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2918 void* ptr, /**< pointer to the allocated memory buffer */ 2919 size_t size, /**< minimal required size of the buffer */ 2920 const char* filename, /**< source file of the function call */ 2921 int line /**< line number in source file of the function call */ 2922 ) 2923 { 2924 #ifndef NDEBUG 2925 if ( size > MAXMEMSIZE ) 2926 { 2927 printErrorHeader(filename, line); 2928 printError("Tried to allocate buffer of size exceeding %lu.\n", MAXMEMSIZE); 2929 return NULL; 2930 } 2931 #endif 2932 2933 return BMSreallocBufferMemory_work(buffer, ptr, size, filename, line); 2934 } 2935 2936 /** reallocates an array in the buffer to at least the given size */ 2937 void* BMSreallocBufferMemoryArray_call( 2938 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2939 void* ptr, /**< pointer to the allocated memory buffer */ 2940 size_t num, /**< size of array to be allocated */ 2941 size_t typesize, /**< size of components */ 2942 const char* filename, /**< source file of the function call */ 2943 int line /**< line number in source file of the function call */ 2944 ) 2945 { 2946 #ifndef NDEBUG 2947 if ( num > (MAXMEMSIZE / typesize) ) 2948 { 2949 printErrorHeader(filename, line); 2950 printError("Tried to allocate array of size exceeding %lu.\n", MAXMEMSIZE); 2951 return NULL; 2952 } 2953 #endif 2954 2955 return BMSreallocBufferMemory_work(buffer, ptr, num * typesize, filename, line); 2956 } 2957 2958 /** allocates the next unused buffer and copies the given memory into the buffer */ 2959 void* BMSduplicateBufferMemory_call( 2960 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2961 const void* source, /**< memory block to copy into the buffer */ 2962 size_t size, /**< minimal required size of the buffer */ 2963 const char* filename, /**< source file of the function call */ 2964 int line /**< line number in source file of the function call */ 2965 ) 2966 { 2967 void* ptr; 2968 2969 assert( source != NULL ); 2970 2971 /* allocate a buffer of the given size */ 2972 ptr = BMSallocBufferMemory_call(buffer, size, filename, line); 2973 2974 /* copy the source memory into the buffer */ 2975 if ( ptr != NULL ) 2976 BMScopyMemorySize(ptr, source, size); 2977 2978 return ptr; 2979 } 2980 2981 /** allocates an array in the next unused buffer and copies the given memory into the buffer */ 2982 void* BMSduplicateBufferMemoryArray_call( 2983 BMS_BUFMEM* buffer, /**< memory buffer storage */ 2984 const void* source, /**< memory block to copy into the buffer */ 2985 size_t num, /**< size of array to be allocated */ 2986 size_t typesize, /**< size of components */ 2987 const char* filename, /**< source file of the function call */ 2988 int line /**< line number in source file of the function call */ 2989 ) 2990 { 2991 void* ptr; 2992 2993 assert( source != NULL ); 2994 2995 /* allocate a buffer of the given size */ 2996 ptr = BMSallocBufferMemoryArray_call(buffer, num, typesize, filename, line); 2997 2998 /* copy the source memory into the buffer */ 2999 if ( ptr != NULL ) 3000 BMScopyMemorySize(ptr, source, num * typesize); 3001 3002 return ptr; 3003 } 3004 3005 /** work for freeing a buffer */ 3006 INLINE static 3007 void BMSfreeBufferMemory_work( 3008 BMS_BUFMEM* buffer, /**< memory buffer storage */ 3009 void** ptr, /**< pointer to pointer to the allocated memory buffer */ 3010 const char* filename, /**< source file of the function call */ 3011 int line /**< line number in source file of the function call */ 3012 ) 3013 { /*lint --e{715}*/ 3014 size_t bufnum; 3015 3016 assert( buffer != NULL ); 3017 assert( buffer->firstfree <= buffer->ndata ); 3018 assert( buffer->firstfree >= 1 ); 3019 assert( ptr != NULL ); 3020 assert( *ptr != NULL ); 3021 3022 /* Search the pointer in the buffer list: 3023 * Usually, buffers are allocated and freed like a stack, such that the freed pointer is 3024 * most likely at the end of the buffer list. 3025 */ 3026 bufnum = buffer->firstfree-1; 3027 while ( bufnum > 0 && buffer->data[bufnum] != *ptr ) 3028 --bufnum; 3029 3030 #ifdef CHECKBUFFERORDER 3031 if ( bufnum < buffer->firstfree - 1 ) 3032 { 3033 warningMessage("[%s:%d]: freeing buffer in wrong order.\n", filename, line); 3034 } 3035 #endif 3036 3037 #ifndef NDEBUG 3038 if ( bufnum == 0 && buffer->data[bufnum] != *ptr ) 3039 { 3040 printErrorHeader(filename, line); 3041 printError("Tried to free unknown buffer pointer.\n"); 3042 return; 3043 } 3044 if ( ! buffer->used[bufnum] ) 3045 { 3046 printErrorHeader(filename, line); 3047 printError("Tried to free buffer pointer already freed.\n"); 3048 return; 3049 } 3050 #endif 3051 3052 #ifdef CHECKCLEANBUFFER 3053 /* check that the memory is cleared */ 3054 if( buffer->clean ) 3055 { 3056 size_t i; 3057 uint8_t* tmpptr = (uint8_t*)(buffer->data[bufnum]); 3058 3059 for( i = 0; i < buffer->size[bufnum]; ++i ) 3060 assert(tmpptr[i] == 0); 3061 } 3062 #endif 3063 3064 assert( buffer->data[bufnum] == *ptr ); 3065 buffer->used[bufnum] = FALSE; 3066 3067 while ( buffer->firstfree > 0 && !buffer->used[buffer->firstfree-1] ) 3068 --buffer->firstfree; 3069 3070 debugMessage("Freed buffer %llu/%llu at %p of size %llu for pointer %p, first free is %llu.\n", 3071 (unsigned long long)bufnum, (unsigned long long)(buffer->ndata), buffer->data[bufnum], 3072 (unsigned long long)(buffer->size[bufnum]), *ptr, (unsigned long long)(buffer->firstfree)); 3073 3074 *ptr = NULL; 3075 } 3076 3077 /** frees a buffer and sets pointer to NULL */ 3078 void BMSfreeBufferMemory_call( 3079 BMS_BUFMEM* buffer, /**< memory buffer storage */ 3080 void** ptr, /**< pointer to pointer to the allocated memory buffer */ 3081 const char* filename, /**< source file of the function call */ 3082 int line /**< line number in source file of the function call */ 3083 ) 3084 { /*lint --e{715}*/ 3085 assert( ptr != NULL ); 3086 3087 #ifndef SCIP_NOBUFFERMEM 3088 if ( *ptr != NULL ) 3089 BMSfreeBufferMemory_work(buffer, ptr, filename, line); 3090 else 3091 { 3092 printErrorHeader(filename, line); 3093 printError("Tried to free null buffer pointer.\n"); 3094 } 3095 #else 3096 BMSfreeMemory(ptr); 3097 #endif 3098 } 3099 3100 /** frees a buffer if pointer is not NULL and sets pointer to NULL */ 3101 void BMSfreeBufferMemoryNull_call( 3102 BMS_BUFMEM* buffer, /**< memory buffer storage */ 3103 void** ptr, /**< pointer to pointer to the allocated memory buffer */ 3104 const char* filename, /**< source file of the function call */ 3105 int line /**< line number in source file of the function call */ 3106 ) 3107 { /*lint --e{715}*/ 3108 assert( ptr != NULL ); 3109 3110 if ( *ptr != NULL ) 3111 { 3112 #ifndef SCIP_NOBUFFERMEM 3113 BMSfreeBufferMemory_work(buffer, ptr, filename, line); 3114 #else 3115 BMSfreeMemory(ptr); 3116 #endif 3117 } 3118 } 3119 3120 /** gets number of used buffers */ 3121 size_t BMSgetNUsedBufferMemory( 3122 BMS_BUFMEM* buffer /**< memory buffer storage */ 3123 ) 3124 { 3125 assert( buffer != NULL ); 3126 3127 return buffer->firstfree; 3128 } 3129 3130 /** returns the number of allocated bytes in the buffer memory */ 3131 long long BMSgetBufferMemoryUsed( 3132 const BMS_BUFMEM* buffer /**< buffer memory */ 3133 ) 3134 { 3135 #ifdef CHECKMEM 3136 size_t totalmem = 0UL; 3137 size_t i; 3138 3139 assert( buffer != NULL ); 3140 for (i = 0; i < buffer->ndata; ++i) 3141 totalmem += buffer->size[i]; 3142 assert( totalmem == buffer->totalmem ); 3143 #endif 3144 3145 return (long long) buffer->totalmem; 3146 } 3147 3148 /** outputs statistics about currently allocated buffers to the screen */ 3149 void BMSprintBufferMemory( 3150 BMS_BUFMEM* buffer /**< memory buffer storage */ 3151 ) 3152 { 3153 size_t totalmem; 3154 size_t i; 3155 3156 assert( buffer != NULL ); 3157 3158 totalmem = 0UL; 3159 for (i = 0; i < buffer->ndata; ++i) 3160 { 3161 printf("[%c] %8llu bytes at %p\n", buffer->used[i] ? '*' : ' ', (unsigned long long)(buffer->size[i]), buffer->data[i]); 3162 totalmem += buffer->size[i]; 3163 } 3164 printf(" %8llu bytes total in %llu buffers\n", (unsigned long long)totalmem, (unsigned long long)(buffer->ndata)); 3165 } 3166