Context Navigation

source: tags/arb-6.0.6/ARBDB/admalloc.cxx

Visit:

Last change on this file was 11889, checked in by westram, 12 years ago
add missing comment to closing #endif of test-sections
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	#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
43	struct gbm_data {
44	long magic; // indicates free element
45	gbm_data *next; // next free element
46	};
47
48	struct gbm_table { // a block containing data
49	gbm_table *next;
50	gbm_data data[1];
51	};
52
53	static 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
65	static 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
77	struct gbb_data;
78
79	struct 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
86	struct 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
94	static 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	NOT4PERL void *GB_calloc(unsigned int nelem, unsigned int elsize)
103	{
104	size_t size = nelem*elsize;
105	void *mem = malloc(size);
106
107	if (mem) {
108	memset(mem, 0, size);
109	}
110	else {
111	fprintf(stderr, "Panic Error: insufficient memory: tried to get %u*%u bytes\n", nelem, elsize);
112	}
113	return mem;
114	}
115
116	NOT4PERL void GB_recalloc(void ptr, unsigned int oelem, unsigned int nelem, unsigned int elsize)
117	{
118	size_t nsize = nelem*elsize;
119	void *mem = malloc(nsize);
120
121	if (mem) {
122	size_t osize = oelem*elsize;
123
124	if (nsize>=osize) {
125	memmove(mem, ptr, osize);
126	if (nsize>osize) {
127	memset(((char*)mem)+osize, 0, nsize-osize);
128	}
129	}
130	else {
131	memmove(mem, ptr, nsize);
132	}
133	}
134	else {
135	fprintf(stderr, "Panic Error: insufficient memory: tried to get %u*%u bytes\n", nelem, elsize);
136	}
137
138	return mem;
139	}
140
141	#ifdef TRACE_ALLOCS
142
143	class AllocLogEntry {
144	void *block;
145	size_t size;
146	long index;
147
148	mutable BackTraceInfo *trace;
149
150	public:
151	AllocLogEntry(void *block_, size_t size_, long index_, bool do_trace)
152	: block(block_)
153	, size(size_)
154	, index(index_)
155	, trace(do_trace ? GBK_get_backtrace(5) : NULL)
156	{ }
157	AllocLogEntry(const AllocLogEntry& other)
158	: block(other.block)
159	, size(other.size)
160	, index(other.index)
161	, trace(other.trace)
162	{
163	other.trace = NULL;
164	}
165	~AllocLogEntry() { if (trace) GBK_free_backtrace(trace); }
166
167	size_t get_size() const { return size; }
168	long get_index() const { return index; }
169
170	bool operator<(const AllocLogEntry& other) const { return block < other.block; }
171	void dump(FILE *out, GB_CSTR message) const { GBK_dump_former_backtrace(trace, out, message); }
172	};
173
174	typedef std::set<AllocLogEntry> AllocLogEntries;
175
176	class AllocLogger {
177	AllocLogEntries entries;
178
179	const AllocLogEntry existingEntry(void block) {
180	AllocLogEntries::const_iterator found = entries.find(AllocLogEntry(block, 0, 0, false));
181
182	return found == entries.end() ? NULL : &*found;
183	}
184
185	public:
186	AllocLogger() {
187	}
188	~AllocLogger() {
189	size_t count = entries.size();
190	if (count) {
191	fprintf(stderr, "%zu non-freed blocks:\n", count);
192	AllocLogEntries::const_iterator end = entries.end();
193	for (AllocLogEntries::const_iterator entry = entries.begin(); entry != end; ++entry) {
194	entry->dump(stderr, "block was allocated from here");
195	}
196	}
197	}
198
199	void allocated(void *block, size_t size, long index) {
200	const AllocLogEntry *exists = existingEntry(block);
201	if (exists) {
202	GBK_dump_backtrace(stderr, "Block allocated again");
203	exists->dump(stderr, "Already allocated from here");
204	}
205	else {
206	entries.insert(AllocLogEntry(block, size, index, true));
207	}
208	}
209	void freed(void *block, size_t size, long index) {
210	const AllocLogEntry *exists = existingEntry(block);
211	if (!exists) {
212	if (!gb_isMappedMemory(block)) {
213	gb_assert(0);
214	// GBK_dump_backtrace(stderr, "Tried to free unallocated block");
215	}
216	}
217	else {
218	gb_assert(exists->get_size() == size);
219	gb_assert(exists->get_index() == index);
220	entries.erase(*exists);
221	}
222	}
223	};
224
225	static AllocLogger allocLogger;
226
227	#endif
228
229	inline void free_gbm_table(gbm_table *table) {
230	while (table) {
231	gbm_table *next = table->next;
232
233	free(table);
234	table = next;
235	}
236	}
237
238	static bool gbm_mem_initialized = false;
239
240	void gbm_flush_mem() {
241	gb_assert(gbm_mem_initialized);
242
243	for (int i = 0; i<GBM_MAX_INDEX; ++i) {
244	gbm_pool& gbm = gbm_pool4idx[i];
245	bool have_used_items = false;
246
247	for (int t = 0; t < GBM_MAX_TABLES; t++) {
248	if (gbm.useditems[t]) {
249	have_used_items = true;
250	break;
251	}
252	}
253
254	if (!have_used_items) {
255	free_gbm_table(gbm.first);
256	memset((char*)&gbm, 0, sizeof(gbm));
257	}
258	}
259	}
260
261	void gbm_init_mem() {
262	if (!gbm_mem_initialized) {
263	for (int i = 0; i<GBM_MAX_INDEX; ++i) {
264	memset((char *)&gbm_pool4idx[i], 0, sizeof(gbm_pool));
265	gbm_pool4idx[i].tables[0] = 0; // CORE zero get mem
266	}
267	gbm_global.old_sbrk = (char *)sbrk(0);
268
269	/* init GBB:
270	* --------- */
271
272	gbb_cluster[0].size = GBB_MINSIZE;
273	gbb_cluster[0].first = NULL;
274
275	for (int i = 1; i<GBB_CLUSTERS; ++i) {
276	long nextSize = gbb_cluster[i-1].size * (100+GBB_INCR);
277
278	nextSize /= 100;
279	nextSize >>= GBB_ALIGN;
280	nextSize ++;
281	nextSize <<= GBB_ALIGN;
282
283	gbb_cluster[i].size = nextSize;
284	gbb_cluster[i].first = NULL;
285	}
286
287	// last cluster contains ALL bigger blocks
288
289	gbb_cluster[GBB_CLUSTERS].size = INT_MAX;
290	gbb_cluster[GBB_CLUSTERS].first = NULL;
291
292	gbm_mem_initialized = true;
293	}
294	}
295
296	struct ARBDB_memory_manager {
297	ARBDB_memory_manager() {
298	gb_assert(!gbm_mem_initialized); // there may be only one instance!
299	gbm_init_mem();
300	}
301	~ARBDB_memory_manager() {
302	#if defined(DUMP_MEMBLKS_AT_EXIT)
303	printf("memory at exit:\n");
304	gbm_debug_mem();
305	#endif // DUMP_MEMBLKS_AT_EXIT
306	gbm_flush_mem();
307	#if defined(DUMP_MEMBLKS_AT_EXIT)
308	printf("memory at exit (after flush):\n");
309	gbm_debug_mem();
310	#endif // DUMP_MEMBLKS_AT_EXIT
311	}
312	};
313	static ARBDB_memory_manager memman;
314
315	void GB_memerr()
316	{
317	GB_internal_error("memory allocation error - maybe you're out of swap space?");
318	}
319
320	#ifdef TEST_MEMBLKS
321
322	#define TEST() testMemblocks(__FILE__, __LINE__)
323
324	void testMemblocks(const char *file, int line)
325	{
326	int idx;
327
328	for (idx=0; idx<GBB_CLUSTERS; idx++)
329	{
330	struct gbb_Cluster *cl = &(gbb_cluster[idx]);
331	gbb_data *blk = cl->first;
332
333	while (blk)
334	{
335	if (blk->size<cl->size)
336	{
337	fprintf(stderr, "Illegal block (size=%zu) in cluster %i (size=%zu) (%s,%i)\n", blk->size, idx, cl->size, file, line);
338	gb_assert(0);
339	}
340	blk = blk->content.next;
341	}
342	}
343	}
344
345	#else
346	# define TEST()
347	#endif
348
349
350	#if (MEMORY_TEST==0)
351
352	static void imemerr(const char *why)
353	{
354	GB_internal_errorf("Dangerous internal error: '%s'\n"
355	"Inconsistent database: Do not overwrite old files with this database", why);
356	}
357
358	static int getClusterIndex(size_t size) /* searches the index of the
359	lowest cluster for that:
360	size <= cluster->size */
361	{
362	int l, m, h;
363
364	if (size<GBB_MINSIZE) return 0;
365
366	l = 1;
367	h = GBB_CLUSTERS;
368
369	while (l!=h)
370	{
371	m = (l+h)/2;
372	if (gbb_cluster[m].size < size) l = m+1;
373	else h = m;
374	}
375
376	gb_assert(l<=GBB_CLUSTERS);
377
378	return l;
379	}
380
381	static void gbm_put_memblk(char *memblk, size_t size) {
382	/* gives any memory block (allocated or not)
383	into the responsibility of this module;
384	the block has to be aligned!!! */
385
386	gbb_data *block;
387	int idx;
388
389	TEST();
390
391	#ifdef DUMP_MEMBLKS
392	printf("put %p (%li bytes)\n", memblk, size);
393	#endif
394
395	if (size<(GBB_HEADER_SIZE+GBB_MINSIZE))
396	{
397	GB_internal_errorf("gmb_put_memblk() called with size below %zu bytes",
398	GBB_HEADER_SIZE+GBB_MINSIZE);
399	return;
400	}
401
402	block = (gbb_data *)memblk;
403	block->size = size-GBB_HEADER_SIZE;
404	block->allocFromSystem = 0;
405
406	idx = getClusterIndex(block->size)-1;
407	if (idx<0) { // (silences warning in NDEBUG mode)
408	gb_assert(0); // should be impossible
409	return;
410	}
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	if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
501	index &= GBM_MAX_INDEX-1;
502
503	gbm_pool *ggi = &gbm_pool4idx[index];
504	unsigned long nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
505
506	char *result;
507	if (nsize > GBM_MAX_SIZE) {
508	ggi->extern_data_size += nsize;
509	ggi->extern_data_items++;
510
511	result = gbm_get_memblk((size_t)nsize);
512	}
513	else {
514	unsigned long pos = nsize >> GBM_LD_ALIGNED;
515	gbm_data *gds = ggi->tables[pos];
516	if (gds) {
517	ggi->tablecnt[pos]--;
518	result = (char *)gds;
519	if (gds->magic != GBM_MAGIC) {
520	printf("%lX!= %lX\n", gds->magic, (long)GBM_MAGIC);
521	GB_internal_error("Dangerous internal error: Inconsistent database: "
522	"Do not overwrite old files with this database");
523	}
524	ggi->tables[pos] = ggi->tables[pos]->next;
525	}
526	else {
527	if (ggi->size < nsize) {
528	gbm_table gts = (gbm_table )GB_MEMALIGN(GBM_SYSTEM_PAGE_SIZE, GBM_TABLE_SIZE);
529
530	if (!gts) { GB_memerr(); return NULL; }
531
532	memset((char *)gts, 0, GBM_TABLE_SIZE);
533	ggi->gds = &gts->data[0];
534	gts->next = ggi->first; // link tables
535	ggi->first = gts;
536	ggi->size = GBM_TABLE_SIZE - sizeof(void *);
537	ggi->allsize += GBM_TABLE_SIZE;
538	}
539	result = (char *)ggi->gds;
540	ggi->gds = (gbm_data )(((char )ggi->gds) + nsize);
541	ggi->size -= (size_t)nsize;
542	}
543
544	ggi->useditems[pos]++;
545	memset(result, 0, nsize); // act like calloc()
546	}
547
548	#ifdef TRACE_ALLOCS
549	allocLogger.allocated(erg, size, index);
550	#endif
551	return result;
552	}
553
554	void gbmFreeMemImpl(void *data, size_t size, long index) {
555	if (size < sizeof(gbm_data)) size = sizeof(gbm_data);
556	index &= GBM_MAX_INDEX-1;
557
558	gbm_pool *ggi = &gbm_pool4idx[index];
559	long nsize = (size + (GBM_ALIGNED - 1)) & (-GBM_ALIGNED);
560
561	#ifdef TRACE_ALLOCS
562	allocLogger.freed(data, size, index);
563	#endif
564
565	if (nsize > GBM_MAX_SIZE) {
566	gbb_data *block;
567
568	if (gb_isMappedMemory(data)) {
569	block = (gbb_data *)data;
570
571	block->size = size-GBB_HEADER_SIZE;
572	block->allocFromSystem = 0;
573
574	if (size>=(GBB_HEADER_SIZE+GBB_MINSIZE)) {
575	gbm_put_memblk((char*)block, size);
576	}
577	}
578	else {
579	block = (gbb_data )((char)data-GBB_HEADER_SIZE);
580
581	ggi->extern_data_size -= (size_t)nsize;
582	ggi->extern_data_items--;
583
584	if (block->size<size) { imemerr("block size does not match"); return; }
585
586	if (block->allocFromSystem) {
587	free(block);
588	}
589	else {
590	/* printf("put unused block (size=%li block->size=%li)\n",
591	size,block->size); */
592	gbm_put_memblk((char*)block, block->size + GBB_HEADER_SIZE);
593	}
594	}
595	}
596	else
597	{
598	if (gb_isMappedMemory(data)) return; // @@@ reason: size may be shorter
599
600	gbm_data gdata = (gbm_data)data;
601
602	if (gdata->magic == GBM_MAGIC) {
603	imemerr("double free");
604	return;
605	}
606
607	long pos = nsize >> GBM_LD_ALIGNED;
608
609	gdata->next = ggi->tables[pos];
610	gdata->magic = GBM_MAGIC;
611	ggi->tables[pos] = gdata;
612	ggi->tablecnt[pos]++;
613	ggi->useditems[pos]--;
614	}
615	}
616
617	#endif // MEMORY_TEST==0
618
619	void gbm_debug_mem() {
620	int i;
621	int index;
622	long total = 0;
623	long index_total;
624	gbm_pool *ggi;
625
626	printf("Memory Debug Information:\n");
627	for (index = 0; index < GBM_MAX_INDEX; index++)
628	{
629	index_total = 0;
630	ggi = &gbm_pool4idx[index];
631	for (i = 0; i < GBM_MAX_TABLES; i++)
632	{
633	index_total += i * GBM_ALIGNED * (int) ggi->useditems[i];
634	total += i * GBM_ALIGNED * (int) ggi->useditems[i];
635
636	if (ggi->useditems[i] \|\| ggi->tablecnt[i]) {
637	printf("\t'I=%3i' 'Size=%3i' * 'Items %4i' = 'size %7i' 'sum=%7li' 'totalsum=%7li' : Free %3i\n",
638	index,
639	i * GBM_ALIGNED,
640	(int) ggi->useditems[i],
641	i * GBM_ALIGNED * (int) ggi->useditems[i],
642	index_total,
643	total,
644	(int) ggi->tablecnt[i]);
645	}
646	}
647	if (ggi->extern_data_size) {
648	index_total += ggi->extern_data_size;
649	total += ggi->extern_data_size;
650	printf("\t'I=%3i' External Data Items=%3li = Sum=%3li 'sum=%7li' 'total=%7li\n",
651	index,
652	ggi->extern_data_items,
653	(long)ggi->extern_data_size,
654	index_total,
655	total);
656	}
657	}
658
659	{
660	char topofmem = (char )sbrk(0);
661	printf("spbrk %lx old %lx size %ti\n",
662	(long)topofmem,
663	(long)gbm_global.old_sbrk,
664	topofmem-gbm_global.old_sbrk);
665	}
666	}
667
668	// --------------------------------------------------------------------------------
669
670	#if defined(UNIT_TESTS) && 0
671
672	#include <test_unit.h>
673
674	void TEST_ARBDB_memory() { // not a real unit test - just was used for debugging
675	#define ALLOCS 69
676	long *blocks[ALLOCS];
677
678	#if (MEMORY_TEST == 0)
679	printf("Before allocations:\n");
680	gbm_debug_mem();
681
682	#if 1
683	static int16_t non_alloc[75]; // 150 byte
684	gbm_put_memblk((char*)non_alloc, sizeof(non_alloc));
685
686	printf("Added one non-allocated block:\n");
687	gbm_debug_mem();
688	#endif
689	#endif
690
691	for (int pass = 1; pass <= 2; ++pass) {
692	long allocs = 0;
693
694	for (size_t size = 10; size<5000; size += size/3) {
695	for (long index = 0; index<3; ++index) {
696	if (pass == 1) {
697	long block = (long)gbm_get_mem(size, index);
698
699	block[0] = size;
700	block[1] = index;
701
702	blocks[allocs++] = block;
703	}
704	else {
705	long *block = blocks[allocs++];
706	gbm_free_mem(block, (size_t)block[0], block[1]);
707	}
708	}
709	}
710
711	#if (MEMORY_TEST == 0)
712	if (pass == 1) {
713	printf("%li memory blocks allocated:\n", allocs);
714	gbm_debug_mem();
715	}
716	else {
717	printf("Memory freed:\n");
718	gbm_debug_mem();
719	}
720	printf("Memory flushed:\n");
721	gbm_flush_mem();
722	gbm_debug_mem();
723	#endif
724
725	gb_assert(allocs == ALLOCS);
726	}
727
728	GBK_dump_backtrace(stderr, "test");
729	}
730
731
732	#endif // UNIT_TESTS

Note: See TracBrowser for help on using the repository browser.

Download in other formats: