source: branches/alilink/ARBDB/admalloc.cxx

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