source: tags/ms_r17q3/ARBDB/admalloc.cxx

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