source: tags/svn.1.5.4/ARBDB/admalloc.cxx

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