Context Navigation

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

Visit:

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
47	struct gbm_data {
48	long magic; // indicates free element
49	gbm_data *next; // next free element
50	};
51
52	struct gbm_table { // a block containing data
53	gbm_table *next;
54	gbm_data data[1];
55	};
56
57	static 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
69	static 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
81	struct gbb_data;
82
83	struct 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
89	struct 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
97	static 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
105	NOT4PERL 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
119	NOT4PERL 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
146	class AllocLogEntry {
147	void *block;
148	size_t size;
149	long index;
150
151	mutable BackTraceInfo *trace;
152
153	public:
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
177	typedef std::set<AllocLogEntry> AllocLogEntries;
178
179	class 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
188	public:
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
228	static AllocLogger allocLogger;
229
230	#endif
231
232	inline 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
241	static bool gbm_mem_initialized = false;
242
243	void 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
264	void 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
299	struct 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	};
316	static ARBDB_memory_manager memman;
317
318	void 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
327	void 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
355	static 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
361	static 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
384	static 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
420	static 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
492	inline 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
499	void *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
561	void 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
630	void 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
685	void 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.

Download in other formats: