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