source: trunk/ARBDB/admalloc.cxx

Last change on this file was 18730, checked in by westram, 3 years ago
  • remove trailing whitespace from c source.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.4 KB
Line 
1// =============================================================== //
2//                                                                 //
3//   File      : admalloc.cxx                                      //
4//   Purpose   :                                                   //
5//                                                                 //
6//   Institute of Microbiology (Technical University Munich)       //
7//   http://www.arb-home.de/                                       //
8//                                                                 //
9// =============================================================== //
10
11#include <unistd.h>
12#include <climits>
13#include <set>
14
15#include <arb_backtrace.h>
16#include "gb_storage.h"
17
18// #define DUMP_MEMBLKS
19// #define DUMP_MEMBLKS_AT_EXIT
20
21#ifdef DEBUG
22// #define TEST_MEMBLKS
23// #define TRACE_ALLOCS
24
25// @@@ unit tests fail when TRACE_ALLOCS is defined (due to wrong sized block during load(?). cant fix atm. see [6672])
26#endif
27
28#define GBM_MAGIC 0x74732876
29
30#define GBM_SYSTEM_PAGE_SIZE 4096                   // 4k Tables
31#define GBM_MALLOC_OVERHEAD  32                     // pointer for alloc
32#define GBM_TABLE_SIZE       (GBM_SYSTEM_PAGE_SIZE-GBM_MALLOC_OVERHEAD) // usable size of table
33
34#define GBM_ALIGNED    8
35#define GBM_LD_ALIGNED 3
36
37#define GBM_MAX_TABLES 16                           // n different sizes -> max = GBM_MAX_TABLES * GBM_ALIGNED
38#define GBM_MAX_SIZE   (GBM_MAX_TABLES*GBM_ALIGNED)
39#define GBM_MAX_INDEX  256                          // has to be 2 ^ x (with x = GBM_MAX_TABLES ? )
40
41
42struct gbm_data {
43    long      magic;                                // indicates free element
44    gbm_data *next;                                 // next free element
45};
46
47struct gbm_table {                           // a block containing data
48    gbm_table *next;
49    gbm_data   data[1];
50};
51
52static struct gbm_pool {                                   // one pool for each memory index
53    gbm_data  *gds;                                 // free data area
54    size_t     size;                                // free size of current table
55    size_t     allsize;                             // full size of all tables
56    gbm_table *first;                               // link list of tables
57    gbm_data  *tables[GBM_MAX_TABLES+1];            // free entries
58    long       tablecnt[GBM_MAX_TABLES+1];          // number of free entries
59    long       useditems[GBM_MAX_TABLES+1];         // number of used items (everything)
60    size_t     extern_data_size;                    // not handled by this routine
61    long       extern_data_items;
62} gbm_pool4idx[GBM_MAX_INDEX];
63
64static struct {
65    char *old_sbrk;
66} gbm_global;
67
68
69#define GBB_INCR       11                           // memsize increment in percent between adjacent clusters
70#define GBB_CLUSTERS   64                           // # of different clusters
71#define GBB_ALIGN      GBM_LD_ALIGNED               // align memsize of clusters (# of bits)
72#define GBB_MINSIZE    GBM_MAX_SIZE                 // minimal size of allocated big block
73#define GBB_MAX_TRIALS 4                            // maximal number of clusters to search for an unused block
74#define GBB_MAGIC      0x67823747
75
76struct gbb_data;
77
78struct gbb_freedata { // part of gbb_data if it`s a free block
79    // cppcheck-suppress unusedStructMember
80    long      magic;
81    gbb_data *next;  // next unused memblock
82};
83
84struct gbb_data {
85    size_t       size;                              // real size of memblock (from `content` to end of block)
86    long         allocFromSystem;                   // ==0 -> it`s a block imported by gbm_put_mem
87    gbb_freedata content;                           // startposition of block returned to user or chain info for free blocks
88};
89
90#define GBB_HEADER_SIZE (sizeof(gbb_data)-sizeof(gbb_freedata))
91
92static struct gbb_Cluster {
93    size_t    size;                                 // minimum size of memblocks in this cluster
94    gbb_data *first;                                // first free block
95
96} gbb_cluster[GBB_CLUSTERS+1];
97
98
99#ifdef TRACE_ALLOCS
100
101class AllocLogEntry {
102    void   *block;
103    size_t  size;
104    long    index;
105
106    mutable BackTraceInfo *trace;
107
108public:
109    AllocLogEntry(void *block_, size_t size_, long index_, bool do_trace) :
110        block(block_),
111        size(size_),
112        index(index_),
113        trace(do_trace ? GBK_get_backtrace(5) : NULp)
114    { }
115    AllocLogEntry(const AllocLogEntry& other) :
116        block(other.block),
117        size(other.size),
118        index(other.index),
119        trace(other.trace)
120    {
121        other.trace = NULp;
122    }
123    ~AllocLogEntry() { if (trace) GBK_free_backtrace(trace); }
124
125    size_t get_size() const { return size; }
126    long get_index() const { return index; }
127
128    bool operator<(const AllocLogEntry& other) const { return block < other.block; }
129    void dump(FILE *out, GB_CSTR message) const { GBK_dump_former_backtrace(trace, out, message); }
130};
131
132typedef std::set<AllocLogEntry> AllocLogEntries;
133
134class AllocLogger {
135    AllocLogEntries entries;
136
137    const AllocLogEntry *existingEntry(void *block) {
138        AllocLogEntries::const_iterator found = entries.find(AllocLogEntry(block, 0, 0, false));
139
140        return found == entries.end() ? NULp : &*found;
141    }
142
143public:
144    AllocLogger() {
145    }
146    ~AllocLogger() {
147        size_t count = entries.size();
148        if (count) {
149            fprintf(stderr, "%zu non-freed blocks:\n", count);
150            AllocLogEntries::const_iterator end = entries.end();
151            for (AllocLogEntries::const_iterator entry = entries.begin(); entry != end; ++entry) {
152                entry->dump(stderr, "block was allocated from here");
153            }
154        }
155    }
156
157    void allocated(void *block, size_t size, long index) {
158        const AllocLogEntry *exists = existingEntry(block);
159        if (exists) {
160            GBK_dump_backtrace(stderr, "Block allocated again");
161            exists->dump(stderr, "Already allocated from here");
162        }
163        else {
164            entries.insert(AllocLogEntry(block, size, index, true));
165        }
166    }
167    void freed(void *block, size_t size, long index) {
168        const AllocLogEntry *exists = existingEntry(block);
169        if (!exists) {
170            if (!gb_isMappedMemory(block)) {
171                gb_assert(0);
172                // GBK_dump_backtrace(stderr, "Tried to free unallocated block");
173            }
174        }
175        else {
176            gb_assert(exists->get_size() == size);
177            gb_assert(exists->get_index() == index);
178            entries.erase(*exists);
179        }
180    }
181};
182
183static AllocLogger allocLogger;
184
185#endif
186
187inline void free_gbm_table(gbm_table *table) {
188    while (table) {
189        gbm_table *next = table->next;
190
191        free(table);
192        table = next;
193    }
194}
195
196static bool gbm_mem_initialized = false;
197
198void gbm_flush_mem() {
199    gb_assert(gbm_mem_initialized);
200
201    for (int i = 0; i<GBM_MAX_INDEX; ++i) {
202        gbm_pool& gbm             = gbm_pool4idx[i];
203        bool      have_used_items = false;
204
205        for (int t = 0; t < GBM_MAX_TABLES; t++) {
206            if (gbm.useditems[t]) {
207                have_used_items = true;
208                break;
209            }
210        }
211
212        if (!have_used_items) {
213            free_gbm_table(gbm.first);
214            memset((char*)&gbm, 0, sizeof(gbm));
215        }
216    }
217}
218
219void gbm_init_mem() {
220    if (!gbm_mem_initialized) {
221        for (int i = 0; i<GBM_MAX_INDEX; ++i) {
222            memset((char *)&gbm_pool4idx[i], 0, sizeof(gbm_pool));
223            gbm_pool4idx[i].tables[0] = NULp; // CORE zero get mem
224        }
225        gbm_global.old_sbrk = (char *)sbrk(0);
226
227        /* init GBB:
228         * --------- */
229
230        gbb_cluster[0].size  = GBB_MINSIZE;
231        gbb_cluster[0].first = NULp;
232
233        for (int i = 1; i<GBB_CLUSTERS; ++i) {
234            long nextSize = gbb_cluster[i-1].size * (100+GBB_INCR);
235
236            nextSize /= 100;
237            nextSize >>= GBB_ALIGN;
238            nextSize ++;
239            nextSize <<= GBB_ALIGN;
240
241            gbb_cluster[i].size  = nextSize;
242            gbb_cluster[i].first = NULp;
243        }
244
245        // last cluster contains ALL bigger blocks
246
247        gbb_cluster[GBB_CLUSTERS].size  = INT_MAX;
248        gbb_cluster[GBB_CLUSTERS].first = NULp;
249
250        gbm_mem_initialized = true;
251    }
252}
253
254struct ARBDB_memory_manager {
255    ARBDB_memory_manager() {
256        gb_assert(!gbm_mem_initialized); // there may be only one instance!
257        gbm_init_mem();
258    }
259    ~ARBDB_memory_manager() {
260#if defined(DUMP_MEMBLKS_AT_EXIT)
261        printf("memory at exit:\n");
262        gbm_debug_mem();
263#endif // DUMP_MEMBLKS_AT_EXIT
264        gbm_flush_mem();
265#if defined(DUMP_MEMBLKS_AT_EXIT)
266        printf("memory at exit (after flush):\n");
267        gbm_debug_mem();
268#endif // DUMP_MEMBLKS_AT_EXIT
269    }
270};
271static ARBDB_memory_manager memman;
272
273#ifdef TEST_MEMBLKS
274
275#define TEST() testMemblocks(__FILE__, __LINE__)
276
277void testMemblocks(const char *file, int line) {
278    int idx;
279
280    for (idx=0; idx<GBB_CLUSTERS; idx++) {
281        struct gbb_Cluster *cl  = &(gbb_cluster[idx]);
282        gbb_data           *blk = cl->first;
283
284        while (blk) {
285            if (blk->size<cl->size) {
286                fprintf(stderr, "Illegal block (size=%zu) in cluster %i (size=%zu) (%s,%i)\n", blk->size, idx, cl->size, file, line);
287                gb_assert(0);
288            }
289            blk = blk->content.next;
290        }
291    }
292}
293
294#else
295#   define TEST()
296#endif
297
298
299#if (MEMORY_TEST==0)
300
301static void imemerr(const char *why) {
302    GB_internal_errorf("Dangerous internal error: '%s'\n"
303                       "Inconsistent database: Do not overwrite old files with this database", why);
304}
305
306static int getClusterIndex(size_t size) {
307    // searches the index of the lowest cluster for that: size <= cluster->size
308    int l, m, h;
309
310    if (size<GBB_MINSIZE) return 0;
311
312    l = 1;
313    h = GBB_CLUSTERS;
314
315    while (l!=h) {
316        m = (l+h)/2;
317        if (gbb_cluster[m].size < size)  l = m+1;
318        else                 h = m;
319    }
320
321    gb_assert(l<=GBB_CLUSTERS);
322
323    return l;
324}
325
326static void gbm_put_memblk(char *memblk, size_t size) {
327    /* gives any memory block (allocated or not)
328       into the responsibility of this module;
329       the block has to be aligned!!! */
330
331    gbb_data *block;
332    int       idx;
333
334    TEST();
335
336#ifdef DUMP_MEMBLKS
337    printf("put %p (%li bytes)\n", memblk, size);
338#endif
339
340    if (size<(GBB_HEADER_SIZE+GBB_MINSIZE)) {
341        GB_internal_errorf("gmb_put_memblk() called with size below %zu bytes",
342                           GBB_HEADER_SIZE+GBB_MINSIZE);
343        return;
344    }
345
346    block                  = (gbb_data *)memblk;
347    block->size            = size-GBB_HEADER_SIZE;
348    block->allocFromSystem = 0;
349
350    idx = getClusterIndex(block->size)-1;
351    if (idx<0) { // (silences warning in NDEBUG mode)
352        gb_assert(0); // should be impossible
353        return;
354    }
355
356    block->content.next     = gbb_cluster[idx].first;
357    block->content.magic    = GBB_MAGIC;
358    gbb_cluster[idx].first  = block;
359
360    gb_assert(idx==GBB_CLUSTERS || block->size>=gbb_cluster[idx].size);
361    TEST();
362}
363
364static char *gbm_get_memblk(size_t size) {
365    gbb_data *block  = NULp;
366    int       trials = GBB_MAX_TRIALS;
367    int       idx;
368
369    TEST();
370
371    idx = getClusterIndex(size);
372    gb_assert(gbb_cluster[idx].size>=size);
373
374    while (trials--) { // search a cluster containing a block
375        if ((block = gbb_cluster[idx].first)) break;  // found!
376        if (idx==GBB_CLUSTERS) break;                 // last cluster!
377        idx++;
378    }
379
380    if (!block) { // if no unused block -> allocate from system
381        int allocationSize;
382
383    allocFromSys :
384
385        allocationSize = (idx==GBB_CLUSTERS
386                          ? (size_t)size
387                          : (size_t)(gbb_cluster[idx].size)) + GBB_HEADER_SIZE;
388
389        block = (gbb_data *)ARB_calloc<char>(allocationSize);
390
391        block->size            = allocationSize-GBB_HEADER_SIZE;
392        block->allocFromSystem = 1;
393
394        gb_assert(block->size>=size);
395
396#ifdef DUMP_MEMBLKS
397        printf("allocated %li bytes\n", size);
398#endif
399    }
400    else {
401        gbb_data **blockPtr = &(gbb_cluster[idx].first);
402
403        if (idx==GBB_CLUSTERS) { // last cluster (test for block size necessary)
404            while ((block=*blockPtr) && block->size<size)
405                blockPtr = &(block->content.next);
406
407            if (!block) goto allocFromSys;
408            gb_assert(block->size>=size);
409        }
410
411        if (block->content.magic!=GBB_MAGIC) { imemerr("bad magic number if free block"); return NULp; }
412        *blockPtr = block->content.next;
413        memset((char*)&(block->content), 0, size);  // act like calloc
414
415#ifdef DUMP_MEMBLKS
416        printf("using unused block "
417               "(add=%p,size=%li, block->size=%li,cluster->size=%li)\n",
418               block, size, block->size, gbb_cluster[idx].size);
419#endif
420
421        gb_assert(block->size>=size);
422    }
423
424    gb_assert(block->size>=size);
425
426    TEST();
427
428    return (char*)&(block->content);
429}
430
431void *gbmGetMemImpl(size_t size, long index) {
432    if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
433    index &= GBM_MAX_INDEX-1;
434
435    gbm_pool      *ggi   = &gbm_pool4idx[index];
436    unsigned long  nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
437
438    char *result;
439    if (nsize > GBM_MAX_SIZE) {
440        ggi->extern_data_size += nsize;
441        ggi->extern_data_items++;
442
443        result = gbm_get_memblk((size_t)nsize);
444    }
445    else {
446        unsigned long  pos = nsize >> GBM_LD_ALIGNED;
447        gbm_data      *gds = ggi->tables[pos];
448        if (gds) {
449            ggi->tablecnt[pos]--;
450            result = (char *)gds;
451            if (gds->magic != GBM_MAGIC) {
452                printf("%lX!= %lX\n", gds->magic, (long)GBM_MAGIC);
453                GB_internal_error("Dangerous internal error: Inconsistent database: "
454                                  "Do not overwrite old files with this database");
455            }
456            ggi->tables[pos] = ggi->tables[pos]->next;
457        }
458        else {
459            if (ggi->size < nsize) {
460                gbm_table *gts;
461                arb_mem::alloc_aligned((void**)(&gts), GBM_SYSTEM_PAGE_SIZE, GBM_TABLE_SIZE);
462
463                memset((char *)gts, 0, GBM_TABLE_SIZE);
464                ggi->gds = &gts->data[0];
465                gts->next = ggi->first; // link tables
466                ggi->first = gts;
467                ggi->size = GBM_TABLE_SIZE - sizeof(void *);
468                ggi->allsize += GBM_TABLE_SIZE;
469            }
470            result = (char *)ggi->gds;
471            ggi->gds = (gbm_data *)(((char *)ggi->gds) + nsize);
472            ggi->size -= (size_t)nsize;
473        }
474
475        ggi->useditems[pos]++;
476        memset(result, 0, nsize); // act like calloc()
477    }
478
479#ifdef TRACE_ALLOCS
480    allocLogger.allocated(erg, size, index);
481#endif
482    return result;
483}
484
485void gbmFreeMemImpl(void *data, size_t size, long index) {
486    if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
487    index &= GBM_MAX_INDEX-1;
488
489    gbm_pool *ggi   = &gbm_pool4idx[index];
490    long      nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
491
492#ifdef TRACE_ALLOCS
493    allocLogger.freed(data, size, index);
494#endif
495
496    if (nsize > GBM_MAX_SIZE) {
497        gbb_data *block;
498
499        if (gb_isMappedMemory(data)) {
500            block = (gbb_data *)data;
501
502            block->size = size-GBB_HEADER_SIZE;
503            block->allocFromSystem = 0;
504
505            if (size>=(GBB_HEADER_SIZE+GBB_MINSIZE)) {
506                gbm_put_memblk((char*)block, size);
507            }
508        }
509        else {
510            block = (gbb_data *)((char*)data-GBB_HEADER_SIZE);
511
512            ggi->extern_data_size -= (size_t)nsize;
513            ggi->extern_data_items--;
514
515            if (block->size<size) { imemerr("block size does not match"); return; }
516
517            if (block->allocFromSystem) {
518                free(block);
519            }
520            else {
521                /* printf("put unused block (size=%li block->size=%li)\n",
522                   size,block->size); */
523                gbm_put_memblk((char*)block, block->size + GBB_HEADER_SIZE);
524            }
525        }
526    }
527    else {
528        if (gb_isMappedMemory(data)) return;    //   @@@ reason: size may be shorter
529
530        gbm_data *gdata = (gbm_data*)data;
531
532        if (gdata->magic == GBM_MAGIC) {
533            imemerr("double free");
534            return;
535        }
536
537        long pos = nsize >> GBM_LD_ALIGNED;
538
539        gdata->next      = ggi->tables[pos];
540        gdata->magic     = GBM_MAGIC;
541        ggi->tables[pos] = gdata;
542        ggi->tablecnt[pos]++;
543        ggi->useditems[pos]--;
544    }
545}
546
547#endif // MEMORY_TEST==0
548
549void gbm_debug_mem() {
550    int       i;
551    int       index;
552    long      total = 0;
553    long      index_total;
554    gbm_pool *ggi;
555
556    printf("Memory Debug Information:\n");
557    for (index = 0; index < GBM_MAX_INDEX; index++) {
558        index_total = 0;
559        ggi = &gbm_pool4idx[index];
560        for (i = 0; i < GBM_MAX_TABLES; i++) {
561            index_total += i * GBM_ALIGNED * (int) ggi->useditems[i];
562            total += i * GBM_ALIGNED * (int) ggi->useditems[i];
563
564            if (ggi->useditems[i] || ggi->tablecnt[i]) {
565                printf("\t'I=%3i' 'Size=%3i' * 'Items %4i' = 'size %7i'    'sum=%7li'   'totalsum=%7li' :   Free %3i\n",
566                       index,
567                       i * GBM_ALIGNED,
568                       (int) ggi->useditems[i],
569                       i * GBM_ALIGNED * (int) ggi->useditems[i],
570                       index_total,
571                       total,
572                       (int) ggi->tablecnt[i]);
573            }
574        }
575        if (ggi->extern_data_size) {
576            index_total += ggi->extern_data_size;
577            total += ggi->extern_data_size;
578            printf("\t'I=%3i' External Data Items=%3li = Sum=%3li  'sum=%7li'  'total=%7li\n",
579                   index,
580                   ggi->extern_data_items,
581                   (long)ggi->extern_data_size,
582                   index_total,
583                   total);
584        }
585    }
586
587    {
588        char *topofmem = (char *)sbrk(0);
589        printf("spbrk %lx old %lx size %ti\n",
590               (long)topofmem,
591               (long)gbm_global.old_sbrk,
592               topofmem-gbm_global.old_sbrk);
593    }
594}
595
596// --------------------------------------------------------------------------------
597
598#if defined(UNIT_TESTS) && 0
599
600#include <test_unit.h>
601
602void TEST_ARBDB_memory() { // not a real unit test - just was used for debugging
603#define ALLOCS 69
604    long *blocks[ALLOCS];
605
606#if (MEMORY_TEST == 0)
607    printf("Before allocations:\n");
608    gbm_debug_mem();
609
610#if 1
611    static int16_t non_alloc[75];                   // 150 byte
612    gbm_put_memblk((char*)non_alloc, sizeof(non_alloc));
613
614    printf("Added one non-allocated block:\n");
615    gbm_debug_mem();
616#endif
617#endif
618
619    for (int pass = 1; pass <= 2; ++pass) {
620        long allocs = 0;
621
622        for (size_t size = 10; size<5000; size += size/3) {
623            for (long index = 0; index<3; ++index) {
624                if (pass == 1) {
625                    long *block = (long*)gbm_get_mem(size, index);
626
627                    block[0] = size;
628                    block[1] = index;
629
630                    blocks[allocs++] = block;
631                }
632                else {
633                    long *block = blocks[allocs++];
634                    gbm_free_mem(block, (size_t)block[0], block[1]);
635                }
636            }
637        }
638
639#if (MEMORY_TEST == 0)
640        if (pass == 1) {
641            printf("%li memory blocks allocated:\n", allocs);
642            gbm_debug_mem();
643        }
644        else {
645            printf("Memory freed:\n");
646            gbm_debug_mem();
647        }
648        printf("Memory flushed:\n");
649        gbm_flush_mem();
650        gbm_debug_mem();
651#endif
652
653        gb_assert(allocs == ALLOCS);
654    }
655
656    GBK_dump_backtrace(stderr, "test");
657}
658
659
660#endif // UNIT_TESTS
Note: See TracBrowser for help on using the repository browser.