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